#include <bits/stdc++.h>
using namespace std;
bool palindrome(long long l, long long r) {
cout << "? " << l+1 << " " << r+1 << endl;
cout << flush;
long long ans = 0;
cin >> ans;
return ans == 1;
}
long long n, ans = 0;
long long len[200005];
int main() {
cin >> n;
long long center = 0, right = -1;
for (int i = 0; i < n * 2 + 1; i++) {
if (i > right) {
// cout << "Out of bounds i" << endl;
center = i;
right = i;
long long newRight = i + 1;
while (newRight < n * 2 + 1) {
long long left = center * 2 - newRight;
if (left < 0) {
break;
}
if (newRight % 2 == 1 && !palindrome(left/2, newRight/2)) {
break;
}
right = newRight;
newRight++;
}
// cout << "hi " << center << " " << right << endl;
len[i] = right - center;
} else if (i <= right) {
long long mirror = center * 2 - i;
if (mirror < 0) {
// cout << "Mirror" << endl;
center = i;
right = i;
long long newRight = right + 1;
while (newRight < 2 * n + 1) {
long long left = 2 * center - newRight;
if (left < 0) {
break;
}
if (newRight % 2 == 1 && !palindrome(left/2, newRight/2)) {
break;
}
right = newRight;
newRight++;
}
len[i] = right - center;
continue;
}
long long rightBounds = i + len[mirror];
if (rightBounds < right) {
len[i] = len[mirror];
} else {
center = i;
right = i;
long long newRight = right + 1;
while (newRight < n * 2 + 1) {
long long left = 2 * center - newRight;
if (left < 0) {
break;
}
// cout << "Expand " << newRight << endl;
if (newRight % 2 == 1 && !palindrome(left/2, newRight/2)) {
break;
}
right = newRight;
newRight++;
}
// cout << "ok expand" << endl;
len[i] = right - center;
}
}
if (i % 2 == 0) {
ans = max(ans,len[i]);
} else {
ans = max(ans,len[i]);
}
}
cout << "! " << ans << endl;
cout << flush;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |