这是一道交互题
有一个长为 n 的排列 p,你需要在 ⌊23n⌋+30 次询问内找出排列 p 每一位所对应的数。
有两种操作
- t=1:max(min(x,pi),min(x+1,pj))
- t=2:min(max(x,pi),max(x+1,pj))
1≤t≤2,1≤i,j≤n(i=j),1≤x≤n−1
1≤T≤104,3≤n≤104,∑n≤2×104
T 组询问 每次询问开始时会给出 p 的长度 n。
若知道了 pi=1 的 i,那么可以通过 n 次询问来确定 p,每次询问 max(min(n−1,pi),min(n,pj)) 即可确定 pj。
现在问题转化成了用 ⌊2n⌋+30 次询问找到 pi=1 的 i。
若每次询问相邻两个位置 pi 和 pi+1,取得 res=min(max(1,pi),max(2,pi+1)),若 res=1 那么 pi=1,若 res=2 那么反过来问一次 min(max(1,pi+1),max(2,pi)) 即可。
询问次数最多 ⌊2n⌋+2。