← 返回题目列表

Codeforces · 2133/C

C. 下界

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

这是一个交互问题。

最近发现了下界,史蒂夫建立了一个由 $$$n$$$ 下界传送门组成的网络,每个传送门都位于他世界的不同位置。

每个门户都在一个方向上连接到一定数量(可能为零)的其他门户。为了避免迷路,史蒂夫精心构建了门户网络,这样就不会有通过门户的跳跃顺序将您从一个位置带回原来的位置;形式上,网络形成有向无环图。

史蒂夫拒绝告诉您哪些门户连接到哪个,但他允许您提出疑问。在每个查询中,您为 Steve 提供一组位置 $$$S = \{s_1, s_2, \ldots, s_k\}$$$ 和起始位置 $$$x \in S$$$。 Steve 将计算出从 $$$x$$$ 开始且仅经过 $$$S$$$ 中的位置的最长路径,并告诉您其中的位置数量。 (如果无法从 $$$x$$$ 到达 $$$S$$$ 中的任何其他位置,Steve 将回复 $$$1$$$。)

当您寻求获得成就“热门旅游目的地”时,您希望找到访问尽可能多的地点的路径。史蒂夫感觉特别慷慨,会给你 $$$2 \cdot n$$$ 查询来找到它。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 1000$$$)。测试用例的描述如下。

每个测试用例的唯一行包含一个整数 $$$n$$$ ($$$2 \le n \le 500$$$) - 位置数。

保证所有测试用例的$$$n^3$$$总和不超过$$$500^3$$$。

互动

每个测试用例的交互都从读取整数 $$$n$$$ 开始。然后您最多可以进行 $$$2 \cdot n$$$ 查询。

要进行查询,请按以下格式输出一行:

  • $$$\texttt{?}\,\,x\,\,k\,\,s_1\,s_2\,\ldots\,s_k$$$

评审团将返回质疑的答案。

当找到最大长度的路径时,按以下格式输出一行:

  • $$$\texttt{!}\,\,k\,\,v_1\,v_2\,\ldots\,v_k$$$

这表示从门户 $$$v_1$$$ 开始,然后跳到 $$$v_2$$$,然后跳到 $$$v_3$$$ 等等,以 $$$v_k$$$ 结束。

注意输出答案 不算数 朝着 $$$2 \cdot n$$$ 查询的限制。

打印每个查询后,不要忘记输出行尾并刷新$$$^{\text{*}}$$$ 输出。否则,你会得到 超出空闲限制 判决。

如果在任何交互步骤中您读取 $$$-1$$$ 而不是有效数据,您的解决方案必须立即退出。这意味着您的解决方案将收到 错误答案 由于无效查询或任何其他错误。未能退出可能会导致任意判决,因为您的解决方案将继续从关闭的流中读取。

交互器是 不自适应。交互过程中门户之间的连接不会改变。

黑客

要执行黑客攻击,请使用以下格式:

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 1000$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 500$$$) — 位置数。

然后,输出 $$$n$$$ 行。第 $$$i$$$ 行的格式应为 $$$k_i\,v_1\,v_2\,\ldots\,v_{k_i}$$$ ($$$0 \le k_i \le n - 1$$$, $$$1 \le v_j \le n$$$, $$$v_j \ne i$$$),表示位置 $$$i$$$ 处的门户已连接朝一个方向(通向)位置 $$$v_1, v_2, \ldots, v_{k_i}$$$。给定网络必须形成有向无环图。

所有测试用例的 $$$n^3$$$ 总和不得超过 $$$500^3$$$。

$$$^{\text{*}}$$$要刷新,请使用:

  • fflush(标准输出) or cout.flush() 在 C++ 中;
  • sys.stdout.flush() 在 Python 中;
  • 请参阅其他语言的文档。

示例

输入
复制

2
5

3

3

2

1


2

1

1

输出
复制

? 1 4 1 2 3 4

? 3 3 4 3 2

? 5 2 1 5

? 2 2 2 4

! 4 5 1 4 2


? 1 2 1 2

? 2 2 1 2

! 1 1

注意

在第一个测试用例中,门户网络如下:

  • 从位置 $$$1$$$ 开始,仅经过 $$$\{1, 2, 3, 4\}$$$ 的最长路径是路径 $$$1 \rightarrow 4 \rightarrow 2$$$,它具有 $$$3$$$ 不同的位置。
  • 从位置 $$$3$$$ 开始,仅经过 $$$\{2, 3, 4\}$$$ 的最长路径是路径 $$$3 \rightarrow 4 \rightarrow 2$$$,它具有 $$$3$$$ 不同的位置。
  • 从位置 $$$5$$$ 开始,仅通过 $$$\{1, 5\}$$$ 的最长路径是路径 $$$5 \rightarrow 1$$$,它具有 $$$2$$$ 不同的位置。
  • 从 $$$2$$$ 开始不可能到达 $$$\{2, 4\}$$$ 中的任何其他位置,因此 Steve 对该查询回答 $$$1$$$。
使用这些查询中的信息,可以确定最长路径是 $$$5 \rightarrow 1 \rightarrow 4 \rightarrow 2$$$。

在第二个测试用例中,门户网络如下:

两个门户都没有相互连接,因此最长的路径是单个位置。请注意 ! 1 2 也是一个有效的答案。