CF1521C Nastia and a Hidden Permutation 做题记录

这是一道交互题

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

有两种操作

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

$1 \le t \le 2,1 \le i,j \le n(i \ne j),1 \le x \le n - 1$

$1 \le T \le 10^4,3 \le n \le 10^{4}, \sum n \le 2\times 10^4$

$T$ 组询问 每次询问开始时会给出 $p$ 的长度 $n$。
若知道了 $p_i=1$ 的 $i$，那么可以通过 $n$ 次询问来确定 $p$，每次询问 $\max(\min(n-1,p_i),\min(n,p_j))$ 即可确定 $p_j$。

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

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

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