#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define int long long
int n;
bool ask(int i, int sz){
if(i<1 || i+sz-1>n) return false;
int resp;
cout << "? " << i << ' ' << i+sz-1 << '\n' << flush;
if(!(cin >> resp)) exit(0);
return resp==1;
}
void sol(){
cin >> n;
//even sized palindromes
int ans=1;
bool found=0;
int sz=2;
do{
found=0;
for(int i=1;i<=n-sz+1;i++){
if(ask(i,sz)){
found=1;
ans=max(ans,sz);
while(1<=i-1 && sz+2<=n && i+sz<=n){ //expand palin
i--; sz+=2;
if(ask(i,sz))ans=max(ans,sz);
else break;
}
}
}
sz+=2;
}while(found && sz<=n);
//odd sized palindromes
sz=3;
do{
found=0;
for(int i=1;i<=n-sz+1;i++){
if(ask(i,sz)){
found=1;
ans=max(ans,sz);
while(1<=i-1 && sz+2<=n && i+sz<=n){ //expand palin
i--; sz+=2;
if(ask(i,sz)) ans=max(ans,sz);
else break;
}
}
}
sz+=2;
}while(found && sz<=n);
cout << "! " << ans << '\n' << flush;
return;
}
signed main(){
int tc=1;
// cin >> tc;
while(tc--) sol();
return 0;
}
# | 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... |