Hidden $k$-Tuples - المسألة

这是一个交互式问题。

存在一个隐藏的划分，将整数 $1, 2, \dots, n$ 划分为 $\frac{n}{k}$ 个互不相交的 $k$-元组（$k$-tuples）。保证 $k \mid n$。

你需要通过询问来确定所有隐藏的 $k$-元组。

在每次询问中，你可以选择一个集合 $S \subseteq \{1, 2, \dots, n\}$，交互器将返回一个整数，表示有多少个隐藏的 $k$-元组完全包含在 $S$ 中。

询问次数不能超过 $n \lceil \log_2 n \rceil$。

在程序开始时，交互器会输出一行，包含两个整数 $n$ 和 $k$。

这里满足 $2 \le n \le 300$，$2 \le k \le n$，且 $k \mid n$。

隐藏的划分由交互器存储，不会直接给出。

在你输出每次有效的询问后，交互器会返回一行，包含一个整数 $r$ —— 完全包含在你询问的集合中的隐藏 $k$-元组的数量。

你可以进行如下格式的询问：

? c x1 x2 ... xc

其中 $0 \le c \le n$，且 $x_1, x_2, \dots, x_c$ 必须是互不相同的整数，满足 $1 \le x_i \le n$。

该询问表示你选择了集合 $S = \{x_1, x_2, \dots, x_c\}$。交互器会返回一个整数 $r$ —— 完全包含在 $S$ 中的隐藏 $k$-元组的数量。

当你确定了答案后，输出：

! a1 a2 ... an

其中 $a_i$ 表示元素 $i$ 所属的元组编号。编号必须满足 $1 \le a_i \le \frac{n}{k}$。

属于同一个隐藏元组的两个元素必须具有相同的编号；属于不同隐藏元组的两个元素必须具有不同的编号。元组编号的顺序是任意的。

询问次数不能超过 $n \lceil \log_2 n \rceil$。在输出最终答案后，你的程序应当立即终止。

请注意，在每次询问或输出最终答案后，你必须刷新输出缓冲区。例如，在 C++ 中你可以使用：

fflush(stdout);

或

cout << flush;

如果你的输出格式无效、询问次数超过限制或最终答案错误，你将收到 Wrong Answer 或 Presentation Error。

交互器是非适应性（non-adaptive）的，这意味着所有 $k$-元组在交互开始前就已经确定，不会根据你的询问而改变。

? 3 1 3 5
? 4 2 3 4 5
? 6 1 2 3 4 5 6
! 1 2 1 3 3 2

在下方的样例中，$n = 6$，$k = 2$，隐藏的元组为 $\{1, 3\}$，$\{2, 6\}$，$\{4, 5\}$。

询问 $\{1, 3, 5\}$：元组 $\{1, 3\} \subseteq S$，因此答案为 $1$。
询问 $\{2, 3, 4, 5\}$：元组 $\{4, 5\} \subseteq S$，因此答案为 $1$。
询问 $\{1, 2, 3, 4, 5, 6\}$：所有三个元组都包含在内，因此答案为 $3$。
输出 ! 1 2 1 3 3 2 表示：元素 $1, 3$ 组成第 $1$ 组；元素 $2, 6$ 组成第 $2$ 组；元素 $4, 5$ 组成第 $3$ 组。

QOJ.ac