P16546 [EGOI 2026] 座位安排 / Seating Plan

EGOI 闭幕式马上就要到了，将有 $N$ 位重要宾客出席。他们需要按照非常严格的外交协议，排成一排坐好。Noemi 为了确定正确的座位顺序，熬了两个通宵。 Veronica 是这次闭幕式的负责人，她得确保前排的座位名牌是正确的。但有个小麻烦：Noemi 没有告诉她正确的座位顺序，而且人也找不到了。好在摄影师 Dorka 有个能派上用场的 App。 Dorka 需要调整相机，以便给前排的宾客拍特定的照片。为了调试设备，她需要知道每张照片会覆盖多大的范围，所以 Noemi 给她写了个 App，能快速输出她需要的信息。Veronica 现在想用这个 App 来找出正确的座位安排。 这 $N$ 位重要宾客编号从 $0$ 到 $N-1$。前排的座位也从左到右编号为 $0$ 到 $N-1$。对于每个 $I$ ($0 \leq I \leq N-1$)，$g_I$ 表示坐在座位 $I$ 上的宾客编号，$s_I$ 表示宾客 $I$ 应该坐的座位编号。 :::align{center}  一排五个宾客。对于这一排，$g = [3, 1, 0, 2, 4]$ 且 $s = [2, 1, 3, 0, 4]$。 ::: 这个 App 的工作方式如下： - Dorka 输入三个不同宾客的编号 $I$、$J$、$K$。 - App 会告诉她，如果非要把这三位宾客都拍进照片里，照片里至少会出现多少位宾客。形式化地说，App 会显示 $\max(s_I, s_J, s_K) - \min(s_I, s_J, s_K) + 1$ 的值。 举个例子，看看图 1： - 宾客 $I=0$、$J=2$ 和 $K=4$ 坐在位置 $s_I = 2$、$s_J = 3$ 和 $s_K = 4$ 上。如果 Dorka 选择了他们，App 会显示 $\max(2,3,4) - \min(2,3,4) + 1 = 3$。 换句话说，包含宾客 $0$、$2$ 和 $4$ 的最窄照片里，刚好只有这三位宾客。 - 宾客 $I=0$、$J=4$ 和 $K=3$ 坐在位置 $s_I = 2$、$s_J = 4$ 和 $s_K = 0$ 上。如果 Dorka 选择了他们，App 会显示 $\max(2,4,0) - \min(2,4,0) + 1 = 5$。 换句话说，包含这三位宾客的照片必须覆盖所有 $5$ 位宾客。 帮 Veronica 用 Dorka 的 App 找出正确的座位顺序。 具体来说，你的程序需要确定并输出序列 $g_0, g_1, \dots, g_{N-1}$。总共有两个正确的答案（一个是另一个的逆序），你可以输出其中任意一个。你的得分取决于你向 App 查询的次数。 ### 实现详情 这是一个交互题。你的程序将通过标准输入和输出与评测程序进行交互，格式如下所述。 你的程序应该首先输入一行，包含一个正整数 $T$，表示测试数据的数量。 对于每个测试数据，你的程序应该先输入一行，包含一个正整数 $N$，即座位的数量（也是宾客的数量）。 如果要进行查询，你的程序应该输出一行 "? $I$ $J$ $K$"，其中 $0 \leq I, J, K \leq N - 1$ 是三个**不同**的数字。 查询后，你的程序应该输入一行，包含一个正整数，即查询的答案。 如果要输出正确的座位顺序，你的程序应该输出一行 "! $g_0$ ... $g_{N-1}$"。 处理完所有 $T$ 个测试数据后，程序应正常终止。 请注意，CMS 中使用的官方评测机可能是 **自适应的（adaptive）**。这意味着，对于某些测试用例，嘉宾的排列顺序并不是提前定好的。相反，评测机可能会根据你的程序已经问出的查询，来决定使用剩余排列中的哪一种。 **刷新缓冲区。** 如果你没有使用提供的模板，请确保在输出每一行后刷新标准输出，否则你的程序可能会被判定为 Not correct。在 Python 中，如果你使用 `input()` 输入行，这会自动完成，你可以使用 `print(..., flush=True)` 来强制刷新。在 C++ 中，`cout

