CodeForces-2168B Locate 题解

Solution

最多询问303030次，恰好两次二分。

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

于是玩家 A 只需要传111和nnn的相对位置关系即可。

Code

#include<bits/stdc++.h>#definerept(i,a,b)for(inti(a);i<=b;++i)usingnamespacestd;intask(intl,intr){cout<<"? "<<l<<' '<<r<<endl;intres;cin>>res;returnres;}namespaceFirst{voidsolve(){intn,x,p1,pn;cin>>n;rept(i,1,n){cin>>x;if(x==1)p1=i;elseif(x==n)pn=i;}cout<<(pn>p1)<<endl;}}namespaceSecond{voidsolve(){intn,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;elsel=mid+1;}b=l;l=1,r=n;while(l<r){mid=l+r+1>>1;if(ask(mid,n)==n-1)l=mid;elser=mid-1;}a=l;if(x)cout<<"! "<<b<<endl;elsecout<<"! "<<a<<endl;}}signedmain(){string op;intT;cin>>op>>T;if(op=="first")while(T--)First::solve();elsewhile(T--)Second::solve();return0;}