P13035 [GCJ 2021 #2] Minimum Sort

在这个问题中，你需要将一个包含 $N = 100$ 个不同整数的列表按严格递增的顺序排序。你可以通过交换任意两个位置的内容来重新排列列表（这两个位置不需要相邻）。但遗憾的是，你无法直接读取这些内容。你可以通过查询区间最小值来获取列表内容的信息。最小值查询会给出一个连续位置区间内最小值所在的位置。例如，在列表 $[51, 33, 100, 11]$ 中，位置 2 到 4（基于 1 的索引）的最小值位于位置 4，而位置 1 到 3 的最小值位于位置 2。 关于区间最小值的查询受到每个测试用例的硬币预算限制。更大的区间更便宜：查询位置 $i$ 到 $j$（$i < j$）的最小值位置需要花费 $\lceil 10^8 / (j - i + 1) \rceil$ 枚硬币，其中 $\lceil x \rceil$ 表示大于或等于 $x$ 的最小整数（即 $x$ 向上取整）。而交换操作不消耗任何硬币。 编写一个程序，使用任意次数的交换操作和最多 $6 \times 10^8$ 枚硬币（每个测试用例中分配到任意数量的最小值查询）对整数列表进行排序。 ### 交互协议 这是一个交互式问题。 最初，评测机会发送一行包含两个整数 $\mathbf{T}$ 和 $\mathbf{N}$：分别是测试用例的数量和每个测试用例中需要排序的元素数量。评测机在收到你的程序的任何输入之前已经预设了初始列表，并且在与你程序的交互过程中，列表的唯一变化是你请求的交换操作。 然后，你需要处理 $\mathbf{T}$ 个测试用例。每个测试用例由一系列交互加上一行表示完成的指令组成。每次交互由你打印一行和评测机打印一行响应组成。你的程序必须打印以下选项之一的一行内容： - 一个大写字母 $\mathbf{M}$ 和两个整数 $i$ 和 $j$（$i < j$），表示一个最小值查询。评测机会响应一个整数，表示基于 1 的索引中位置 $i$ 到 $j$（包含）区间内最小值的位置。 - 一个大写字母 $\mathbf{S}$ 和两个整数 $i$ 和 $j$（$i < j$），表示一个交换操作。评测机会交换基于 1 的索引中位置 $i$ 和 $j$ 的两个元素，并响应 1。 - 一个大写字母 $\mathbf{D}$，表示你已完成列表的排序。评测机会检查列表。如果列表已按严格递增顺序排序，则响应 1；否则响应 -1。 当评测机对 $\mathbf{D}$ 响应 1 后，如果是最后一个测试用例，评测机会结束；否则会立即开始等待你对下一个测试用例的第一条指令。在收到第 $\mathbf{T}$ 个测试用例的响应后，你的程序必须结束，否则会收到“超出时间限制”错误。 如果评测机在任何时候收到格式无效的行或无效的值（包括最小值查询的硬币成本超过了当前测试用例的剩余预算），评测机会打印一个数字 -1。在评测机因上述任何原因打印 -1 后，它将不再输出任何内容。如果你的程序在收到 -1 后继续等待评测机的响应，你的程序将因超时而收到“超出时间限制”错误。请注意，你的程序有责任及时退出以避免收到“超出时间限制”错误，而应收到“答案错误”的判定。与往常一样，如果超出内存限制或程序出现运行时错误，你将收到相应的判定。

参见交互协议。

参见交互协议。

你可以使用此测试工具在本地或我们的平台上进行测试。要在本地测试，你需要同时运行该工具和你的代码；你可以使用我们的[交互式运行器](https://storage.googleapis.com/coding-competitions.appspot.com/interactive_runner.py)来实现。 测试工具的说明包含在工具的注释中。我们鼓励你添加自己的测试用例。请注意，尽管该测试工具旨在模拟评测系统，但它**并非**真实的评测系统，可能会表现出不同的行为。 **限制** **测试集 1（15 分，可见判定）** - $\mathbf{T} = 100$。 - $\mathbf{N} = 100$。 翻译由 DeepSeek V3 完成