#216579. [EGOI 2026] 座位安排 / Seating Plan

EGOI 闭幕式马上就要到了，将有 位重要宾客出席。他们需要按照非常严格的外交协议，排成一排坐好。Noemi 为了确定正确的座位顺序，熬了两个通宵。

Veronica 是这次闭幕式的负责人，她得确保前排的座位名牌是正确的。但有个小麻烦：Noemi 没有告诉她正确的座位顺序，而且人也找不到了。好在摄影师 Dorka 有个能派上用场的 App。

Dorka 需要调整相机，以便给前排的宾客拍特定的照片。为了调试设备，她需要知道每张照片会覆盖多大的范围，所以 Noemi 给她写了个 App，能快速输出她需要的信息。Veronica 现在想用这个 App 来找出正确的座位安排。

这 位重要宾客编号从 到 。前排的座位也从左到右编号为 到 。对于每个 ()， 表示坐在座位 上的宾客编号， 表示宾客 应该坐的座位编号。

:::align{center}

一排五个宾客。对于这一排， 且 。 :::

这个 App 的工作方式如下：

• Dorka 输入三个不同宾客的编号 、、。
• App 会告诉她，如果非要把这三位宾客都拍进照片里，照片里至少会出现多少位宾客。形式化地说，App 会显示 的值。

举个例子，看看图 1：

• 宾客 、 和 坐在位置 、 和 上。如果 Dorka 选择了他们，App 会显示 。

  换句话说，包含宾客 、 和 的最窄照片里，刚好只有这三位宾客。

• 宾客 、 和 坐在位置 、 和 上。如果 Dorka 选择了他们，App 会显示 。

  换句话说，包含这三位宾客的照片必须覆盖所有 位宾客。

帮 Veronica 用 Dorka 的 App 找出正确的座位顺序。 具体来说，你的程序需要确定并输出序列 。总共有两个正确的答案（一个是另一个的逆序），你可以输出其中任意一个。你的得分取决于你向 App 查询的次数。

实现详情

这是一个交互题。你的程序将通过标准输入和输出与评测程序进行交互，格式如下所述。

你的程序应该首先输入一行，包含一个正整数 ，表示测试数据的数量。

对于每个测试数据，你的程序应该先输入一行，包含一个正整数 ，即座位的数量（也是宾客的数量）。

如果要进行查询，你的程序应该输出一行 "? "，其中 是三个不同的数字。

查询后，你的程序应该输入一行，包含一个正整数，即查询的答案。

如果要输出正确的座位顺序，你的程序应该输出一行 "! ... "。

处理完所有 个测试数据后，程序应正常终止。

请注意，CMS 中使用的官方评测机可能是 自适应的（adaptive）。这意味着，对于某些测试用例，嘉宾的排列顺序并不是提前定好的。相反，评测机可能会根据你的程序已经问出的查询，来决定使用剩余排列中的哪一种。

刷新缓冲区。 如果你没有使用提供的模板，请确保在输出每一行后刷新标准输出，否则你的程序可能会被判定为 Not correct。在 Python 中，如果你使用 input() 输入行，这会自动完成，你可以使用 print(..., flush=True) 来强制刷新。在 C++ 中，cout << endl; 在输出换行符之外还会进行刷新；如果使用 printf，请使用 fflush(stdout)。

样例输入 1

1
5

3

3

5

样例输出 1

? 0 2 4

? 3 0 1

? 0 4 3

! 3 1 0 2 4

约束条件

• 。
• 为 （只有样例符合）、、 或 。
• 对于每个测试数据，你最多可以进行 次查询。

评分方式

你的程序将在分成若干子任务的测试数据上进行测试。 要获得某个子任务的分数，你必须正确解出该子任务中所有的测试数据。

• 子任务 [ 分]: 样例 ()。
• 子任务 [ 分]: 。
• 子任务 [ 分]: ，且宾客 和 坐在一起。
• 子任务 [ 分]: 。
• 子任务 [ 分]: 。

对于子任务 1 和 2，任何能正确解决所有测试数据的解法都将获得全部分数。

对于子任务 3 和 4，你的解法必须正确解决所有测试数据才能得分，且你的得分取决于 ，即你解决一个测试数据所需的最大查询次数。设 。子任务 3 和 4 的得分计算如下：

对于每个子任务， 的值四舍五入到最接近的整数，总分是各子任务得分之和。为了获得满分，你需要在子任务 3 中最多使用 55 次查询，在子任务 4 中最多使用 2597 次查询。子任务 3 和 4 的 样例值及对应得分如下表所示。

:::align{center} :::

样例解释

样例输入包含一个测试数据 ()，其中 位宾客。此测试数据中的隐藏宾客配置对应于图 1。

程序进行的第一次查询是 0, 2, 4。该查询的答案 3 告诉我们，这些宾客以某种未知顺序坐在三个相邻的座位上。

第二个查询的答案 3 告诉我们关于宾客 3、0 和 1 也是如此。

我们现在可以推断出宾客 0 一定坐在中间，宾客 2 和 4 在一侧，宾客 1 和 3 在另一侧。

第三次查询后，我们已经确定宾客一定以 的顺序或反向顺序 就座。我们可以输出这两种顺序中的任意一种。

代码模板和评测详情

我们强烈建议使用提供的 C++ 和 Python 代码模板。这些模板会检查与评测程序的交互是否成功，并在交互失败时优雅地终止程序。

与你程序交互的评测程序在遇到第一个错误时会进行报错，然后终止。如果你不使用提供的模板，这可能会导致你的程序崩溃或一直等待响应。

我们也建议使用测试工具（见下文）在提交前进行本地测试。测试工具会检查你程序的输出并报告协议违规情况（protocol violations）。

测试工具

为了方便你测试程序，我们提供了一个可以下载的简单工具。该工具是可选的。注意，洛谷使用的评测程序与测试工具不同。

要使用该工具，你需要一个输入文件。你可以使用提供的样例输入 seatingplan.input0.txt 或者自己创建一个。输入文件应以包含测试数据数量 的行开头，然后每个测试数据占用两行：一行包含 ，另一行包含 。

对于 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