无

无

### 约束条件 - $1 \leq T \leq 10$。 - $N$ 为 $5$（只有样例符合）、$8$、$40$ 或 $2000$。 - 对于每个测试数据，你最多可以进行 $10\ 000$ 次查询。 ### 评分方式 你的程序将在分成若干子任务的测试数据上进行测试。 要获得某个子任务的分数，你必须正确解出该子任务中所有的测试数据。 - **子任务 $0$** [$0$ 分]: 样例 ($N = 5$)。 - **子任务 $1$** [$9$ 分]: $N = 8$。 - **子任务 $2$** [$11$ 分]: $N = 2000$，且宾客 $0$ 和 $1$ 坐在一起。 - **子任务 $3$** [$15$ 分]: $N = 40$。 - **子任务 $4$** [$65$ 分]: $N = 2000$。 对于子任务 1 和 2，任何能正确解决所有测试数据的解法都将获得全部分数。 对于子任务 3 和 4，你的解法必须正确解决所有测试数据才能得分，且你的得分取决于 $Q_s$，即你解决一个测试数据所需的最大查询次数。设 $X_s = max( 1, Q_s / N )$。子任务 3 和 4 的得分计算如下： $$ score_3 = \min( 15, 3 + \frac{19}{X_s^{1.5}} ), $$ $$ score_4 = \min( 65, 3 + \frac{91}{X_s^{1.5}} ) $$ 对于每个子任务，$score_s$ 的值四舍五入到最接近的整数，总分是各子任务得分之和。为了获得满分，你需要在子任务 3 中最多使用 55 次查询，在子任务 4 中最多使用 2597 次查询。子任务 3 和 4 的 $Q_s$ 样例值及对应得分如下表所示。 :::align{center}  ::: ### 样例解释 样例输入包含一个测试数据 ($T = 1$)，其中 $N = 5$ 位宾客。此测试数据中的隐藏宾客配置对应于图 1。 程序进行的第一次查询是 0, 2, 4。该查询的答案 3 告诉我们，这些宾客以某种未知顺序坐在三个相邻的座位上。 第二个查询的答案 3 告诉我们关于宾客 3、0 和 1 也是如此。 我们现在可以推断出宾客 0 一定坐在中间，宾客 2 和 4 在一侧，宾客 1 和 3 在另一侧。 第三次查询后，我们已经确定宾客一定以 $[3, 1, 0, 2, 4]$ 的顺序或反向顺序 $[4, 2, 0, 1, 3]$ 就座。我们可以输出这两种顺序中的任意一种。 ### 代码模板和评测详情 我们强烈建议使用提供的 C++ 和 Python 代码模板。这些模板会检查与评测程序的交互是否成功，并在交互失败时优雅地终止程序。 与你程序交互的评测程序在遇到第一个错误时会进行报错，然后终止。如果你不使用提供的模板，这可能会导致你的程序崩溃或一直等待响应。 我们也建议使用测试工具（见下文）在提交前进行本地测试。测试工具会检查你程序的输出并报告协议违规情况（protocol violations）。 ### 测试工具 为了方便你测试程序，我们提供了一个可以下载的简单工具。该工具是可选的。注意，洛谷使用的评测程序与测试工具不同。 要使用该工具，你需要一个输入文件。你可以使用提供的样例输入 `seatingplan.input0.txt` 或者自己创建一个。输入文件应以包含测试数据数量 $T$ 的行开头，然后每个测试数据占用两行：一行包含 $N$，另一行包含 $g_0, g_1, ..., g_{N-1}$。 对于 Python 程序，假设为 `seatingplan.py`（通常以 `pypy3 seatingplan.py` 运行），按如下方式运行测试工具： ``` python3 testing_tool.py pypy3 seatingplan.py < seatingplan.input0.txt ``` 对于 C++ 程序，先编译你的程序： ``` g++ -DEVAL -std=gnu++20 -O2 -pipe -static -s -o seatingplan seatingplan.cpp ``` 然后运行测试工具： ``` python3 testing_tool.py ./seatingplan < seatingplan.input0.txt ```