Submission #1274442

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274442		huhuhuhuhu	Mađioničar (COI22_madionicar)	C++20	0 / 100	1 ms	412 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL_TESTING
string test = "neven";
bool palin(long long l, long long r) {
  for (int i = 0; i < r - l + 1; i++) {
    // char lChar = (l + i)/10000;
    // char rChar = (r - i)/10000;
    char lChar = test[l + i], rChar = test[r - i];
    if (lChar != rChar) {
      return false;
    }
    if (l > r) {
      break;
    }
  }
  return true;
}

#else 

bool palin(long long l, long long r) {
  cout << "? " << l << " " << r << endl;
  cout << flush;
  long long ans = 0;
  cin >> ans;
  return ans;
}

#endif

long long pSize[200005];
long long n;
int main() {
  cin >> n;
  long long center = 0, right = -1;
  long long ans = 0;
  for (int i = 0; i < n*2+1; i++) {
    if (i > right) {
      center = i;
      right = i;
      long long r = i + 1;
      while (r < n * 2 + 1) {
        long long left = 2 * center - r;
        if (left < 0) {
          break;
        }
        if (r % 2 == 1 && !palin((2 * center - r)/2, r/2)) {
          break;
        }
        right = r;
        r++;
      }
      pSize[i] = right - center + 1;
    } else if (i <= right) {
      bool recalc = false;
      long long mirror = 2 * center - i;
      long long newBound;
      
      if (mirror < 0) {
        newBound = i;
        recalc = true;
      } else {
        newBound = i + pSize[mirror] - 1;
      }

      if (recalc || newBound >= right) {
        center = i;
        right = newBound;
        long long newRight = newBound + 1;
        while (newRight < 2 * n + 1) {
          long long left = 2 * center - newRight;
          if (left < 0) {
            break;
          }
          if (newRight % 2 == 1 && !palin(left/2, newRight/2)) {
            break;
          }
          right = newRight;
          newRight++;
        }
        // cout << center << " " << right << endl;
        pSize[i] = right - center + 1;
      } else {
        pSize[i] = pSize[mirror];
      }
      // cout << i << " ";
    }
    // cout << pSize[i] << " " << (i % 2 == 1 ? test[i/2] : '#') << endl;
    if (i%2 == 0) {
      ans = max(ans, 2 * (pSize[i]/2));
    } else {
      ans = max(ans, 2 * (pSize[i]/2) - 1);
    }
  }
  cout << "! " << ans << endl;
  cout << flush;
}

• Subtask 1: 0 / 13
• Subtask 2: 0 / 25
• Subtask 3: 0 / 25
• Subtask 4: 0 / 37