#define CF_SUBWAY_SURFER
#include<time.h>
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
int h(int i,int j){return i>j?i:j;}
int h_(int i,int j){return -h(-i,-j);}
int a_,past_ask[66],b_;
int asked(long long c){for(int j=0;j<b_;++j)if(past_ask[j]==c)return 1;return 0;}
int ask(long long c){for(int j=0;j<b_;++j)if(past_ask[j]==c)return -1;past_ask[b_++]=c;printf("? %lld\n",c);fflush(stdout);scanf("%d",&a_);return a_;}
#define report(x) do{printf("= %lld\n",(long long)(x));fflush(stdout);goto X;}while(0)
int main(){
srand(8686868);
int t;
#ifndef CF_SUBWAY_SURFER
t=1;
#else
scanf("%d",&t);
#endif
while(t--){
b_=0;
long long n;
scanf("%lld",&n);
if(n==1)report(1);
if(n<=64){
ask(1);
if(!ask(n))report(n);
for(int r=n-1,l=2,d=n-1,i=1,cc=0;cc<n-2;++i,--d,++cc)if((i%2&&!ask(l++)) || (i%2==0&&!ask(r--)))report(d);
report(1);
}
if(n<=125){
int m = n / 2 + 1;
ask(m);
int mid = ask(1);
if (!ask(n))report(n);
if(mid){
for(int r=m-1,l=2,d=m-1,i=1,cc=0;d>1;++i,--d,++cc)
if(i%2&&!ask(l++))report(d);
else if(i%2==0&&!ask(r--))report(d);
report(1);
}else{
for(int r=n-1,l=2,d=n-1,i=1,cc=0;d>1;++i,--d,++cc){
if(i%2){
if(l==m)report(1);
if(!ask(l++))report(d);
}
else{
if(r==m)report(1);
else if(!ask(r--)) report(d);
}
}
report(1);
}
}
if(n<=1000){
int S=34,m=n/2+1;
ask(m);
if (ask(m+1))report(1);
ask(m);
int ll=m,rr=m;
for(int ii=1;;ii^=1){
if(ii){
ll=h(ll-S,1);
if(ask(ll)){
for(int r=rr-1,l=ll+1,d=rr-ll,i=0;d>1;++i,--d)
if(i%2){ if(!ask(l++))report(d); }
else{ if(!ask(r--))report(d); }
report(rr-ll);
}
}else{
rr=h_(rr+S,n);
if(ask(rr)){
for(int r=rr-1,l=ll+1,d=rr-ll,i=1;d>1;++i,--d)
if(i%2){ if(!ask(l++))report(d); }
else{ if(!ask(r--))report(d); }
report(rr-ll);
}
}
if (ll==1&&rr==n)
report(n);
}
report(n);
}
else if(n<=1e9){
ask(1);
int lb=0,ub=n;
while(ub-lb>1){
int md=lb+(ub-lb)/2;
int v=1,xx,yy;
while(asked(v)||asked(v+md)||v+md>n)
v=rand()*1ll*rand()%n+1;
ask(v);
yy=ask(v+md);
if(yy)ub=md;
else lb=md;
}
report(ub);
}
X:;
}
}
Compilation message
Colors.c: In function 'main':
Colors.c:89:25: warning: unused variable 'xx' [-Wunused-variable]
89 | int v=1,xx,yy;
| ^~
Colors.c: In function 'ask':
Colors.c:10:124: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
10 | int ask(long long c){for(int j=0;j<b_;++j)if(past_ask[j]==c)return -1;past_ask[b_++]=c;printf("? %lld\n",c);fflush(stdout);scanf("%d",&a_);return a_;}
| ^~~~~~~~~~~~~~~
Colors.c: In function 'main':
Colors.c:18:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
18 | scanf("%d",&t);
| ^~~~~~~~~~~~~~
Colors.c:23:9: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
23 | scanf("%lld",&n);
| ^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
0 ms |
344 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
0 ms |
344 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
0 ms |
344 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
0 ms |
344 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
0 ms |
344 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
