← 返回题目列表

Codeforces · 1977/E

E. 张量

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

这是一个交互问题。

给你一个整数$$$n$$$。

陪审团向您隐藏了一个有向图,该图具有 $$$n$$$ 个顶点(编号从 $$$1$$$ 到 $$$n$$$)和一定数量的边。您还知道:

- 该图仅包含 $$$i \leftarrow j$$$ 形式的边,其中 $$$1 \le i < j \le n$$$。
- 对于任何三个顶点 $$$1 \le i < j < k \le n$$$,至少满足以下条件之一$$$^\dagger$$$:顶点 $$$i$$$ 可从顶点 $$$j$$$ 到达,或顶点 $$$i$$$ 可从顶点 $$$k$$$ 到达,或顶点 $$$j$$$ 可从顶点$$$k$$$。

您希望将每个顶点着色为黑色或白色,以便对于任何两个相同颜色的顶点 $$$i$$$ 和 $$$j$$$ ($$$1 \le i < j \le n$$$),顶点 $$$i$$$ 可以从顶点 $$$j$$$ 到达。

为此,您可以提出以下类型的查询:

- ? i j — 顶点 $$$i$$$ 是否可以从顶点 $$$j$$$ ($$$1 \le i < j \le n$$$) 到达?

在最多 $$$2 \cdot n$$$ 查询中找到隐藏图的任何有效顶点着色。可以证明这样的着色总是存在的。

请注意,分级器不具有自适应性:图表在进行任何查询之前是固定的。

$$$^\dagger$$$ 如果图中存在从顶点 $$$b$$$ 到顶点 $$$a$$$ 的路径,则顶点 $$$a$$$ 可以从顶点 $$$b$$$ 到达。

输入

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

每个测试用例的唯一行包含一个整数 $$$n$$$ ($$$3 \le n \le 100$$$) — 隐藏图中的顶点数。

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

互动

每个测试用例的交互从读取整数 $$$n$$$ 开始。

要进行查询,请输出不带引号的“? i j” ($$$1 \le i < j \le n$$$)。如果从顶点 $$$j$$$ 可以到达顶点 $$$i$$$,则您将得到“是”的答案。否则,您将得到“否”的答案。

如果您收到整数 $$$-1$$$ 而不是答案或有效值 $$$n$$$,则意味着您的程序进行了无效查询,超出了查询限制,或者对之前的测试用例给出了错误答案。您的程序必须立即终止才能收到错误答案判决。否则,您可以获得任意判决,因为您的解决方案将继续从关闭的流中读取。

当您准备好给出最终答案时,输出“! $$$c_1 \ c_2 \ \ldots \ c_n$$$”(不带引号)——顶点的颜色,其中如果顶点为黑色,则 $$$c_i = 0$$$;如果顶点为白色,则 $$$c_i = 1$$$。解决所有测试用例后,您的程序应立即终止。

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

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

黑客

要破解,请使用以下格式:

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$3 \le n \le 100$$$, $$$0 \le m \le \frac{n\cdot(n - 1)}{2}$$$) - 图中顶点和边的数量。

以下$$$m$$$行中的每一行都应包含两个整数$$$a$$$和$$$b$$$ ($$$1 \le b < a \le n$$$),表示图中存在边$$$a \rightarrow b$$$。图表应满足上述条件。

所有测试用例的 $$$n$$$ 总和不应超过 $$$1000$$$。

示例

输入 #1

2
4

YES

YES

YES

NO

NO

NO

5

输出 #1

? 1 2

? 2 3

? 1 3

? 1 4

? 2 4

? 3 4

! 0 0 0 1

! 1 1 0 1 0

注意

第一个测试用例中的隐藏图:

第二个测试用例中的隐藏图:

交互发生如下:

SolutionJuryExplanation2有$$$2$$$测试用例。4在第一个测试用例中,图有$$$4$$$个顶点。? 1 2 YES解决方案询问顶点$$$1$$$是否可以从顶点$$$2$$$到达,陪审团回答是。? 2 3 YES解决方案询问顶点$$$2$$$是否可以从顶点$$$3$$$到达,陪审团回答是。? 1 3 YES解决方案询问顶点$$$1$$$是否可以从顶点$$$3$$$到达,陪审团回答是。? 1 4 NO 该解决方案询问顶点 $$$1$$$ 是否可以从顶点 $$$4$$$ 到达,陪审团回答“否”。 2 4 NO 该解决方案询问顶点 $$$2$$$ 是否可以从顶点 $$$4$$$ 到达,陪审团回答“否”。 3 4 NO 该解决方案询问顶点 $$$3$$$ 是否可以从顶点 $$$4$$$ 到达,陪审团回答“否”! 0 0 0 1该解决方案以某种方式确定了有效的颜色并将其输出。由于输出正确,陪审团继续进行下一个测试用例。5在第二个测试用例中,该图有 $$$5$$$ 个顶点。! 1 1 0 1 0该解决方案以某种方式确定了有效的着色,并将其输出。由于输出是正确的并且没有更多的测试用例,陪审团和解决方案退出。

请注意,示例输入和输出中的换行符是为了清楚起见,在实际交互中不会出现。