#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define ff first
#define ss second
using namespace std;
const int inf = 1e18;
const int maxv = 1e9;
pii intersect(pii a, pii b)
{
if (a.ff > b.ff)
swap(a, b);
if (a.ss >= b.ss)
return b;
return {b.ff, a.ss};
}
int _now = 0;
int c;
int fin = 0;
/*
int grader(int x)
{
bool g = (abs(_now-x)>=c);
_now = x;
fin++;
return g;
}*/
int grader(int x)
{
cout << "? " << x << endl;
cin >> x;
return x;
}
void solve()
{
int n;
cin >> n;
if(n==2){
grader(1);
if(grader(2))
{
cout << "= 1" << endl;
}
else
cout << "= 2" << endl;
return;
}
//cin >> c;
pii seg = {1, n};
map<int, int> kor;
auto relax = [&](pii x)
{
seg = intersect(seg, x);
};
int now = 0;
int qs = 0;
auto query = [&](int l, int r)
{
kor[l]=1,kor[r]=1;
int a;
a = grader(l);
if (qs)
{
if (a)
relax({1, abs(l-now)});
else
relax({abs(l-now) + 1, n});
}
now = l;
a = grader(r);
qs++;
if (a)
relax({1, abs(r - l)});
else
relax({abs(r - l) + 1, n});
now = r;
};
while(seg.ss-seg.ff > 1)
{
int l = seg.ff,r = seg.ss;
int mid = l+r>>1;
if(((mid%2)^(n%2)) == 0)
{
int a = max(abs(mid-l),abs(r-mid+1));
int b= max(abs(r-mid-1),abs(mid+2-l));
if (a < b)
mid--;
else
mid++;
}
query((n+1)/2-(mid+1)/2 +(n%2==0),(n+1)/2+(mid+1)/2);
}
if(seg.ss==seg.ff)
{
cout << "= " << seg.ff << endl;
}
else
{
if ((now-seg.ff > 0 && !kor[now-seg.ff]))
{
if (grader(now-seg.ff))
cout << "= " << seg.ff << endl;
else
cout << "= " << seg.ss << endl;
cerr << fin << endl;
return;
}
if ((now+seg.ff <= n && !kor[now+seg.ff]))
{
if (grader(now+seg.ff))
cout << "= " << seg.ff << endl;
else
cout << "= " << seg.ss << endl;
cerr << fin << endl;
return;
}
for (int i = 1; i+seg.ff <= n; i++)
if (!kor[i] && !kor[i+seg.ff])
{
query(i,i+seg.ff);
cout << "= " << seg.ff << endl;
break;
}
}
cerr << fin << endl;
fin = 0;
_now = 0;
}
signed main()
{
/*ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
*/int t = 1;
//cin >> t;
while(t--)
solve();
}
# | 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... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |