P13024 [GCJ 2021 Qualification] Median Sort

你需要对 $\mathbf{N}$ 个互不相同的元素 $x_1$, $x_2$, $\ldots$, $x_{\mathbf{N}}$ 进行排序。但遗憾的是，你无法直接比较任意两个元素。你只能通过一种方式：给定三个元素，找出其中的中位数（即既不是最小值也不是最大值的那个元素）。 例如，假设 $\mathbf{N} = 5$，并且你知道： * $x_1$ 是 $\{x_1, x_2, x_3\}$ 的中位数 * $x_2$ 是 $\{x_2, x_3, x_4\}$ 的中位数 * $x_3$ 是 $\{x_3, x_4, x_5\}$ 的中位数 那么可以确定，元素的排序结果要么是 $x_4, x_2, x_1, x_3, x_5$，要么是其逆序 $x_5, x_3, x_1, x_2, x_4$。注意，仅通过中位数信息无法区分一个列表与其逆序，因为对于任意三个元素，中位数的结果在这两种情况下是相同的。 你的程序需要在最多 $\mathbf{Q}$ 次中位数询问的总次数内（平均每个列表 $\mathbf{Q}/\mathbf{T}$ 次询问），找出 $\mathbf{T}$ 个 $\mathbf{N}$ 元素列表的顺序。对于每个测试用例，只要给出的顺序是正确的或其逆序，都被认为是正确答案。每个测试用例的顺序是从所有可能顺序中均匀随机生成的，且与其他信息无关。 ### 交互协议 这是一个交互式问题。 初始时，评测机将发送一行包含三个整数 $\mathbf{T}$、$\mathbf{N}$ 和 $\mathbf{Q}$：分别表示测试用例的数量、每个测试用例中需要排序的元素数量，以及允许在所有测试用例中进行的总询问次数。然后，你需要处理 $\mathbf{T}$ 个测试用例。每个测试用例包含一系列询问交互以及一个额外的回答交互。 对于询问交互，你的程序需要输出一行包含三个介于 1 和 $\mathbf{N}$ 之间的不同整数 $i$、$j$、$k$，表示询问评测机"集合 $\{x_i, x_j, x_k\}$ 的中位数是哪个元素？"。评测机将回复一个整数 $\mathbf{L}$，表示该集合的中位数是 $x_{\mathbf{L}}$（$\mathbf{L}$ 总是等于 $i$、$j$ 或 $k$ 之一）。如果你尝试进行第 $(\mathbf{Q} + 1)$ 次询问，评测机将输出 -1。 当你准备好提交结果时，输出一行包含 $\mathbf{N}$ 个整数，表示元素按升序或降序排列的索引。评测机将回复一个整数 1 表示答案正确，或 -1 表示错误。在接收到第 $\mathbf{T}$ 个测试用例的评测结果后，你的程序必须及时结束以避免超时错误。此外，如果在接收到第 $\mathbf{T}$ 个测试用例的结果后继续输出，将被判为错误答案。 如果评测机在任何时候接收到格式错误或无效的值，它将输出 -1。在输出 -1 后，评测机将不再输出任何内容。如果你的程序在接收到 -1 后继续等待评测机输出，将会因超时而收到 Time Limit Exceeded 错误。注意，确保程序及时退出以避免超时错误是你的责任。如果内存超出限制或程序运行时出错，将收到相应的判定结果。

参见交互协议。

参见交互协议。

你可以使用此测试工具在本地或我们的平台上进行测试。要在本地测试，你需要同时运行工具和你的代码；可以使用我们的[交互式运行器](https://storage.googleapis.com/coding-competitions.appspot.com/interactive_runner.py)。更多信息请参阅该文件注释中的说明，并查看 FAQ 的交互式问题部分。 测试工具的说明包含在工具的注释中。我们建议你添加自己的测试用例。请注意，尽管测试工具旨在模拟评测系统，但它**并非**真实的评测系统，行为可能有所不同。 **数据范围** - $\mathbf{T} = 100$。 **测试集 1（7 分，可见判定结果）** - $\mathbf{N} = 10$。 - $\mathbf{Q} = 300 \cdot \mathbf{T}$。 **测试集 2（11 分，可见判定结果）** - $\mathbf{N} = 50$。 - $\mathbf{Q} = 300 \cdot \mathbf{T}$。 **测试集 3（10 分，隐藏判定结果）** - $\mathbf{N} = 50$。 - $\mathbf{Q} = 170 \cdot \mathbf{T}$。 翻译由 DeepSeek V3 完成