P16914 [JLCPC 2026] Hidden $k$-Tuples.

**This is an interactive problem.** There is a hidden partition that divides the integers $1, 2, \ldots, n$ into $\dfrac{n}{k}$ pairwise disjoint $k$-tuples. It is guaranteed that $n$ is a multiple of $k$. You need to find all hidden $k$-tuples by making queries. In one query, you may choose a set $S \subseteq \{1, 2, \ldots, n\}$. The interactor will return an integer indicating how many hidden $k$-tuples are **fully contained** in $S$. The number of queries you make must not exceed $n \times \lceil \log_2 n \rceil$. > $\lceil \cdot \rceil$ is the ceiling function. $\lceil x \rceil$ is the smallest integer not less than $x$. For example, $\lceil 7 \rceil = 7$, and $\lceil 3.14 \rceil = 4$.

At the start, the interactor outputs one line with two integers $n$ and $k$ ($2 \le n \le 300$, $2 \le k \le n$, and $n$ is a multiple of $k$). The hidden partition is kept by the interactor and will not be given directly. After each time you output a valid query, the interactor returns one line with an integer $r$, which is the number of hidden $k$-tuples fully contained in your queried set.

You can make queries in the following form: $$\texttt{? c $x_1$ $x_2$ $\ldots$ $x_c$}$$ Here, $0 \le c \le n$, and $x_1, x_2, \ldots, x_c$ must be pairwise distinct integers satisfying $1 \le x_i \le n$. This query means you choose the set $S=\{x_1,x_2,\ldots,x_c\}$. The interactor will return an integer $r$, which is the number of hidden $k$-tuples fully contained in $S$. When you are sure about the answer, you need to output: $$\texttt{! $a_1$ $a_2$ $\ldots$ $a_n$}$$ Here, $a_i$ denotes the tuple index of the tuple that contains element $i$. The indices must satisfy $1 \le a_i \le \dfrac{n}{k}$. If two elements belong to the same hidden tuple, their indices must be the same; if two elements belong to different hidden tuples, their indices must be different. The order of the tuple indices can be arbitrary. The number of queries you make must not exceed $n \times \lceil \log_2 n \rceil$. After outputting the final answer, your program should terminate immediately. Note that after each query or final answer, you must flush the output buffer. For example, in C++ you can use `fflush(stdout)` or `cout

In the example below, $n = 6$, $k = 2$, and the hidden tuples are $\{1, 3\}$, $\{2, 6\}$, and $\{4, 5\}$. $$ \def\arraystretch{1.5} \begin{array}{|l|c|} \hline \textbf{Program} & \textbf{Interactor} \\ \hline & \verb!6 2! \\ \hline \verb!? 3 1 3 5! & \verb!1! \\ \hline \verb!? 4 2 3 4 5! & \verb!1! \\ \hline \verb!? 6 1 2 3 4 5 6! & \verb!3! \\ \hline \verb|! 1 2 1 3 3 2| & \\ \hline \end{array} $$ - Query $\{1, 3, 5\}$: the tuple $\{1, 3\} \subseteq S$, so the answer is $1$. - Query $\{2, 3, 4, 5\}$: the tuple $\{4, 5\} \subseteq S$, so the answer is $1$. - Query $\{1, 2, 3, 4, 5, 6\}$: all three tuples are contained, so the answer is $3$. - Output $[1, 2, 1, 3, 3, 2]$ means: elements $1, 3$ form group $1$; elements $2, 6$ form group $2$; elements $4, 5$ form group $3$. Translated by ChatGPT 5