1733C.md (1980B)
1 Source: https://codeforces.com/problemset/problem/1733/C 2 3 C. Parity Shuffle Sorting 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 You are given an array $a$ with $n$ non-negative integers. You can apply the following operation on it. 22 23 * Choose two indices $l$ and $r$ ($1 \le l \lt r \le n$). 24 * If $a_l + a_r$ is odd, do $a_r := a_l$. If $a_l + a_r$ is even, do $a_l := a_r$. 25 26 Find any sequence of at most $n$ operations that makes $a$ non-decreasing. It can be proven that it is always possible. Note that you do not have to minimize the number of operations. 27 28 An array $a_1, a_2, \ldots, a_n$ is non-decreasing if and only if $a_1 \le a_2 \le \ldots \le a_n$. 29 30 Input 31 32 The first line contains one integer $t$ ($1 \le t \le 10^5$) — the number of test cases. 33 34 Each test case consists of two lines. The first line of each test case contains one integer $n$ ($1 \le n \le 10^5$) — the length of the array. 35 36 The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^9$) — the array itself. 37 38 It is guaranteed that the sum of $n$ over all test cases doesn't exceed $10^5$. 39 40 Output 41 42 For each test case, print one integer $m$ ($0 \le m \le n$), the number of operations, in the first line. 43 44 Then print $m$ lines. Each line must contain two integers $l_i, r_i$, which are the indices you chose in the $i$-th operation ($1 \le l_i \lt r_i \le n$). 45 46 If there are multiple solutions, print any of them. 47 48 Example 49 50 Input 51 52 ``` 53 3 54 55 2 56 57 7 8 58 59 5 60 61 1 1000000000 3 0 5 62 63 1 64 65 0 66 ``` 67 68 Output 69 70 ``` 71 0 72 2 73 3 4 74 1 2 75 0 76 ``` 77 78 Note 79 80 In the second test case, $a$ changes like this: 81 82 * Select indices $3$ and $4$. $a_3 + a_4 = 3$ is odd, so do $a_4 := a_3$. $a = [1, 1000000000, 3, 3, 5]$ now. 83 * Select indices $1$ and $2$. $a_1 + a_2 = 1000000001$ is odd, so do $a_2 := a_1$. $a = [1, 1, 3, 3, 5]$ now, and it is non-decreasing. 84 85 In the first and third test cases, $a$ is already non-decreasing.