Palindrome

input/code.cpp: In function 'int edit(std::string, std::string)':
input/code.cpp:9:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int y = 0; y <= s.length(); y++) {
                                 ^
input/code.cpp:10:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int x = 0; x <= t.length(); x++) {
                                   ^
input/code.cpp: In function 'bool ok(int)':
input/code.cpp:28:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (i + 1 >= s.length()) return false;
                         ^
input/code.cpp: In function 'bool ok2(int)':
input/code.cpp:45:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (i + 2 >= s.length()) return false;
                         ^
input/code.cpp: In function 'int main()':
input/code.cpp:61:29: warning: comparison between signed and unsigned integer...

#include <bits/stdc++.h>
#define ll long long
#define N (1<<17)

using namespace std;

int edit (string s, string t) {
  int dp[s.length() + 1][t.length() + 1];
  for (int y = 0; y <= s.length(); y++) {
    for (int x = 0; x <= t.length(); x++) {
      if (x == 0) dp[y][0] = y; 
      else if (y == 0) dp[0][x] = x;
      else dp[y][x] = min(min(dp[y][x - 1] + 1, dp[y - 1][x] + 1), dp[y - 1][x - 1] + (s[y - 1] == t[x - 1] ? 0 : 1));
    }
  }
  return dp[s.length()][t.length()];
}

int ans = 999999999;
string s;
bool ok (int i) {
  string x = s.substr(0, i);
  string y = s.substr(i, s.length() - i);
  reverse(y.begin(), y.end());
  int a = edit(x, y);
  ans = min(ans, a);
  if (((int)s.length()) - i - 1 < 0) return false;
  if (i + 1 >= s.length()) return false;
  x = s.substr(0, i + 1);
  y = s.substr(i + 1, s.length() - i - 1);
  reverse(y.begin(), y.end());
  int b = edit(x, y);
  ans = min(min(a, b), ans);
  return b <= a;
}

bool ok2 (int i) {
  string x = s.substr(0, i);
  string y = s.substr(i + 1, s.length() - i - 1);
  reverse(y.begin(), y.end());
  int a = edit(x, y);
  ans = min(ans, a);
  
  if (((int)s.length()) - i - 2 < 0) return false;
  if (i + 2 >= s.length()) return false;
  x = s.substr(0, i + 1);
  y = s.substr(i + 2, ((int)s.length()) - i - 2);
  reverse(y.begin(), y.end());
  int b = edit(x, y);
  ans = min(min(a, b), ans);
  return b <= a;
}

int main () {
  cin>>s;
  if (s.length() == 1) cout<<0<<endl, exit(0);
  
  int k = s.length();
  int i = 0;
  for (; k >= 1; k /= 2) {
    while (i + k < s.length() && ok(i + k)) i += k;
  }
  int j = 0;
  k = s.length();
  for (; k >= 1; k /= 2) {
    while (j + k < s.length() && ok2(j + k)) j += k;
  }
  cout<<ans<<endl;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: WRONG ANSWER

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: WRONG ANSWER

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: WRONG ANSWER

Test 17

Verdict: ACCEPTED

Test 18

Verdict: ACCEPTED

Test 19

Verdict: ACCEPTED

Test 20

Verdict: WRONG ANSWER

Test 21

Verdict: ACCEPTED

Test 22

Verdict: ACCEPTED

Test 23

Verdict: ACCEPTED

Test 24

Verdict: ACCEPTED

Test 25

Verdict: ACCEPTED

Test 26

Verdict: ACCEPTED

Test 27

Verdict: ACCEPTED

Test 28

Verdict: WRONG ANSWER

Test 29

Verdict: ACCEPTED

Test 30

Verdict: ACCEPTED