2287 「WC2017」排序

每个测试点单独评分，同时每个测试点你还有可能获得部分分。

每一个测试点总分值为 $T$ 分，每个测试点得分为其中所有测试数据的得分之和。

在每组测试数据中，若 $M \leq m$，$\text{num} \le 10^6$ ，比较器之间不会发生冲突且可以对这 $K$ 个排列正确地排序，则该测试点得 $1$ 分，否则得 $0$ 分。

如果你输出了不足 $T$ 个计算机，那么我们将默认你输出的第 $i$ 个计算机对应第 $i$ 组测试数据。

如果你的输出不符合格式要求，我们不保证你能得到该测试点的分数。

我们提供 checker 这个工具来测试你的输出文件是否是可接受的。使用这个工具的方法是，在终端中运行

./checker_linux64 input output

（32 位 Linux 用户请使用 checker_linux32，Windows 用户请使用 checker_win32.exe，其他平台可以安装 node.js 然后使用 node checker.js 运行 checker，下同）

其中 input 是给出的输入文件，output 是你的输出文件，例如

./checker_linux64 sort1.in sort1.out

将测试 sort1.out 在以 sort1.in 为输入时是否可以接受。

在你调用这个程序后，checker 将根据你给出的输出文件给出每一个测试数据的测试结果，其中包括（如果你输出的计算机同时出现了多种错误，将会返回其中一种）： 1. 非法退出：未知错误。 2. 输入文件错误：输入文件非法，在不修改输入文件的情况下不会触发。 3. The number of the comparators is invalid!：输入的比较器个数不在 $[1,10^6]$ 范围内，这时 checker 将会直接退出。 4. Unexpected EOF：输出文件中给出的计算机不完整。 5. The running time of the comparator should be in [1, 150]：你给出的比较器的运行时间不在 $[1,150]$ 范围内。 6. Invalid sorting network!：排序网络不合法，包括 $u≥\ge v$，$u<0$，比较器间产生冲突等。 7. Invalid! m=a but M=b：计算机的运行时间超过限制。 8. The answer is incorrect：排序网络合法，但是并没有将输入的排列正确排序。 9. Correct! m=a and M=b：排序网络合法且对输入的排列正确排序，此时将得到该组测试数据的分数。 10. Total points: a：如果 checker 正常运行到了最后，将会额外输出一行表示你的总得分。其中 $a$ 是你在这组数据中得到的分数。

这里给出部分数据的部分特性：

1. 测试点 $4$ 中，对于输入的每一个排列 $P$，它每一个循环的大小都互不相同。循环可以理解为，将一个长度为 $n$ 的排列 $P$ 看成一张 $n$ 个点 $n$ 条边的无向图，其中 $i$ 和 $P_i$ 之间有一条边，这张图中的每一个联通块都是一个循环。
2. 测试点 $7$ 中，对于输入的每一个排列 $P$，都存在若干个互不相交的区间 $[l_i,r_i]$，使得在对每一个区间 $[l_i,r_i]$ 循环左移一次后，数组有序。循环左移的例子为：$(1,2,3,4)$ 循环左移一步为 $(2,3,4,1)$。同时，该测试点的前 $8$ 组数据，满足对于输入的每一个排列 $P$，都存在整数 $i$，使得对区间 $[1,i]$ 循环左移一次后，数组有序。