Parity Shuffle Sorting

题意翻译

给定一个长度为 $n$ 的数组，你可以对它进行不超过 $n$ 次操作。 对于每次操作： - 选择两个下标 $l, r$, 满足 $1\leq l<r\leq n$ - 若 $a_l + a_r $ 为奇数，将 $a_l$ 赋值为 $a_r$, 否则将 $a_r$ 赋值为 $a_l$ 求一种方案，使得操作后的数组单调不减（即 $a_1\leq a_2\leq a_3 \leq \cdots\leq a_n$ ）

题目描述

You are given an array $ a $ with $ n $ non-negative integers. You can apply the following operation on it. - Choose two indices $ l $ and $ r $ ( $ 1 \le l < r \le n $ ). - If $ a_l + a_r $ is odd, do $ a_r := a_l $ . If $ a_l + a_r $ is even, do $ a_l := a_r $ . 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. 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 $ .

输入输出格式

输入格式

The first line contains one integer $ t $ ( $ 1 \le t \le 10^5 $ ) — the number of test cases. 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. 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. It is guaranteed that the sum of $ n $ over all test cases doesn't exceed $ 10^5 $ .

输出格式

For each test case, print one integer $ m $ ( $ 0 \le m \le n $ ), the number of operations, in the first line. 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 < r_i \le n $ ). If there are multiple solutions, print any of them.

输入输出样例

输入样例 #1

3
2
7 8
5
1 1000000000 3 0 5
1
0

输出样例 #1

0
2
3 4
1 2
0

说明

In the second test case, $ a $ changes like this: - 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. - 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. In the first and third test cases, $ a $ is already non-decreasing.

题目大意：
给定一个长度为 $n$ 的非负整数数组，可以进行不超过 $n$ 次操作。每次操作选择两个下标 $l, r$（$1 \leq l < r \leq n$），如果 $a_l + a_r$ 为奇数，则将 $a_l$ 赋值为 $a_r$，否则将 $a_r$ 赋值为 $a_l$。求一种方案，使得操作后的数组单调不减（即 $a_1 \leq a_2 \leq a_3 \leq \cdots \leq a_n$）。

输入输出格式：
输入格式：
- 第一行包含一个整数 $t$（$1 \leq t \leq 10^5$）——测试用例的数量。
- 每个测试用例包含两行，第一行包含一个整数 $n$（$1 \leq n \leq 10^5$）——数组的长度。
- 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$0 \leq a_i \leq 10^9$）——数组本身。

输出格式：
- 对于每个测试用例，首先输出一行一个整数 $m$（$0 \leq m \leq n$），表示操作的数量。
- 然后输出 $m$ 行，每行包含两个整数 $l_i, r_i$，表示第 $i$ 次操作选择的下标（$1 \leq l_i < r_i \leq n$）。

输入输出样例：
输入样例 #1：
```
3
2
7 8
5
1 1000000000 3 0 5
1
0
```
输出样例 #1：
```
0
2
3 4
1 2
0
```
说明：
在第二个测试用例中，数组 $a$ 的变化如下：
- 选择下标 $3$ 和 $4$。$a_3 + a_4 = 3$ 为奇数，所以执行 $a_4 := a_3$。现在 $a = [1, 1000000000, 3, 3, 5]$。
- 选择下标 $1$ 和 $2$。$a_1 + a_2 = 1000000001$ 为奇数，所以执行 $a_2 := a_1$。现在 $a = [1, 1, 3, 3, 5]$，并且它是非递减的。

在第一个和第三个测试用例中，数组 $a$ 已经是非递减的。题目大意： 给定一个长度为 $n$ 的非负整数数组，可以进行不超过 $n$ 次操作。每次操作选择两个下标 $l, r$（$1 \leq l < r \leq n$），如果 $a_l + a_r$ 为奇数，则将 $a_l$ 赋值为 $a_r$，否则将 $a_r$ 赋值为 $a_l$。求一种方案，使得操作后的数组单调不减（即 $a_1 \leq a_2 \leq a_3 \leq \cdots \leq a_n$）。 输入输出格式： 输入格式： - 第一行包含一个整数 $t$（$1 \leq t \leq 10^5$）——测试用例的数量。 - 每个测试用例包含两行，第一行包含一个整数 $n$（$1 \leq n \leq 10^5$）——数组的长度。 - 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$0 \leq a_i \leq 10^9$）——数组本身。 输出格式： - 对于每个测试用例，首先输出一行一个整数 $m$（$0 \leq m \leq n$），表示操作的数量。 - 然后输出 $m$ 行，每行包含两个整数 $l_i, r_i$，表示第 $i$ 次操作选择的下标（$1 \leq l_i < r_i \leq n$）。 输入输出样例： 输入样例 #1： ``` 3 2 7 8 5 1 1000000000 3 0 5 1 0 ``` 输出样例 #1： ``` 0 2 3 4 1 2 0 ``` 说明： 在第二个测试用例中，数组 $a$ 的变化如下： - 选择下标 $3$ 和 $4$。$a_3 + a_4 = 3$ 为奇数，所以执行 $a_4 := a_3$。现在 $a = [1, 1000000000, 3, 3, 5]$。 - 选择下标 $1$ 和 $2$。$a_1 + a_2 = 1000000001$ 为奇数，所以执行 $a_2 := a_1$。现在 $a = [1, 1, 3, 3, 5]$，并且它是非递减的。 在第一个和第三个测试用例中，数组 $a$ 已经是非递减的。