A16157 | $Parity Sort$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

给定一个长度为 $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 \times 10^5$），表示数组 $a$ 的长度。 每个测试用例的第二行包含 $n$ 个正整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$），表示数组 $a$ 的元素。 保证所有测试用例中 $n$ 的总和不超过 $2 \times 10^5$。

对于每个测试用例，输出一行： - 如果可以通过若干次操作将数组排序，输出 YES； - 否则输出 NO。 你可以用任意大小写形式输出 YES 和 NO（例如 yEs, yes, Yes 和 YES 都会被识别为肯定回答）。

输入 #1

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

输出 #1

YES
YES
NO
NO
YES
NO

C++ 编辑器

输入

输出