310838: CF1896G. Pepe Racing
Description
This is an interactive problem.
There are $n^2$ pepes labeled $1, 2, \ldots, n^2$ with pairwise distinct speeds. You would like to set up some races to find out the relative speed of these pepes.
In one race, you can choose exactly $n$ distinct pepes and make them race against each other. After each race, you will only know the fastest pepe of these $n$ pepes.
Can you order the $n^2-n+1$ fastest pepes in at most $2n^2 - 2n + 1$ races? Note that the slowest $n - 1$ pepes are indistinguishable from each other.
Note that the interactor is adaptive. That is, the relative speeds of the pepes are not fixed in the beginning and may depend on your queries. But it is guaranteed that at any moment there is at least one initial configuration of pepes such that all the answers to the queries are consistent.
InputEach test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.
The only line of each test case contains a single integer $n$ ($2 \le n \le 20$) — the number of pepes in one race.
After reading the integer $n$ for each test case, you should begin the interaction.
It is guaranteed that the sum of $n^3$ over all test cases does not exceed $3 \cdot 10^5$.
InteractionTo set up a race, print a line with the following format:
- $\mathtt{?}\,x_1\,x_2 \ldots x_n$ ($1 \le x_i \le n^2$, $x_i$ are pairwise distinct) — the labels of the pepes in the race.
After each race, you should read a line containing a single integer $p$ ($1\le p\le n^2$) — the label of the fastest pepe in the race.
When you know the $n^2-n+1$ fastest pepes, print one line in the following format:
- $\mathtt{!}\,p_1\,p_2 \ldots p_{n^2 - n + 1}$ ($1 \le p_i \le n^2$, $p_i$ are pairwise distinct)
After that, move on to the next test case, or terminate the program if no more test cases are remaining.
If your program performs more than $2n^2 - 2n + 1$ races for one test case or makes an invalid race, you may receive a Wrong Answer verdict.
After printing a query do not forget to output the end of the line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:
- fflush(stdout) or cout.flush() in C++;
- System.out.flush() in Java;
- flush(output) in Pascal;
- stdout.flush() in Python;
- see the documentation for other languages.
Hack format
For hacks, use the following format.
The first line should contain $t$ — the number of test cases.
The first line of each test case should contain an integer $n$ followed by the string manual.
The second line of each test case should contain a permutation $a_1,a_2,\ldots,a_{n^2}$ of the integers from $1$ to $n^2$. $a_i > a_j$ if and only if pepe $i$ has a faster speed than pepe $j$.
As an example, the hack format for the example input is: $\mathtt{1}\\\mathtt{2}~\mathtt{manual}\\\mathtt{1}~\mathtt{2}~\mathtt{3}~\mathtt{4}$
ExampleInput1 2 2 4 4 3 2Output
? 1 2 ? 3 4 ? 2 4 ? 2 3 ? 2 1 ! 4 3 2
Output
这是一个交互式问题。有n^2个标号为1, 2, ..., n^2的pepes，它们的速度两两不同。你需要通过安排一些比赛来确定这些pepes的相对速度。
在一场比赛中，你可以精确地选择n个不同的pepes让它们相互比赛。每场比赛后，你只能知道这n个pepes中最快的那个。
你能否在最多2n^2 - 2n + 1场比赛中确定n^2-n+1个最快的pepes的顺序？注意，最慢的n-1个pepes之间是不可区分的。
注意，这个交互器是自适应的。也就是说，pepes的相对速度在一开始并不是固定的，可能会依赖于你的查询。但是保证在任何时刻都至少存在一种pepes的初始配置，使得对所有查询的回答都是一致的。
输入输出数据格式：
每个测试包含多个测试用例。第一行包含测试用例的数量t (1 ≤ t ≤ 10^4)。接下来是每个测试用例的描述。
每个测试用例只有一行，包含一个整数n (2 ≤ n ≤ 20)，表示一场比赛中的pepes数量。在读取每个测试用例的整数n后，你应该开始交互。
保证所有测试用例的n^3之和不超过3 * 10^5。
交互过程：
- 输入格式：要设置一场比赛，请按照以下格式打印一行：
? x1 x2 ... xn (1 ≤ xi ≤ n^2, xi两两不同) —— 比赛中的pepes的标签。
- 输出格式：在每场比赛后，你应该读取一行，包含一个整数p (1 ≤ p ≤ n^2) —— 比赛中最快的pepe的标签。
- 当你知道n^2-n+1个最快的pepes时，按照以下格式打印一行：
! p1 p2 ... p(n^2 - n + 1) (1 ≤ pi ≤ n^2, pi两两不同)
其中p是这些pepe的标签，按速度降序排列。
如果在一场测试用例中进行了超过2n^2 - 2n + 1场比赛，或者进行了无效的比赛，你可能会得到错误的答案。
在打印查询后，不要忘记输出行尾并刷新输出。否则，你会得到“Idleness limit exceeded”。具体刷新输出的方法取决于使用的编程语言。
黑客格式：
- 输入格式：对于黑客攻击，请使用以下格式。
第一行包含t —— 测试用例的数量。
每个测试用例的第一行包含一个整数n，后跟字符串“manual”。
每个测试用例的第二行包含一个1到n^2的整数的排列a1,a2,...,an^2。ai > aj当且仅当pepe i的速度比pepe j快。
- 输出格式：与正常执行相同。
例：
```
Input
1
2
Output
? 1 2
? 3 4
? 2 4
? 2 3
? 2 1
! 4 3 2
```题目大意： 这是一个交互式问题。有n^2个标号为1, 2, ..., n^2的pepes，它们的速度两两不同。你需要通过安排一些比赛来确定这些pepes的相对速度。 在一场比赛中，你可以精确地选择n个不同的pepes让它们相互比赛。每场比赛后，你只能知道这n个pepes中最快的那个。 你能否在最多2n^2 - 2n + 1场比赛中确定n^2-n+1个最快的pepes的顺序？注意，最慢的n-1个pepes之间是不可区分的。 注意，这个交互器是自适应的。也就是说，pepes的相对速度在一开始并不是固定的，可能会依赖于你的查询。但是保证在任何时刻都至少存在一种pepes的初始配置，使得对所有查询的回答都是一致的。 输入输出数据格式： 每个测试包含多个测试用例。第一行包含测试用例的数量t (1 ≤ t ≤ 10^4)。接下来是每个测试用例的描述。 每个测试用例只有一行，包含一个整数n (2 ≤ n ≤ 20)，表示一场比赛中的pepes数量。在读取每个测试用例的整数n后，你应该开始交互。 保证所有测试用例的n^3之和不超过3 * 10^5。 交互过程： - 输入格式：要设置一场比赛，请按照以下格式打印一行： ? x1 x2 ... xn (1 ≤ xi ≤ n^2, xi两两不同) —— 比赛中的pepes的标签。 - 输出格式：在每场比赛后，你应该读取一行，包含一个整数p (1 ≤ p ≤ n^2) —— 比赛中最快的pepe的标签。 - 当你知道n^2-n+1个最快的pepes时，按照以下格式打印一行： ! p1 p2 ... p(n^2 - n + 1) (1 ≤ pi ≤ n^2, pi两两不同) 其中p是这些pepe的标签，按速度降序排列。 如果在一场测试用例中进行了超过2n^2 - 2n + 1场比赛，或者进行了无效的比赛，你可能会得到错误的答案。 在打印查询后，不要忘记输出行尾并刷新输出。否则，你会得到“Idleness limit exceeded”。具体刷新输出的方法取决于使用的编程语言。 黑客格式： - 输入格式：对于黑客攻击，请使用以下格式。 第一行包含t —— 测试用例的数量。 每个测试用例的第一行包含一个整数n，后跟字符串“manual”。 每个测试用例的第二行包含一个1到n^2的整数的排列a1,a2,...,an^2。ai > aj当且仅当pepe i的速度比pepe j快。 - 输出格式：与正常执行相同。 例： ``` Input 1 2 Output ? 1 2 ? 3 4 ? 2 4 ? 2 3 ? 2 1 ! 4 3 2 ```