[WC2017] 排序

**本题暂时只能使用代码提交。**

牛牛最近学习了排序的相关知识。他对排序算法的运行效率产生了浓厚的兴趣并对此展开了一系列的研究。 为了优化排序的运行时间，牛牛找到了来参加冬令营的你，希望你帮助他设计一台计算机进行排序（**升序**）。 这台计算机的设计方法如下： - 需要进行排序的序列存储在大小为 $n$ 的数组 $Q$ 中。 - 进行计算的最小单元是比较器，一个比较器可以用一个三元组 $(i,j,t)$ 表示（$i,j,t$ 均为整数），其中 $1 \le i<j \le n$，$1 \le t \le m$。它的功能是：在时刻 $t$ 比较 $Q_{i}$ 与 $Q_{j}$ 的大小，若 $Q_{i}>Q_{j}$，就交换 $Q_{i}$ 与 $Q_{j}$ 的值，否则什么也不做。 - 若要让计算机**工作**（**但不一定解决问题**），则需要任意两个比较器之间**不能发生冲突**。两个比较器 $(A,B,S)$ 与 $(C,D,T)$ **会发生冲突**当且仅当 $A,B,C,D$ 中有**至少两个相等的数**，**并且** $S=T$。例如：比较器 $(1,3,1)$ 和 $(2,4,1)$ 不会发生冲突，而比较器 $(1,2,3)$ 和 $(2,3,3)$ 会发生冲突。 在运行时，这台计算机中的每个比较器都会按照预先设定好的参数在指定的时间进行相应的操作。这台计算机运行时需要消耗的时间为所有的比较器中参数 $t$ 的**最大值** $w$，该值越小意味着运行时间越短。 为了检验你设计的计算机，牛牛提供了测试数据。**每组测试数据**包含 $q$ 个**问题**，即 $q$ 个长度为 $n$ 的排列 $P$。请你为**每组测试数据**设计一台运行时间不超过 $m$ 的计算机（否则计算机将**超时**），使得这台计算机能对**测试数据中所有的** $P$ 排序。

为了方便你区分不同的子任务，每个输入文件第一行为一个整数 $I$，表示当前测试点的编号。 第二行一个整数 $J$ 表示**这个测试点**中的**测试数据**组数。 **每组测试数据**第一行三个整数 $q,n,m$。 接下来 $q$ 行每行 $n$ 个整数，描述一个 $1$ 到 $n$ 的排列 $P$。 **数据保证有解。**

对于**每组测试数据**，第一行输出一个整数 $f$ 表示你设计的计算机中比较器个数。 接下来 $f$ 行，每行 $3$ 个整数 $i,j,t$，描述你的计算机的一个比较器 $(i,j,t)$。 若 $i,j \notin [1,n]$，则计算机**不能工作**。

0
1
3 5 4
1 2 5 3 4
3 4 5 1 2
3 1 4 2 5

7
1 2 1
3 4 1
2 3 2
4 5 2
1 2 3
3 4 3
2 3 4

