P13150 [GCJ 2018 #3] Name-Preserving Network

一个研究联盟正在建设一个新的数据中心。在数据中心中，一组计算机被设置为协同工作，并通过网络进行通信。该网络仅通过计算机之间的直接双向连接工作。对于没有直接连接的两台计算机 $c_1$ 和 $c_2$，只要存在一条由连接 $l_1, l_2, ..., l_k$ 组成的路径，使得每对相邻连接 $l_i$ 和 $l_{i+1}$ 共享一个端点，且 $c_1$ 是 $l_1$ 的一个端点，$c_2$ 是 $l_k$ 的一个端点，那么 $c_1$ 和 $c_2$ 依然可以通信。任意两台计算机之间最多只能有一条直接连接。 联盟要求你提交一个网络设计，说明网络中有多少台计算机，以及它们之间如何连接。你提交的每个网络设计都必须满足以下特定限制： 1. 网络中的计算机数量必须在 $L$ 到 $U$ 之间（包含两端）。 2. 每台计算机必须正好作为 4 条连接的端点，即与 4 台不同的计算机直接相连。 3. 任意两台计算机都必须能够互相通信，如上所述。 4. 即使系统关闭时计算机的编号被随机更改，计算机也必须能够唯一地识别自己。 对于最后一点，具体说明如下：在你的网络设计中，每台计算机最初被分配一个唯一的整数编号，范围为 $1$ 到 $N$。然而，系统在某次关闭后，重新启动时这些编号可能会被重新排列——也就是说，每台计算机仍然拥有 $1$ 到 $N$ 之间的唯一编号，但不一定是原来的编号。网络必须能够仅凭现有的直接连接关系，恢复出原始的编号分配。 为了评估你的网络设计，研究联盟设置了一个自动化程序。该程序会接收你的网络设计，验证上述第 1-3 条限制，然后返回一个经过如下更改的网络设计副本： - 唯一编号被随机重新排列（即每个编号现在在任意计算机上都是等可能的）； - 每条连接按照较小编号在前的顺序输出（使用新的编号）； - 所有连接按照第一个端点编号递增排序，若相同则按第二个端点递增排序（即字典序）。 你需要能够准确判断编号是如何被更改的。形式化地说，自动化程序会生成一个 $1$ 到 $N$ 的随机排列 $f$，并将这些编号分配给一个“空白副本”网络（所有原有连接已移除）。然后，对于你设计中的每一条连接 $i$ 和 $j$，在副本中添加一条 $f(i)$ 和 $f(j)$ 之间的连接。你必须准确还原出 $f$。如果存在另一个不同的排列 $f'$ 也能得到相同的连接集合，而你返回了 $f'$，联盟将不接受你的设计，因为此时无法确保恢复的编号就是原始编号。 对于每个 $N$，其中 $10 \leq N \leq 100$，都至少存在一个满足所有上述限制且具有如下性质的网络：对其应用任意两个不同的排列 $f$ 和 $f'$，会得到不同的连接集合。 ### 交互协议 本题为交互题，这意味着输入输出方式与标准题目不同。你需要与一个独立的进程进行交互，该进程既为你提供信息，也评估你的回答。所有信息通过标准输入传入你的程序；你需要输出的内容通过标准输出发送。请注意，许多编程语言默认会缓冲输出，因此在等待输入前请确保输出已刷新（例如，使用 flush）。详见 FAQ 关于 flush 的说明。你通过标准错误输出的内容会被忽略，但可能会占用内存并计入内存限制，因此请勿输出过多内容。为方便调试，题目末尾提供了本地测试工具脚本（Python）。此外，分析部分还提供了以往 Code Jam 交互题的参考实现。 最初，你的程序应读取一行，包含一个整数 $T$，表示测试用例数量。然后，你需要处理 $T$ 个测试用例。 对于每个测试用例，你的程序首先读取一行，包含两个整数 $L$ 和 $U$，表示网络中计算机数量的取值范围（包含两端）。 接下来，你需要设计一个包含 $N$ 台计算机的网络，并输出 $2N+1$ 行，描述该网络设计。第一行包含一个整数 $N$。接下来的 $2N$ 行，每行包含两个整数 $A$ 和 $B$，表示一条连接 $A$ 和 $B$ 的不同计算机，且 $A \neq B$。注意，如果你输出了 $A$ $B$，则不能再输出 $A$ $B$ 或 $B$ $A$。 评测程序收到你的网络设计后，会首先检查前 3 条限制。如果有任何一条不满足，评测程序会返回一行 $-1$，然后结束所有通信并等待你的程序结束。如果你的程序正常结束且未违反其他限制，将收到 Wrong Answer 判定。 如果所有限制均满足，评测程序会返回 $2N+1$ 行。第一行包含整数 $N$（与你输出的 $N$ 相同）。接下来的 $2N$ 行，每行包含两个整数，描述副本网络的连接，格式同上。副本的生成方式如前所述，排列 $f$ 是从所有可能的排列中等概率随机选取的，且与网络设计无关。 完成一个测试用例后，你需要输出一行，包含 $N$ 个整数 $X_1, X_2, ..., X_N$，表示你设计中编号为 $i$ 的计算机在副本中被分配到的编号 $X_i$。 如果该列表不是评测程序生成的排列，将收到 Wrong Answer 判定。如果这是最后一个测试用例，评测程序不会再发送任何信息。否则，评测程序会发送一行 $-1$，然后不再通信。在这两种情况下，评测程序都会等待你的程序结束，只有在程序正常结束且未违反资源限制时才会判定为 Wrong Answer。 请勿在所有测试用例结束后继续向评测程序输出内容。也就是说，在输出最后一个测试用例的 $X$ 列表后，不要再输出任何内容，否则会收到 Wrong Answer 判定。 注意，你可以为不同测试用例提交相同的网络设计，只要该设计同时满足所有相关限制。此外，评测程序的随机种子是固定的，因此以相同顺序提交相同的原始网络设计，会得到相同的副本。

见交互协议。

见交互协议。

**样例交互** 注意，此样例交互使用的 $L$ 值比实际数据小，仅为说明方便。此外，正如题目所述，$N=6$ 时不存在满足“对任意不同排列 $f$ 和 $f'$，应用后得到的连接集合不同”这一性质的网络，因此即使题目限制允许，设计 $N=6$ 的网络也是不明智的！ ``` t = readline_int() // 读取 t=2 limits = readline_int_list() // 读取 6 50 printline 6 to stdout // 使用 6 台计算机。选手设计了一个八面体网络 printline 2 4 to stdout printline 1 2 to stdout // 连接的输出顺序不限 printline 3 1 to stdout // 端点顺序也不限 printline 1 4 to stdout printline 1 5 to stdout printline 2 3 to stdout printline 2 6 to stdout printline 3 5 to stdout printline 3 6 to stdout printline 4 5 to stdout printline 4 6 to stdout printline 5 6 to stdout flush stdout // 评测程序验证网络是否满足前 3 条限制，并随机选择 2 6 3 1 5 4 作为新排列 n = readline_int() // 读取 n=6 repeat 12 times: add readline_int_list() to edges // 读取 1 2, 1 4, 1 5, 1 6, 2 3, 2 5, // 2 6, 3 4, 3 5, 3 6, 4 5, 4 6, 按顺序 printline 2 5 6 1 3 4 // 这与评测程序返回的内容一致，但不是评测程序实际用的排列 flush stdout // 评测程序判定错误 limits = readline_int_list() // 期望读取下一个用例，但收到 -1，表示答案错误 exit // 退出，避免歧义性 TLE ``` 你可以使用本地测试工具进行本地或平台测试。要在本地测试，需要并行运行该工具和你的代码；可以使用我们的 [interactive runner](https://storage.googleapis.com/coding-competitions.appspot.com/interactive_runner.py)。更多信息请阅读该文件中的注释说明。 测试工具的使用说明已包含在工具注释中。建议你自行添加测试用例。请注意，虽然测试工具旨在模拟评测系统，但它**不是**真实的评测系统，可能存在差异。 **限制条件** - $1 \leq T \leq 30$。 **测试点 1（9 分，可见）** - $L = 10$。 - $U = 50$。 **测试点 2（16 分，隐藏）** - $10 \leq L \leq 50$。 - $L = U$。 由 ChatGPT 4.1 翻译