CF1854D Michael and Hotel

Michael 和 Brian 被困在一个有 $n$ 个房间的酒店中，房间编号从 $1$ 到 $n$。他们需要找到彼此。但这个酒店的所有门都被锁住了，唯一的移动方式是使用每个房间里的传送器。第 $i$ 个房间有一个传送器，会把你传送到房间 $a_i$（可能有 $a_i = i$）。但他们并不知道 $a_1,a_2, \dots, a_n$ 的具体数值。 不过，他们可以打电话到前台进行询问。每次询问时，他们给出一个房间 $u$，一个正整数 $k$，以及一个房间集合 $S$。酒店前台会回答：如果一个人从房间 $u$ 出发，连续使用传送器 $k$ 次，最终是否会到达集合 $S$ 中的某个房间。 Brian 在房间 $1$。Michael 想知道房间集合 $A$，使得如果他从这些房间中的某一个出发，他们可以通过传送器最终相遇。他最多可以询问 $2000$ 次。 数列 $a_1, a_2, \dots, a_n$ 在交互开始前就已经确定，并且不会根据你的询问而改变。换句话说，交互器不是自适应的。

输入包含一个整数 $n$（$2 \leq n \leq 500$）。

每次询问，请输出一行，格式为 "? u k |S| S_1 S_2 ... S_{|S|}"，其中 $1 \leq u, S_1, \ldots, S_{|S|} \leq n$，所有 $S_i$ 互不相同，且 $1 \leq k \leq 10^9$。 对于每次询问，你会收到一行回复，"1" 表示答案是肯定的，"0" 表示答案是否定的。 当你要输出最终答案时，输出一行，格式为 "! |A| A_1 A_2 ... A_{|A|}"，其中 $1 \leq A_1, \ldots, A_{|A|} \leq n$，所有 $A_i$ 互不相同。输出答案不计入询问次数。 具体交互格式请参考样例。 如果你询问次数过多或询问格式错误，将会收到 Wrong answer。 每次输出询问后不要忘记输出换行并刷新输出缓冲区，否则会收到 Idleness limit exceeded。具体做法如下： - C++：fflush(stdout) 或 cout.flush() - Java：System.out.flush() - Pascal：flush(output) - Python：stdout.flush() - 其它语言请查阅相关文档。 Hack 格式 对于 hack，请使用如下格式： 第一行包含 $n$，即房间数。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示第 $i$ 个房间的传送器会传送到房间 $a_i$。

在样例测试中，有 $n=5$ 个房间，隐藏的传送器数组为 $[1, 2, 1, 3, 2]$。 - 第一个询问是从房间 $a=3$ 出发，连续使用传送器 $5$ 次，最终是否会到达 $S=\{2, 3\}$ 中的某个房间。实际上会到达房间 $1$，所以答案是 $0$。 - 第二个询问是从房间 $a=2$ 出发，连续使用传送器 $5$ 次，最终是否会到达 $S=\{2, 3\}$ 中的某个房间。实际上会到达房间 $2$，所以答案是 $1$。 由 ChatGPT 4.1 翻译