CodeForces-2168B Locate 题解

张开发
• 2026/4/21 19:05:02 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

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#includebits/stdc.h#definerept(i,a,b)for(inti(a);ib;i)usingnamespacestd;intask(intl,intr){cout? l rendl;intres;cinres;returnres;}namespaceFirst{voidsolve(){intn,x,p1,pn;cinn;rept(i,1,n){cinx;if(x1)p1i;elseif(xn)pni;}cout(pnp1)endl;}}namespaceSecond{voidsolve(){intn,x,a,b,l,r,mid;cinnx;l1,rn;while(lr){midlr1;if(ask(1,mid)n-1)rmid;elselmid1;}bl;l1,rn;while(lr){midlr11;if(ask(mid,n)n-1)lmid;elsermid-1;}al;if(x)cout! bendl;elsecout! aendl;}}signedmain(){string op;intT;cinopT;if(opfirst)while(T--)First::solve();elsewhile(T--)Second::solve();return0;}

更多文章