310556: CF1851B. Parity Sort
Description
You have an array of integers $a$ of length $n$. You can apply the following operation to the given array:
- Swap two elements $a_i$ and $a_j$ such that $i \neq j$, $a_i$ and $a_j$ are either both even or both odd.
Determine whether it is possible to sort the array in non-decreasing order by performing the operation any number of times (possibly zero).
For example, let $a$ = [$7, 10, 1, 3, 2$]. Then we can perform $3$ operations to sort the array:
- Swap $a_3 = 1$ and $a_1 = 7$, since $1$ and $7$ are odd. We get $a$ = [$1, 10, 7, 3, 2$];
- Swap $a_2 = 10$ and $a_5 = 2$, since $10$ and $2$ are even. We get $a$ = [$1, 2, 7, 3, 10$];
- Swap $a_4 = 3$ and $a_3 = 7$, since $3$ and $7$ are odd. We get $a$ = [$1, 2, 3, 7, 10$].
The first line of input data contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.
The description of the test cases follows.
The first line of each test case contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the length of array $a$.
The second line of each test case contains exactly $n$ positive integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$) — the elements of array $a$.
It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
OutputFor each test case, output on a separate line:
- YES if the array can be sorted by applying the operation to it some number of times;
- NO otherwise.
You can output YES and NO in any case (for example, strings yEs, yes, Yes and YES will be recognized as positive response).
ExampleInput6 5 7 10 1 3 2 4 11 9 3 5 5 11 3 15 3 2 6 10 7 8 1 2 3 1 10 5 6 6 4 1 6Output
YES YES NO NO YES NONote
The first test case is explained in the problem statement.
Input
题意翻译
有一个长度为 $n$的整数数组 $a$。你可以对给定的数组进行以下操作： - 将两个元素$a_i$和$a_j$对调，使得$i \neq j$、$a_i$和$a_j$要么**都是偶数，要么**都是奇数。 确定是否有可能通过执行任意次数（可能为零）的操作对数组进行非递减排序。 例如，让 $a$ = \[$7, 10, 1, 3, 2$\]。那么我们可以执行 $3$ 次操作对数组进行排序： 1. 交换 $a_3 = 1$和 $a_1 = 7$，因为 $1$和 $7$都是奇数。我们得到 $a$ = \[$1, 10, 7, 3, 2$/]； 2. 交换$a_2 = 10$和$a_5 = 2$，因为$10$和$2$是偶数。我们得到 $a$ = \[$1, 2, 7, 3, 10$\]； 3. 交换$a_4 = 3$和$a_3 = 7$，因为$3$和$7$是奇数。我们得到 $a$ = \[$1, 2, 3, 7, 10$/]。 **输入** 第一行输入数据包含一个整数 $t$（$1 \le t \le 10^4$）--测试用例数。 测试用例说明如下。 每个测试用例的第一行包含一个整数$n$（$1 \le n \le 2 \cdot 10^5$）--数组$a$的长度。 每个测试用例的第二行正好包含 $n$个正整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$）--在数组 $a$的元素。 保证所有测试用例的 $n$之和不超过 $2 \cdot 10^5$。 **输出** 每个测试用例的输出都单独成行： - 如果数组可以通过一定次数的操作进行排序，则 "是"； - 否则为 "否"。 您可以在任何情况下输出 YES 和 NO（例如，字符串 yEs、yes、Yes 和 YES 将被识别为积极响应）。 **注** 第一个测试案例已在问题陈述中说明。Output
输入数据格式：第一行输入一个整数 `t`（`1 ≤ t ≤ 10^4`），表示测试用例的数量。接下来每个测试用例的描述如下：第一行输入一个整数 `n`（`1 ≤ n ≤ 2 × 10^5`），表示数组 `a` 的长度。第二行输入 `n` 个正整数 `a_1, a_2, ..., a_n`（`1 ≤ a_i ≤ 10^9`），表示数组 `a` 的元素。所有测试用例的 `n` 之和不超过 `2 × 10^5`。
输出数据格式：对于每个测试用例，输出一行结果：如果可以通过执行操作将数组排序，则输出 `YES`；否则输出 `NO`。`YES` 和 `NO` 的大小写不敏感。
例如，对于数组 `a = [7, 10, 1, 3, 2]`，可以通过执行 3 次操作来排序数组：1. 交换 `a_3 = 1` 和 `a_1 = 7`，得到 `a = [1, 10, 7, 3, 2]`；2. 交换 `a_2 = 10` 和 `a_5 = 2`，得到 `a = [1, 2, 7, 3, 10]`；3. 交换 `a_4 = 3` 和 `a_3 = 7`，得到 `a = [1, 2, 3, 7, 10]`。
示例输入：
```
6
5
7 10 1 3 2
4
11 9 3 5
5
11 3 15 3 2
6
10 7 8 1 2 3
1
10
5
6 6 4 1 6
```
示例输出：
```
YES
YES
NO
NO
YES
NO
```题目大意：给定一个整数数组 `a`，其长度为 `n`。你可以对数组执行以下操作任意次（可能为零次）：交换两个元素 `a_i` 和 `a_j`（其中 `i != j`），且 `a_i` 和 `a_j` 要么都是偶数，要么都是奇数。确定是否可以通过执行该操作将数组按非递减顺序排序。 输入数据格式：第一行输入一个整数 `t`（`1 ≤ t ≤ 10^4`），表示测试用例的数量。接下来每个测试用例的描述如下：第一行输入一个整数 `n`（`1 ≤ n ≤ 2 × 10^5`），表示数组 `a` 的长度。第二行输入 `n` 个正整数 `a_1, a_2, ..., a_n`（`1 ≤ a_i ≤ 10^9`），表示数组 `a` 的元素。所有测试用例的 `n` 之和不超过 `2 × 10^5`。 输出数据格式：对于每个测试用例，输出一行结果：如果可以通过执行操作将数组排序，则输出 `YES`；否则输出 `NO`。`YES` 和 `NO` 的大小写不敏感。 例如，对于数组 `a = [7, 10, 1, 3, 2]`，可以通过执行 3 次操作来排序数组：1. 交换 `a_3 = 1` 和 `a_1 = 7`，得到 `a = [1, 10, 7, 3, 2]`；2. 交换 `a_2 = 10` 和 `a_5 = 2`，得到 `a = [1, 2, 7, 3, 10]`；3. 交换 `a_4 = 3` 和 `a_3 = 7`，得到 `a = [1, 2, 3, 7, 10]`。 示例输入： ``` 6 5 7 10 1 3 2 4 11 9 3 5 5 11 3 15 3 2 6 10 7 8 1 2 3 1 10 5 6 6 4 1 6 ``` 示例输出： ``` YES YES NO NO YES NO ```