这是一个交互问题。
陪审团有一个长度为 $$$n$$$ 的排列 $$$p$$$,并希望你猜出它。为此,陪审团创建了另一个长度为 $$$n$$$ 的排列 $$$q$$$。最初,$$$q$$$ 是一个恒等排列(对于所有$$$i$$$,$$$q_i = i$$$)。
您可以提出查询来获取您想要的任何 $$$i$$$ 的 $$$q_i$$$。每次询问后,陪审团将按以下方式更改$$$q$$$:
- 首先,评审团将创建一个长度为 $$$n$$$ 的新排列 $$$q'$$$,使得所有 $$$i$$$ 的 $$$q'_i = q_{p_i}$$$。
- 然后陪审团将用排列 $$$q'$$$ 替换排列 $$$q$$$。
为了查询 $$$p$$$,您最多可以进行 $$$2n$$$ 查询。
输入
输入的第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 1000$$$) — 测试用例的数量。
互动
每个测试用例中的交互在读取单个整数 $$$n$$$ ($$$1 \leq n \leq 10^4$$$) 后开始 - 排列 $$$p$$$ 和 $$$q$$$ 的长度。
要获取 $$$q_i$$$ 的值,请以 $$$?$$$ $$$i$$$ ($$$1 \leq i \leq n$$$) 格式输出查询。之后您将收到 $$$q_i$$$ 的值。
您最多可以进行 $$$2n$$$ 查询。错误查询后,您将收到 $$$0$$$,您应该立即退出以获得错误答案判决。
当您准备好确定 $$$p$$$ 时,以 $$$!$$$ $$$p_1$$$ $$$p_2$$$ $$$\ldots$$$ $$$p_n$$$ 格式输出 $$$p$$$。之后,您应该转到下一个测试用例,或者如果是最后一个测试用例则退出。打印排列不计为 $$$2n$$$ 查询之一。
打印查询后,不要忘记输出行尾并刷新输出。否则,您将超出空闲限制。为此,请使用:
- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 请参阅其他语言的文档。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^4$$$。交互器在这个问题上不具有适应性。
黑客:
要破解,请使用以下格式:
第一行包含单个整数 $$$t$$$ — 测试用例的数量。
每个测试用例的第一行包含单个整数 $$$n$$$ — 排列 $$$p$$$ 和 $$$q$$$ 的长度。每个测试用例的第二行包含 $$$n$$$ 整数 $$$p_1, p_2, \ldots, p_n$$$ - 此测试用例的隐藏排列。
示例
输入 #1
2 4 3 2 1 4 2 4 4
输出 #1
? 3 ? 2 ? 4 ! 4 2 1 3 ? 2 ? 3 ? 2 ! 1 3 4 2
注意
在第一个测试用例中,隐藏排列 $$$p = [4, 2, 1, 3]$$$。
在第一个查询 $$$q = [1, 2, 3, 4]$$$ 之前,因此查询的答案将是 $$$q_3 = 3$$$。
在第二个查询 $$$q = [4, 2, 1, 3]$$$ 之前,因此查询的答案将是 $$$q_2 = 2$$$。
在第三个查询 $$$q = [3, 2, 4, 1]$$$ 之前,因此查询的答案将是 $$$q_4 = 1$$$。
在第二个测试用例中,隐藏排列 $$$p = [1, 3, 4, 2]$$$。
给出空字符串只是为了更好的可读性。测试系统中不会有空行。