← 返回题目列表

Codeforces · 1854/D

D. 迈克尔和酒店

中文机器翻译题面 查看原题

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$$$ 房间。迈克尔想知道房间的集合 $$$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$$$ 全部不同。打印答案不算作查询。

请参阅交互示例以更清楚地了解。

如果您提出太多查询或提出格式错误的查询,您将得到错误的答案。

打印查询后,不要忘记输出行尾并刷新输出。否则,您将超出空闲限制。为此,请使用:

- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 请参阅其他语言的文档。

黑客格式

对于 hacks,请使用以下格式。

第一行应包含 $$$n$$$ — 房间数量。

第二行应包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ — 房间 $$$i$$$ 中的传送器通向房间 $$$a_i$$$。

示例

输入 #1

5

0

1

输出 #1

? 3 5 2 2 3

? 2 5 2 2 3

! 3 1 3 4

注意

在示例测试中,有 $$$n=5$$$ 个房间,描述传送器行为的(隐藏)数组为 $$$[1, 2, 1, 3, 2]$$$。

- 第一个查询询问是否从房间号 $$$a=3$$$ 开始,使用传送器 $$$5$$$ 次,最终到达两个房间 $$$S=\{2, 3\}$$$ 中的一个。此操作导致最终进入房间 $$$1$$$,因此答案是 $$$0$$$。
- 第二个查询询问是否从房间号 $$$a=2$$$ 开始,使用传送器 $$$5$$$ 次,最终到达两个房间 $$$S=\{2, 3\}$$$ 之一。此操作导致最终进入房间$$$2$$$,因此答案是$$$1$$$。