Solution
交互库自适应，也就是它会尽量使你的代码进行尽量多的交互，从而卡掉一些诸如随机化的做法。
显然我们需要通过询问不断缩小查找范围。假设当前已经确定 \(q\in [1,n]\)，如果询问 \((l,r)\)，那么交互库返回“比 \(l\) 大”或“比 \(r\) 小”就可以使下一轮区间长度为 \(\max(r-1,n-l)\)，取到最大值。
于是有性质：询问的区间必须满足 \(r-1=n-l\)。否则可以拓展小的一边使 \(\max(r-1,n-l)\) 不变而区间长度增加，得到更优解。
\(1.9813035\) 这样的奇怪限制启发我们考虑 dp。设 \(f_i\) 为长度为 \(i\) 的区间确定唯一值的最小代价。若一次询问后区间长度缩减到 \(j\)，则 \(l=i-j-1,r=j+1\)。于是转移方程为：
\[f_i=\min_{\left\lceil\frac{i-1}{2}\right\rceil\le j<i}f_j+\frac{1}{2j-i+2}
\]
直接跑 dp 是 \(O(n^2)\) 的，期望得分 \(70\)。
我们可以证明代价函数满足四边形不等式。因此 dp 具有决策单调性，二分队列算法可以在 \(O(n\log n)\) 复杂度内解决本题。
Code
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i(a);i<b;++i)
#define rept(i,a,b) for(int i(a);i<=b;++i)
#define db double
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
namespace{constexpr int N=1e5+5;deque<int> q;int n,l[N],r[N],g[N];db f[N];
}
inline const pii ask(int l,int r){cout<<"? "<<l<<' '<<r<<endl;pii res;cin>>res.fi>>res.se;return res;
}
inline void submit(int x){cout<<"! "<<x<<endl;exit(0);
}
inline db w(int j,int i){return f[j]+1.0/(2*j-i+2);
}
inline int rb(int i){ // i能更新到的最右边界return min(n,i<<1|1);
}
inline bool check(int i,int j){ // i是否能更新jreturn i<j&&rb(i)>=j;
}
int main(){cin>>n;if(n==1) submit(1);l[1]=2,r[1]=rb(1);q.push_back(1);rept(i,2,n){while(!q.empty()&&r[q.front()]<i) q.pop_front();g[i]=q.front();f[i]=w(g[i],i);while(!q.empty()&&check(i,l[q.back()])&&w(i,l[q.back()])<w(q.back(),l[q.back()])) q.pop_back();if(q.empty()){l[i]=i+1,r[i]=rb(i);q.emplace_back(i);}else if(!check(i,r[q.back()])||w(i,r[q.back()])>=w(q.back(),r[q.back()])){if(r[q.back()]<rb(i)){l[i]=r[q.back()]+1,r[i]=rb(i);q.emplace_back(i);}}else{int L=l[q.back()],R=r[q.back()],mid;while(L<R){mid=L+R>>1;if(check(i,mid)&&w(i,mid)<w(q.back(),mid)) R=mid;else L=mid+1;}r[q.back()]=L-1;l[i]=L,r[i]=rb(i);q.emplace_back(i);}}int L=1,R=n;while(true){if(L==R) submit(L);int t=R-L+1-1-g[R-L+1];pii res=ask(L+t,R-t);if(res.se==1) submit(res.fi);if(res.se==0) L=res.fi+1;else R=res.fi-1;}return 0;
}