← 返回题目列表

Codeforces · 1621/C

C. 隐藏排列

中文机器翻译题面 查看原题

这是一个交互问题。

陪审团有一个长度为 $$$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]$$$。

给出空字符串只是为了更好的可读性。测试系统中不会有空行。