2034D.md (2642B)
1 Source: https://codeforces.com/problemset/problem/2034/D 2 3 D. Darius' Wisdom 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 [Darius the Great](https://en.wikipedia.org/wiki/Darius_the_Great) is constructing $n$ stone columns, each consisting of a base and between $0$, $1$, or $2$ inscription pieces stacked on top. 22 23 In each move, Darius can choose two columns $u$ and $v$ such that the difference in the number of inscriptions between these columns is exactly $1$, and transfer one inscription from the column with more inscriptions to the other one. It is guaranteed that at least one column contains exactly $1$ inscription. 24 25  26 27 Since beauty is the main pillar of historical buildings, Darius wants the columns to have ascending heights. To avoid excessive workers' efforts, he asks you to plan a sequence of at most $n$ moves to arrange the columns in non-decreasing order based on the number of inscriptions. Minimizing the number of moves is not required. 28 29 Input 30 31 The first line contains an integer $t$ — the number of test cases. ($1 \leq t \leq 3000$) 32 33 The first line of each test case contains an integer $n$ — the number of stone columns. ($1 \leq n \leq 2 \cdot 10^5$) 34 35 The second line contains $n$ integers $a_1, a_2, \ldots, a_n$, where $a_i \in \{0,1,2\}$ represents the initial number of inscriptions in the $i$-th column. It is guaranteed that at least one column has exactly $1$ inscription. 36 37 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. 38 39 Output 40 41 For each test case, output an integer $k$ — the number of moves used to sort the columns. ($0 \leq k \leq n$) 42 43 Then, output $k$ lines, each containing two integers $u_i$ and $v_i$ ($1 \leq u_i, v_i \leq n$), representing the indices of the columns involved in the $i$-th move. During each move, it must hold that $|a_{u_i} - a_{v_i}| = 1$, and one inscription is transferred from the column with more inscriptions to the other. 44 45 It can be proven that a valid solution always exists under the given constraints. 46 47 Example 48 49 Input 50 51 ``` 52 3 53 54 4 55 56 0 2 0 1 57 58 3 59 60 1 2 0 61 62 6 63 64 0 1 1 2 2 2 65 ``` 66 67 Output 68 69 ``` 70 2 71 2 4 72 2 3 73 2 74 3 1 75 2 3 76 0 77 ``` 78 79 Note 80 81 Columns state in the first test case: 82 83 * Initial: $0, 2, 0, 1$ 84 * After the first move: $0, 1, 0, 2$ 85 * After the second move: $0, 0, 1, 2$ 86 87 Columns state in the second test case: 88 89 * Initial: $1, 2, 0$ 90 * After the first move: $0, 2, 1$ 91 * After the second move: $0, 1, 2$ 92 93 In the third test case, the column heights are already sorted in ascending order.