CF1583D Omkar and the Meaning of Life 做题记录

这是一道交互题。

原来生命的意义是一个 $n$ ($2 \leq n \leq 100$) 的排列。 创造了世上所有生命的 Omkar 知道这个排列，他允许你在有限的询问次数内查询出这个排列是什么。

每一次询问你可以给出一个序列 $a_1, a_2, \ldots, a_n$ ($1\le a_1,a_2,\ldots,a_n \le n$) 来对 Omkar 进行询问。 $ a $ 序列不一定要是一个排列。之后 Omkar 会逐个将 $a_i$ 与 $p_i$ 相加得到一个新的序列 $s$ ，即对于每个 $j$ ($1\le j \le n$) ，$s_j = p_j + a_j$ 。最后 $s$ 序列中可能会出现一些相同的数，你将读入 Omkar 告诉你的第一个出现相同数的位置。如果没有相同的数出现，你将读入数字 $0$ 。

你最多只能进行 $2n$ 次询问。

显然对于 $a_i=a_j$ 的两个位置 $i,j$，它们一定对答案没有贡献，那么考虑询问形如 $\{2,2,\dots,2,1,2,2\dots,2\}$ 的第 $i$ 位为 $1$，其它位为 $2$ 的序列 $a$。

记询问只有第 $i$ 位为 $1$ 的 $a$ 的答案为 $res1_i$，那么 $res1_i$ 显然有三种情况：

• $res1_i<i$，那么 $p_i$ 的前驱是 $p_{res1_i}$；
• $res1_i=i$，那么 $p_i$ 的前驱在 $[i+1,n]$ 中；
• $res1_i=0$，那么 $p_i=1$；

接下来考虑获取每个位置的后继以解决 $p_i$ 的前驱不确定的情况。类似的，考虑询问形如 $\{1,1,\dots,1,2,1,1\dots,1\}$ 的第 $i$ 位为 $2$，其它位为 $1$ 的序列 $a$。

记询问只有第 $i$ 位为 $1$ 的 $a$ 的答案为 $res2_i$，那么 $res2_i$ 显然也有三种情况：

• $res2_i<i$，那么 $p_i$ 的后继是 $p_{res2_i}$；
• $res2_i=i$，那么 $p_i$ 的后继在 $[i+1,n]$ 中；
• $res2_i=0$，那么 $p_i=1$；

这样我们就用 $2n$ 次操作确定了每个 $p_i$ 的前驱后继，自然也确定了 $p$。