#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<cassert>
#include<unordered_map>
#include <queue>
#include <cstdint>
#include<cstring>
#include<limits.h>
#include<cmath>
#include<set>
#include<algorithm>
#include <iomanip>
#include<numeric>
#include<bitset>
using namespace std;
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-lopps")
#define int long long
using namespace std;
const int mod=998244353,mxn=2e5+5,inf=1e18,minf=-1e18,lg=25;
int n,m,k,x,q,t;
map<int,int>here;
int current=-1,C=0,cnt=0;
int ans=inf,atleast=0;
int test(int x){
if(current==-1)return 0;
if(abs(current-x)>=C)return 1;
return 0;
}
int ask(int x){
cnt++;
cout<<"? "<<x<<endl;
cout.flush();
here[x]=1;
int a;
cin>>a;
//a=test(x);
if(current!=-1){
if(a)ans=min(ans,abs(current-x));
else atleast=max(atleast,abs(current-x));
}
current=x;
return a;
}
void answer(int x){
cout<<"= "<<x<<endl;
cout.flush();
return;
}
int mid(int l,int r){return l+(r-l)/2;}
int cur=0;
void solve(){
cin>>n;
here.clear();
current=-1;
ans=inf,atleast=0;
int l1=1,r1=mid(1,n),l2=r1+1,r2=n;
bool huh=1,side=1;
while(r1-l1>1&&r2-l2>1){
if(abs((r1-l1)-(r2-l2))>1)assert(0);
int mid1=mid(l1,r1),mid2=mid(l2,r2);
int x;
if(r1-l1>r2-l2){
ask(mid1);
x=ask(mid2);
side=1;
}
else{
ask(mid2);
x=ask(mid1);
side=0;
}
if(x)l1=mid1+1,r2=mid2-1,huh=1;
else r1=mid1-1,l2=mid2+1,huh=0;
}
vector<int>v;
for(int j=l1;j<=r1;j++)v.pb(j);
for(int j=l2;j<=r2;j++)v.pb(j);
//cout<<l1<<" "<<r1<<" "<<l2<<" "<<r2<<" "<<current<<" "<<huh<<' '<<side<<"LL\n";
for(int i=0;i<10;i++){
int furthest=-1;
int closest=-1;
if(huh){
for(auto j:v)if(!here[j]&&(furthest==-1||abs(current-j)>abs(current-furthest)))furthest=j;
}
if(!huh){
if(side){
for(int j=r1;j>=l1;j--)if(!here[j]){
closest=j;
break;
}
}
else{
for(int j=l2;j<=r2;j++)if(!here[j]){
closest=j;
break;
}
}
side^=1;
}
if(furthest==-1&&closest==-1)break;
if(furthest!=-1)ask(furthest);
else ask(closest);
}
int check=1;
if(ans==inf)return void(answer(n));
if(ans-atleast>2)assert(0);
if(ans-atleast==1)return void(answer(ans));
if(current-ans+1>=1&&!here[current-ans+1])ask(current-ans+1);
else if(current+ans-1<=n&&!here[current+ans-1])ask(current+ans-1);
else{
while(check+ans-1<=n){
if(here[check]==0&&here[check+ans-1]==0){
ask(check);
ask(check+ans-1);
break;
}
check++;
}
}
answer(ans);
}
int32_t main(){
fastio
cin>>t;
while(t--)solve();
}
/*
<=1000->sqrt decomp
keep range l1,r1 and l2,r2
we can then qry mid=mid(l1,r1) to mid2=mid(l2,r2)
then move to (mid+1,r1) and (l2,mid2-1)
or (l1,mid-1) and (mid2+1,r2)
until length if range1 or 2 ==1
abs(length1-length2) should always be <=1
problems->this will skip some range
skip odd/even range
*/
Compilation message
Colors.cpp:32:40: warning: bad option '-funroll-lopps' to pragma 'optimize' [-Wpragmas]
32 | #pragma GCC optimize ("03,unroll-lopps")
| ^
Colors.cpp:40:15: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
40 | int test(int x){
| ^
Colors.cpp:45:14: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
45 | int ask(int x){
| ^
Colors.cpp:60:18: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
60 | void answer(int x){
| ^
Colors.cpp:65:20: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
65 | int mid(int l,int r){return l+(r-l)/2;}
| ^
Colors.cpp:67:12: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
67 | void solve(){
| ^
Colors.cpp:138:14: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
138 | int32_t main(){
| ^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
0 ms |
344 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
0 ms |
344 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
0 ms |
344 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
0 ms |
344 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
0 ms |
344 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
