← 返回题目列表

Codeforces · 2032/D

D. 吉诺克拉肯

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

这是一个交互问题。

清理水边区域后,格蕾特发现了一个名为 Genokraken 的怪物,她将其收容起来以进行科学研究。

怪物的神经系统可以被构造为一棵由$$$n$$$节点组成的树$$$^{\dagger}$$$(实际上,一切都应该不再像树$$$\ldots$$$),编号从$$$0$$$到$$$n-1$$$,以节点$$$0$$$为根。

Gretel 的目标是了解怪物神经系统的确切结构 - 更具体地说,她想知道树的值 $$$p_1, p_2, \ldots, p_{n-1}$$$,其中 $$$p_i$$$ ($$$0 \le p_i < i$$$) 是节点 $$$i$$$ ($$$1 \le我\le n - 1$$$)。

她不知道节点到底是如何放置的,但她知道一些方便的事实:

- 如果我们删除根节点$$$0$$$和所有相邻的边,这棵树将变成仅由路径$$$^{\ddagger}$$$组成的森林。最初与节点 $$$0$$$ 相邻的每个节点将是某个路径的终点。
- 节点的索引方式为:如果 $$$1 \le x \le y \le n - 1$$$,则 $$$p_x \le p_y$$$。
- 节点 $$$1$$$ 恰好有两个相邻节点(包括节点 $$$0$$$)。

这张图中的树不满足条件,因为如果我们删除节点$$$0$$$,那么节点$$$2$$$(最初与节点$$$0$$$相邻)将不会是路径$$$4-2-5$$$的终点。这张图中的树不满足条件,因为$$$p_3 \le p_4$$$必须成立。这张图中的树不满足条件,因为节点 $$$1$$$ 只有一个相邻节点。

Gretel 可以对收容间进行查询:

- "? a b" ($$$1 \le a, b < n$$$, $$$a \ne b$$$) — 单元格将检查节点 $$$a$$$ 和 $$$b$$$ 之间的简单路径是否包含节点 $$$0$$$。

然而,为了避免过度刺激生物而产生意外后果,Gretel 希望最多查询 $$$2n - 6$$$ 次。尽管格蕾特很有天赋,但她无法同时完成所有事情,所以你能为她提供帮助吗?

$$$^{\dagger}$$$树是一个连通图,其中每对不同的节点都有一个简单的路径连接它们。

$$$^{\ddagger}$$$路径是一棵树,其顶点可以按 $$$v_1, v_2, \ldots, v_k$$$ 的顺序列出,使得边为 $$$(v_i, v_{i+1})$$$ ($$$1 \le i < k$$$)。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 500$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$4 \le n \le 10^4$$$) — Genokraken 神经系统中的节点数。

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

互动

对于每个测试用例,交互都是通过读取整数 $$$n$$$ 开始的。

然后您可以进行以下类型的查询:

- "? a b" (不带引号) ($$$1 \le a, b < n$$$, $$$a \ne b$$$)。

查询后,读取一个整数 $$$r$$$ — 您的查询的答案。您最多可以使用 $$$2n - 6$$$ 此类查询。

- 如果节点 $$$a$$$ 和 $$$b$$$ 之间的简单路径不包含节点 $$$0$$$,则将得到 $$$r = 0$$$。
- 如果节点 $$$a$$$ 和 $$$b$$$ 之间的简单路径包含节点 $$$0$$$,则将得到 $$$r = 1$$$。
- 如果您进行超过 $$$2n-6$$$ 查询或进行无效查询,您将得到 $$$r = -1$$$。您需要在此之后终止才能获得“错误答案”的判决。否则,您可以获得任意判决,因为您的解决方案将继续从关闭的流中读取。

查出结构后,输出一行,格式为“! $$$p_1 \space p_2 \ldots p_{n-1}$$$”(不带引号),其中$$$p_i$$$ ($$$0 \le p_i < i$$$)表示节点$$$i$$$的直接父节点的索引。此查询不计入 $$$2n - 6$$$ 查询限制。

解决一个测试用例后,程序应立即转到下一个测试用例。解决所有测试用例后,程序应立即终止。

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

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

交互器是非自适应的。交互过程中树不会改变。

黑客

对于 hack,请使用以下格式:

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

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$4 \le n \le 10^4$$$) — Genokraken 神经系统中的节点数。

每个测试用例的第二行包含 $$$n-1$$$ 整数 $$$p_1, p_2, \ldots, p_{n-1}$$$ ($$$0 \le p_1 \le p_2 \le \ldots \le p_{n-1} \le n - 2$$$, $$$0 \le p_i < i$$$) — 的直接父级系统中的节点分别为$$$1$$$、$$$2$$$、...、$$$n-1$$$。

在每个测试用例中,值 $$$p_1, p_2, \ldots, p_{n-1}$$$ 必须确保树中满足以下条件:

- 如果我们删除根节点 $$$0$$$ 和所有相邻的边,这棵树将变成仅由路径组成的森林。最初与节点 $$$0$$$ 相邻的每个节点将是某个路径的终点。
- 节点 $$$1$$$ 恰好有两个相邻节点(包括节点 $$$0$$$)。

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

示例

输入 #1

3
4

1

5

1

0

9

输出 #1

? 2 3

! 0 0 1

? 2 3

? 2 4

! 0 0 1 2

! 0 0 0 1 3 5 6 7

注意

在第一个测试用例中,Genokraken 的神经系统形成以下树:

- “?2 3”的答案是$$$1$$$。这意味着节点 $$$2$$$ 和 $$$3$$$ 之间的简单路径包含节点 $$$0$$$。

在第二个测试用例中,Genokraken 的神经系统形成以下树:

- “?2 3”的答案是$$$1$$$。这意味着节点 $$$2$$$ 和 $$$3$$$ 之间的简单路径包含节点 $$$0$$$。
- “?2 4”的答案是$$$0$$$。这意味着节点 $$$2$$$ 和 $$$4$$$ 之间的简单路径不包含节点 $$$0$$$。

在第三个测试用例中,Genokraken 的神经系统形成以下树: