CodeForces-2168B Locate 题解

Solution

最多询问 \(30\) 次，恰好两次二分。

注意到如果询问 \([l,r]\) 的返回值为 \(n-1\)，则 \(1\) 和 \(n\) 一定都在 \([l,r]\) 内。于是两次二分就可以确定 \(1,n\) 的位置，但不知道两个位置中哪个是 \(n\)。

于是玩家 A 只需要传 \(1\) 和 \(n\) 的相对位置关系即可。

Code

#include <bits/stdc++.h>
#define rept(i,a,b) for(int i(a);i<=b;++i)
using namespace std;
int ask(int l,int r){cout<<"? "<<l<<' '<<r<<endl;int res;cin>>res;return res;
}
namespace First{void solve(){int n,x,p1,pn;cin>>n;rept(i,1,n){cin>>x;if(x==1) p1=i;else if(x==n) pn=i;}cout<<(pn>p1)<<endl;}
}
namespace Second{void solve(){int n,x,a,b,l,r,mid;cin>>n>>x;l=1,r=n;while(l<r){mid=l+r>>1;if(ask(1,mid)==n-1) r=mid;else l=mid+1;}b=l;l=1,r=n;while(l<r){mid=l+r+1>>1;if(ask(mid,n)==n-1) l=mid;else r=mid-1;}a=l;if(x) cout<<"! "<<b<<endl;else cout<<"! "<<a<<endl;}
}
signed main(){string op;int T;cin>>op>>T;if(op=="first") while(T--) First::solve();else while(T--) Second::solve();return 0;
}