CF1526F Median Queries

这是一个交互题。 有一个长度为 $n$ 的秘密排列 $p$（下标从 $1$ 开始），它是 $1$ 到 $n$ 的一个排列。更正式地说，对于 $1 \leq i \leq n$，有 $1 \leq p[i] \leq n$，且对于 $1 \leq i < j \leq n$，$p[i] \neq p[j]$。已知 $p[1] < p[2]$。 每次询问，你可以给出 $3$ 个互不相同的整数 $a, b, c$（$1 \leq a, b, c \leq n$），你将会收到 $\{|p[a]-p[b]|,|p[b]-p[c]|,|p[a]-p[c]|\}$ 的中位数。 这里的中位数指的是将序列按非递减顺序排列后的第 $2$ 个（下标从 $1$ 开始）元素。例如，$\{4,6,2\}$ 的中位数是 $4$，$\{0,123,33\}$ 的中位数是 $33$。 你能否在不超过 $2n+420$ 次询问内找出这个秘密排列？ 注意：评测器是非自适应的：排列在所有询问前就已经固定。

输入的第一行包含一个整数 $t$（$1 \leq t \leq 1000$），表示测试用例的数量。 每个测试用例的第一行包含一个整数 $n$（$20 \leq n \leq 100000$），表示秘密排列的长度。 保证所有测试用例中 $n$ 的总和不超过 $100000$。

对于每个测试用例，你首先读入 $n$。 每次询问时，输出一行 "? a b c"，其中 $a, b, c$ 是你想要查询的三个下标。 要求 $1 \leq a, b, c \leq n$ 且 $a \neq b$，$b \neq c$，$a \neq c$。 对于每次询问，你会收到一个整数 $x$，表示 $\{|p[a]-p[b]|,|p[b]-p[c]|,|p[a]-p[c]|\}$ 的中位数。 如果你的询问不合法，或者你询问次数超过 $2n+420$，评测器会输出 "-1" 并终止交互。你将收到 Wrong answer 判定。请确保立即退出以避免获得其它判定。 当你确定了秘密排列后，输出一行 "! p[1] p[2] ... p[n]"。如果排列正确，评测器会输出 "1"。否则，评测器会输出 "-1" 并终止交互。你将收到 Wrong answer 判定。请确保立即退出以避免获得其它判定。 每次输出后不要忘记换行并刷新输出缓冲区，否则会收到 Idleness limit exceeded 判定。 刷新输出缓冲区的方法： - C++：fflush(stdout) 或 cout.flush() - Java：System.out.flush() - Pascal：flush(output) - Python：stdout.flush() - 其它语言请查阅相关文档。 Hack 格式： Hack 时，输入格式如下： 第一行包含一个整数 $t$（$1 \leq t \leq 1000$），表示测试用例数量。 每个测试用例的第一行包含一个整数 $n$（$20 \leq n \leq 100000$），表示秘密排列长度。 接下来一行包含 $n$ 个整数 $p[1],p[2],p[3],\ldots,p[n]$，满足 $p[1]

秘密排列为 $\{9,10,19,7,16,18,11,14,15,6,20,8,17,4,5,3,12,2,13,1\}$。 第一次询问，$(a,b,c) = (1,5,2)$。由于 $p[1]=9$，$p[5]=16$，$p[2]=10$，返回值为 $\{|9-16|,|16-10|,|9-10|\}$ 的中位数，即 $6$。 第二次询问，$(a,b,c) = (20,19,2)$。由于 $p[20]=1$，$p[19]=13$，$p[2]=10$，返回值为 $\{|1-13|,|13-10|,|1-10|\}$ 的中位数，即 $9$。 通过某种方式，我们得到了秘密排列 $\{9,10,19,7,16,18,11,14,15,6,20,8,17,4,5,3,12,2,13,1\}$。我们输出它，评测器返回 $1$，表示我们猜对了。 由 ChatGPT 4.1 翻译