← 返回题目列表

Codeforces · 1896/G

G. 佩佩赛车

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

这是一个交互问题。

有 $$$n^2$$$ 辣椒,标记为 $$$1, 2, \ldots, n^2$$$,且速度成对不同。您想举办一些比赛来找出这些佩佩的相对速度。

在一场比赛中,您可以准确选择 $$$n$$$ 不同的佩佩并让他们相互比赛。每场比赛结束后,您只会知道这些 $$$n$$$ 佩佩中最快的佩佩。

您可以在最多 $$$2n^2 - 2n + 1$$$ 比赛中订购 $$$n^2-n+1$$$ 最快的佩佩吗?请注意,最慢的 $$$n - 1$$$ pepe 彼此无法区分。

请注意,交互器是自适应的。也就是说,pepes 的相对速度一开始并不是固定的,可能取决于您的查询。但可以保证在任何时刻至少有一个 pepes 的初始配置,以便所有查询的答案都是一致的。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的唯一行包含一个整数 $$$n$$$ ($$$2 \le n \le 20$$$) — 一场比赛中佩佩的数量。

读取每个测试用例的整数 $$$n$$$ 后,您应该开始交互。

保证所有测试用例的 $$$n^3$$$ 总和不超过 $$$3 \cdot 10^5$$$。

互动

要设置比赛,请使用以下格式打印一行:

- $$$\mathtt{?}\,x_1\,x_2 \ldots x_n$$$ ($$$1 \le x_i \le n^2$$$, $$$x_i$$$ 成对不同) — 比赛中佩佩的标签。

每次比赛结束后,您应该读取一行,其中包含单个整数 $$$p$$$ ($$$1\le p\le n^2$$$) — 比赛中最快的 pepe 的标签。

当您知道 $$$n^2-n+1$$$ 最快的 pepes 时,请按以下格式打印一行:

- $$$\mathtt{!}\,p_1\,p_2 \ldots p_{n^2 - n + 1}$$$ ($$$1 \le p_i \le n^2$$$, $$$p_i$$$ 成对不同)

之后,继续进行下一个测试用例,或者如果没有剩余的测试用例则终止程序。

如果您的程序对一个测试用例执行超过 $$$2n^2 - 2n + 1$$$ 竞赛或进行无效竞赛,您可能会收到错误答案判决。

打印查询后,不要忘记输出行尾并刷新输出。否则,您将超出空闲限制。为此,请使用:

- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 请参阅其他语言的文档。

黑客格式

对于 hack,请使用以下格式。

第一行应包含 $$$t$$$ — 测试用例的数量。

每个测试用例的第一行应包含一个整数 $$$n$$$ 后跟字符串手册。

每个测试用例的第二行应包含从 $$$1$$$ 到 $$$n^2$$$ 的整数的排列 $$$a_1,a_2,\ldots,a_{n^2}$$$。 $$$a_i > a_j$$$ 当且仅当 pepe $$$i$$$ 的速度比 pepe $$$j$$$ 更快。

例如,示例输入的 hack 格式为: $$$\mathtt{1}\\\mathtt{2}~\mathtt{manual}\\\mathtt{1}~\mathtt{2}~\mathtt{3}~\mathtt{4}$$$

示例

输入 #1

1
2

2

4

4

3

2

输出 #1

? 1 2

? 3 4

? 2 4

? 2 3

? 2 1

! 4 3 2