### 输入数据及 checker 下载 在[这里](http://pan.baidu.com/s/1miBgJ3q)下载。 **警告：所有数据（包括 SPJ）均为 Windows（64 位）格式。** ### 关于 UKE 的问题 由于本题 SPJ 的时间复杂度较高，请用比较器个数尽量少的方案来通过该题，否则可能出现 SPJ TLE 的问题，导致评测结果为 UKE。 SPJ 的时间复杂度为： $$O\left ( \sum_{i=1}^{J}q_i\times (n_i+f_i) \right )$$ ### 评分方式 共 $8$ 个**测试点**，分别有 $6,12,13,10,10,10,19,20$ 组**测试数据**，共 $100$ 组，**每组测试数据满分 $1$ 分。** 在**每组测试数据**中，若 $1 \le w\le m$ 且 $f\le 10^{6}$，比较器之间不会发生冲突，计算机能对**测试数据中所有的** $P$ 排序，则该**测试数据**得分，否则不得分。 如果你输出了不足 $J$ 个计算机，那么我们将默认你输出的第 $i$ 个计算机对应第 $i$ 组测试数据。 如果你的输出不符合格式要求，我们不保证你能得到该测试点的分数。 ### 数据特性 对于 $100\%$ 的数据，$1 \le m \le 150$，$J \in \{1,6,10,12,13,19,20\}$，$0 \le I \le 8$，其余请自行下载数据查看。 这里给出部分数据的部分特性： - **测试点 $4$（$10$ 分）** 中，对于输入的每一个排列 $P$，它每一个环的大小都互不相同。循环可以理解为，将一个长度为 $n$ 的排列 $P$ 看成一张 $n$ 个点 $n$ 条边的无向图（**基环森林**），其中 $i$ 号点和 $P_{i}$ 号点之间有一条边，这张图中的**每一个联通块都是一个环**（**即该图由若干个环组成**），如 $P=\{\color{blue}1,\color{green}3,2,\color{purple}6,\color{red}10,\color{purple}7,4,\color{red}5,8,9\color{black}\}$（**每个颜色代表一个环**）。 - **测试点 $7$（$19$ 分）** 中，对于输入的每一个排列 $P$，都存在若干个互不相交的区间 $[l_i,r_i]$，使得在对每一个区间 $[l_i,r_i]$ 循环左移一次后，数组有序，如 $P=\{\color{blue}3,1,2,\color{green}7,4,5,6,\color{purple}8,\color{red}9\color{black}\}$（**每个颜色代表一个区间**）。循环左移的例子为：$(1,2,3,4)$ 循环左移一步为 $(2,3,4,1)$。 - **测试点 $7$ 的前 $8$ 组测试数据（$8$ 分）** 中，满足对于输入的每一个排列 $P$，都存在整数 $i$，使得对区间 $[1,i]$ 循环左移一次后，数组有序，如 $P=\{\color{red}5,1,2,3,4\color{black},6,7,8\}$。 ### 测试你的输出 我们在文件中提供了 `checker`（**Windows x64**）来检测你的输出的得分，使用这个工具的方法为： `checker.exe sort<I>.in sort<I>.out sort<I>.out` 其中 $I$ 为**测试点**编号（**输入时不带尖括号**），`checker.exe` 为校验器，`sort<I>.in` 为题目提供的输入文件，`sort<I>.out` 为你的对应的输出文件（**输入两遍**）。运行此命令将给出以 `sort<I>.in` 为输入文件，以 `sort<I>.out` 为输出文件时你的得分情况。 在你调用这个程序后，`checker` 将根据你给出的输出文件给出每一个**测试数据**的测试结果，其中包括（如果你输出的计算机同时出现了多种错误，将会返回其中一种）： | 测试结果 | 含义 | | :----------- | :----------- | | `FAIL!` | 未知错误：SPJ 运行失败。 | | `Input error!` | 输入文件非法：你改动了输入文件。 | | `The number of the comparators is invalid!` | 检测到 $f>10^6$。 | | `Unexpected EOF` | 给出的计算机不完整。 | | `The running time of the comparator should be in [1, 150]` | 检测到 $w \notin [1,150]$。 | | `Invalid sorting network!` | 给出的计算机不能工作。 | | `The answer is incorrect` | 给出的计算机不能解决所有问题。 | | `Invalid! m=(X) but M=(X)` | 给出的计算机超时：$w=Y,m=X$（$Y>X$）。 | | `Correct! m=(X) and M=(X)` | 给出的计算机正确：$w=Y,m=X$（$Y\le X$）。 | 最后，如果 `checker` 正常运行到了最后，将会额外输出一行 `Total points: (Z)`，表示你在**这个测试点**一共得了 $Z$ 分。 ### 提醒 **请注意「测试点」、「测试数据」和「问题」的区别！** **请牢记下面的图示：** - 整道题目 - 测试点 $1$ - 测试数据 $1.1$ - 问题 $1.1.1$ - 测试数据 $1.2$ - 问题 $1.2.1$ - 测试数据 $1.3$ - 问题 $1.3.1$ - 问题 $1.3.2$ - …… - 问题 $1.3.5$ - …… - 测试数据 $1.6$ - 测试点 $2$ - …… - 测试点 $8$