codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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.