CF1521C Nastia and a Hidden Permutation 做题记录

这是一道交互题

有一个长为 nn 的排列 pp,你需要在 3n2+30\lfloor\frac{3n}{2}\rfloor + 30 次询问内找出排列 pp 每一位所对应的数。

有两种操作

  • t=1:max(min(x,pi),min(x+1,pj))t = 1 : max(min(x, p_i), min(x + 1, p_j))
  • t=2:min(max(x,pi),max(x+1,pj))t = 2 : min(max(x, p_i), max(x +1, p_j))

1t2,1i,jn(ij),1xn11 \le t \le 2,1 \le i,j \le n(i \ne j),1 \le x \le n - 1

1T104,3n104,n2×1041 \le T \le 10^4,3 \le n \le 10^{4}, \sum n \le 2\times 10^4

TT 组询问 每次询问开始时会给出 pp 的长度 nn
若知道了 pi=1p_i=1ii,那么可以通过 nn 次询问来确定 pp,每次询问 max(min(n1,pi),min(n,pj))\max(\min(n-1,p_i),\min(n,p_j)) 即可确定 pjp_j

现在问题转化成了用 n2+30\left\lfloor\frac{n}{2}\right\rfloor+30 次询问找到 pi=1p_i=1ii

若每次询问相邻两个位置 pip_ipi+1p_{i+1},取得 res=min(max(1,pi),max(2,pi+1))res=\min(\max(1,p_i),\max(2,p_{i+1})),若 res=1res=1 那么 pi=1p_i=1,若 res=2res=2 那么反过来问一次 min(max(1,pi+1),max(2,pi))\min(\max(1,p_{i+1}),\max(2,p_{i})) 即可。

询问次数最多 n2+2\left\lfloor\frac{n}{2}\right\rfloor+2