P3782 [WC2017] Sorting

This problem currently only allows code submissions.

Niuniu has recently learned about sorting and has become very interested in the efficiency of sorting algorithms. To optimize sorting time, Niuniu turned to you at the winter camp to help design a computer to perform sorting (ascending). The computer is designed as follows: - The sequence to be sorted is stored in an array $Q$ of size $n$. - The smallest unit of computation is a comparator, represented by a triple $(i, j, t)$ (all integers), where $1 \le i < j \le n$, $1 \le t \le m$. Its function is: at time $t$, compare $Q_{i}$ and $Q_{j}$. If $Q_{i} > Q_{j}$, swap $Q_{i}$ and $Q_{j}$; otherwise do nothing. - For the computer to work (but not necessarily solve the problem), any two comparators must not conflict. Two comparators $(A, B, S)$ and $(C, D, T)$ conflict if and only if at least two numbers among $A, B, C, D$ are equal and $S = T$. For example, comparators $(1, 3, 1)$ and $(2, 4, 1)$ do not conflict, while $(1, 2, 3)$ and $(2, 3, 3)$ do conflict. At runtime, each comparator in the computer performs its operation at its preset time. The running time of the computer is the maximum value $w$ of parameter $t$ among all comparators; the smaller this value, the shorter the running time. To test your computer design, Niuniu provides testdata. Each group of testdata contains $q$ queries, i.e., $q$ permutations $P$ of length $n$. For each group of testdata, please design a computer with running time at most $m$ (otherwise the computer will time out) that can sort all $P$ in the testdata.

To help you distinguish sub-tasks, each input file begins with an integer $I$, the current test point index. The second line contains an integer $J$, the number of testdata groups in this test point. For each group of testdata, the first line contains three integers $q, n, m$. Then follow $q$ lines, each containing $n$ integers describing a permutation $P$ of $1$ to $n$. It is guaranteed that a solution exists.

For each group of testdata, output an integer $f$ in the first line, the number of comparators in your computer. Then output $f$ lines, each with $3$ integers $i, j, t$, describing a comparator $(i, j, t)$ of your computer. If $i, j \notin [1, n]$, then the computer cannot work.

### Download input data and checker Download from [here](http://pan.baidu.com/s/1miBgJ3q). Warning: All files (including the SPJ) are in Windows (64-bit) format. ### About the UKE issue Because the SPJ has high time complexity, please use as few comparators as possible. Otherwise the SPJ may TLE, causing the verdict to be UKE. The SPJ time complexity is: $$O\left ( \sum_{i=1}^{J}q_i\times (n_i+f_i) \right )$$ ### Scoring There are 8 test points with $6, 12, 13, 10, 10, 10, 19, 20$ groups of testdata respectively, 100 groups in total, and each group of testdata is worth 1 point. In each group of testdata, if $1 \le w \le m$ and $f \le 10^{6}$, the comparators do not conflict, and the computer can sort all $P$ in the testdata, then that testdata scores; otherwise it scores 0. If you output fewer than $J$ computers, we assume your $i$-th computer corresponds to the $i$-th group of testdata. If your output format is invalid, we do not guarantee you can get points for that test point. ### Data characteristics For $100\%$ of the data, $1 \le m \le 150$, $J \in \{1, 6, 10, 12, 13, 19, 20\}$, $0 \le I \le 8$. See the downloadable data for the rest. Some partial characteristics: - Test point $4$ (10 points): For every input permutation $P$, all its cycle sizes are pairwise distinct. You can think of a permutation $P$ of length $n$ as an undirected graph with $n$ nodes and $n$ edges (a functional graph consisting only of cycles), where there is an edge between node $i$ and node $P_{i}$. Every connected component in this graph is a cycle (i.e., the graph consists of several cycles), e.g., $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}\}$ (each color indicates a cycle). - Test point $7$ (19 points): For every input permutation $P$, there exist several pairwise disjoint intervals $[l_i, r_i]$ such that after rotating each interval $[l_i, r_i]$ left by one step, the array becomes sorted, e.g., $P=\{\color{blue}3,1,2,\color{green}7,4,5,6,\color{purple}8,\color{red}9\color{black}\}$ (each color indicates an interval). Example of a left cyclic shift: $(1, 2, 3, 4)$ rotated left by one step becomes $(2, 3, 4, 1)$. - In the first 8 groups of testdata of test point $7$ (8 points), for every input permutation $P$, there exists an integer $i$ such that after rotating the interval $[1, i]$ left by one step, the array becomes sorted, e.g., $P=\{\color{red}5,1,2,3,4\color{black},6,7,8\}$. ### Test your output We provide a checker (Windows x64) in the files to evaluate your output. Usage: `checker.exe sort.in sort.out sort.out` Here $I$ is the test point index (do not include angle brackets in the input), `checker.exe` is the checker, `sort.in` is the provided input file, and `sort.out` is your corresponding output file (input twice). Running this command will show your score on the input file `sort.in` with your output file `sort.out`. After you invoke the program, the checker prints the result for each group of testdata, including (if multiple errors occur simultaneously, one of them is reported): | Result | Meaning | | :----------- | :----------- | | `FAIL!` | Unknown error: SPJ runtime failure. | | `Input error!` | Invalid input file: you modified the input. | | `The number of the comparators is invalid!` | Detected $f>10^6$. | | `Unexpected EOF` | The computer you provided is incomplete. | | `The running time of the comparator should be in [1, 150]` | Detected $w \notin [1, 150]$. | | `Invalid sorting network!` | The computer you provided cannot work. | | `The answer is incorrect` | The computer you provided cannot solve all queries. | | `Invalid! m=(X) but M=(X)` | The computer timed out: $w=Y, m=X$ ($Y>X$). | | `Correct! m=(X) and M=(X)` | The computer is correct: $w=Y, m=X$ ($Y \le X$). | Finally, if the checker finishes normally, it additionally prints `Total points: (Z)`, which is the total points you scored on this test point. ### Reminder Please pay attention to the difference between “test point”, “testdata”, and “query”. Please keep in mind the structure below: - The whole problem - Test point $1$ - Testdata $1.1$ - Query $1.1.1$ - Testdata $1.2$ - Query $1.2.1$ - Testdata $1.3$ - Query $1.3.1$ - Query $1.3.2$ - … - Query $1.3.5$ - … - Testdata $1.6$ - Test point $2$ - … - Test point $8$ Translated by ChatGPT 5