CF 1407C

题目内容

交互题。

给定一个隐藏的长为 $n$ 的排列 $P$ ，要求进行不超过 $2 n$ 次询问猜出这个排列。每次询问可以给出一个 $(i, j)$ 对，并获得 $P_{i} mod P_{j}$ 的结果。

解法

提示

$a mod b > b mod a$ 当且仅当 $a < b$ 。

解答

知道提示中的这条性质后这题就纯一眼了。考虑每次选出两个仍然未知的元素 $P_{i}$ 与 $P_{j}$ 作两次询问。不妨设 $P_{i} mod P_{i + 1} > P_{i + 1} mod P_{i}$ ，则依据性质可知 $P_{i} < P_{i + 1}$ ，则 $P_{i} mod P_{i + 1} = P_{i}$ ，因此我们能恰好使用 $2 (n - 1)$ 次询问求出答案。

AC 代码

见提交记录。