34630번 - Monotone Subsequence 다국어인터랙티브

문제

This is an interactive problem.

Faker is being naughty again. You asked him to create a nice query problem, but he created an interactive problem where he is answering a query instead! Faker hid a permutation from you, and you have to infer some interesting information by interacting with him.

You are given an integer $n$. Faker hid a hidden permutation^* $p_1, p_2, \ldots, p_{n^2+1}$ of length $n^2+1$. Your goal is to find a monotone subsequence (either increasing or decreasing) of the hidden permutation, with length exactly $n+1$. It can be proved that every permutation of length $n^2 + 1$ contains a monotone subsequence of length $n+1$. For more information about the proof, you can check out this Wikipedia page.

To find it, you can make at most $n$ skyscraper queries to the interactor, which is defined as follows:

• You provide a set of $k$ indices as a strictly increasing sequence: $i_1, i_2, \ldots, i_k$.
• The interactor considers the values of the hidden permutation at these indices: $p_{i_1}, p_{i_2}, \ldots, p_{i_k}$.
• The interactor then returns the indices corresponding to the visible skyscrapers from this set. An index $i_j$ is visible if its value $p_{i_j}$ is greater than the values of all preceding elements in your query, i.e., $p_{i_j} > p_{i_m}$ for all 1ドル \le m < j$. This is equivalent to finding the indices of the left-to-right maxima of the sequence $(p_{i_1}, \ldots, p_{i_k})$.

After making at most $n$ queries, you must report a valid monotone subsequence of length exactly $n+1$.

Note that the permutation $p$ is fixed before any queries are made and does not depend on the queries.

^*A permutation of length $m$ is an array consisting of $m$ distinct integers from 1ドル$ to $m$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation (2ドル$ appears twice in the array), and $[1,3,4]$ is also not a permutation ($m=3$ but there is 4ドル$ in the array).

입력

Each test contains multiple test cases. The first line contains the number of test cases $t$ (1ドル \le t \le 5000$). The description of the test cases follows.

The first and only line of each test case contains a single integer $n$ (1ドル \le n \le 100$).

It is guaranteed that the sum of $n^2+1$ over all test cases does not exceed 10ドル,001円$.

출력

제한

인터랙션

The interaction for each test case begins by reading the integer $n$.

To make a query, print a line in the following format:

• ? $k$ $i_1$ $i_2$ $\ldots$ $i_k$

where $k$ is the number of indices in your query (1ドル \le k \le n^2+1$), and $i_1, \ldots, i_k$ are the indices themselves, satisfying 1ドル \le i_1 < i_2 < \ldots < i_k \le n^2+1$. The indices should be presented in sorted order.

In response, the interactor will print a line in the following format:

• $c$ $j_1$ $j_2$ $\ldots$ $j_c$

where $c$ is the number of visible skyscrapers from your query (1ドル \le c \le k$), and $j_1, \ldots, j_c$ are their indices, satisfying 1ドル \le j_1 < j_2 < \ldots < j_c \le n^2+1$. The indices will be presented in sorted order.

To report your final answer, print a line in the following format:

• ! $s_1$ $s_2$ $\ldots$ $s_{n+1}$

where $s_1, \ldots, s_{n+1}$ are the indices of the elements that form your found monotone subsequence of length $n+1,ドル satisfying 1ドル \le s_1 < s_2 < \ldots < s_{n+1} \le n^2 + 1$. The indices should be presented in sorted order.

Note that answering does not count toward your limit of commands.

After printing the answer, your program should proceed to the next test case or terminate if there are no more.

After printing each query do not forget to output the end of line and flush^* the output. Otherwise, you will get Idleness limit exceeded verdict.

If, at any interaction step, you read $-1$ instead of valid data, your solution must exit immediately. This means that your solution will receive Wrong answer because of an invalid query or any other mistake. Failing to exit can result in an arbitrary verdict because your solution will continue to read from a closed stream.

^*To flush, use:

• fflush(stdout) or cout.flush() in C++;
• sys.stdout.flush() in Python;
• see the documentation for other languages.

노트

For the first test case, $n=1$. The hidden permutation is $p=[1, 2]$.

• For the query ? 2 1 2, the visible skyscrapers are at indices 1ドル$ and 2ドル$. The interactor returns 2 1 2.
• An increasing subsequence of length 2ドル$ at indices 1,ドル 2$ is reported.

For the second test case, $n=2$. The hidden permutation is $p=[5, 3, 4, 1, 2]$.

• For the query ? 3 1 2 3, the visible skyscraper is at index 1ドル$. The interactor returns 1 1.
• For the query ? 3 2 3 5, the visible skyscrapers are at indices 2ドル$ and 3ドル$. The interactor returns 2 2 3.
• A decreasing subsequence of length 3ドル$ at indices 1,ドル 3, 4$ is reported.

Although Faker will play the role of interactor, the interactor will never lie to you.