这是一个交互问题。
存在从 $$$1$$$ 到 $$$n$$$ 的数字的秘密排列 $$$p$$$($$$1$$$ 索引)。更正式地说,对于 $$$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]$$$。
在 $$$1$$$ 查询中,给出 $$$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$$$ 是要用于查询的 $$$3$$$ 索引。
数字必须满足 $$$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”并完成交互。您将收到错误答案判决。确保立即退出,以避免得到其他判决。
确定秘密排列后,输出“! p[1] p[2] ... p[n]”。如果秘密排列正确,交互器将打印“1”。否则,交互器将打印“-1”并完成交互。您将收到错误答案判决。确保立即退出,以避免得到其他判决。
打印查询后,不要忘记输出行尾并刷新输出。否则,您将得到超出空闲限制的判决。
为此,请使用:
- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 请参阅其他语言的文档。
黑客:
要破解,请使用以下测试格式:
第一行应包含一个整数 $$$t$$$ ($$$1 \leq t \leq 1000$$$) — 测试用例的数量。
每个测试用例的第一行应包含一个整数 $$$n$$$ ($$$20 \leq n \leq 100000$$$) — 秘密排列的长度。
以下行应包含 $$$n$$$ 整数 $$$p[1],p[2],p[3],\ldots,p[n]$$$。 $$$p[1]<p[2]$$$ 和 $$$p$$$ 必须是从 $$$1$$$ 到 $$$n$$$ 的整数排列。
您必须确保所有测试用例的 $$$n$$$ 总和不超过 $$$100000$$$。
示例
输入 #1
1 20 6 9 1
输出 #1
? 1 5 2 ? 20 19 2 ! 9 10 19 7 16 18 11 14 15 6 20 8 17 4 5 3 12 2 13 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$$$,这意味着我们已经正确猜测了秘密排列。