CF1363D Guess The Maximums

这是一个交互题。 Ayush 设计了一种新的方式来设置他的锁的密码。这个锁有 $k$ 个槽位，每个槽位可以放 $1$ 到 $n$ 之间的整数。密码 $P$ 是一个长度为 $k$ 的整数序列，每个元素都在 $[1, n]$ 范围内，第 $i$ 个元素放在锁的第 $i$ 个槽位。 为了设置密码，Ayush 先构造了一个长度为 $n$ 的整数数组 $A$，每个元素都在 $[1, n]$ 范围内（不一定互不相同）。然后他选择了 $k$ 个非空且两两不相交的下标子集 $S_1, S_2, ..., S_k$（即 $S_i \cap S_j = \emptyset$，$i \neq j$），并将密码设置为 $P_i = \max\limits_{j \notin S_i} A[j]$。换句话说，密码的第 $i$ 个数字等于数组 $A$ 中所有下标不属于 $S_i$ 的元素的最大值。 你将获得 Ayush 选择的这些下标子集。你需要猜出密码。你可以进行不超过 12 次的查询，每次可以选择数组 $A$ 的一个非空下标子集，询问该子集下标对应元素的最大值。

输入的第一行包含一个整数 $t$（$1 \leq t \leq 10$），表示测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含两个整数 $n$ 和 $k$（$2 \leq n \leq 1000, 1 \leq k \leq n$），分别表示数组的长度和子集的数量。接下来的 $k$ 行，每行描述一个子集。第 $i$ 行包含一个整数 $c$（$1 \leq c < n$），表示子集 $S_i$ 的大小，随后是 $c$ 个互不相同的整数，表示 $S_i$ 中的下标，这些下标在 $[1, n]$ 范围内。 保证任意两个子集没有交集。

每次查询时，输出一行： - 首先输出 "? c "（不含引号），其中 $c$（$1 \leq c \leq n$）表示你要查询的下标子集的大小，后面跟着 $c$ 个互不相同的 $[1, n]$ 范围内的下标，空格分隔。 对于每次查询，你会收到一个整数 $x$，表示你查询的下标对应的数组元素的最大值。如果你查询了非法的下标子集，或者查询次数超过限制（比如某个下标大于 $n$），你会收到 $x = -1$。此时你应立即终止程序。 当你猜出密码后，输出一行 "! "（不含引号），后面跟着 $k$ 个空格分隔的整数，表示你猜测的密码序列。 猜测密码不计入查询次数。 之后，你需要读取一个字符串。如果你猜测正确，会收到字符串 "Correct"。此时继续解答剩余测试用例。如果猜测错误，会收到字符串 "Incorrect"，此时应立即终止程序。 交互器是非自适应的。数组 $A$ 在所有查询中保持不变。 每次输出查询后不要忘记换行并刷新输出，否则会因超时被判为“Idleness limit exceeded”。刷新输出的方法如下： - C++：fflush(stdout) 或 cout.flush() - Java：System.out.flush() - Pascal：flush(output) - Python：stdout.flush() - 其它语言请查阅相关文档。 ### Hack 格式 Hack 数据格式如下： 第一行输入一个整数 $t$（$1 \leq t \leq 10$），表示测试用例数量。 每个测试用例第一行输入两个整数 $n$ 和 $k$（$2 \leq n \leq 1000, 1 \leq k \leq n$），表示数组长度和子集数量。接下来一行输入 $n$ 个 $[1, n]$ 范围内的整数，表示数组 $A$。接下来的 $k$ 行，每行输入一个整数 $c$（$1 \leq c < n$），后跟 $c$ 个互不相同的 $[1, n]$ 范围内的下标，表示子集 $S_i$。 任意两个子集之间没有交集。

样例中的数组 $A$ 为 $[1, 2, 3, 4]$。密码长度为 $2$。第一个密码元素是 $A[2]$、$A[4]$ 的最大值（因为第一个子集包含下标 $1$ 和 $3$，所以取剩下下标的最大值）。第二个密码元素是 $A[1]$、$A[3]$ 的最大值（因为第二个子集包含下标 $2$、$4$，所以取剩下下标的最大值）。 在猜测密码后，不要忘记读取 "Correct" / "Incorrect" 字符串。 由 ChatGPT 4.1 翻译