A16747. Isamatdin and His Magic Wand!
编程题
入门
知识点
题目描述
伊萨马特丁有 $n$ 个玩具排成一排。第 $i$ 个玩具上有一个整数 $a_i$。他想要把它们排好序，否则他妈妈会责备他。
但伊萨马特丁一直不喜欢把玩具排好，于是他的朋友 JahonaliX 给了他一根魔法棒来帮忙。不幸的是，JahonaliX 在制作魔法棒时犯了个小错误。
然而，伊萨马特丁已经等不及了，还是决定使用这根坏了的魔法棒。这根魔法棒只能交换两个整数奇偶性不同（一个是偶数，一个是奇数）的玩具。也就是说，只有当 $a_i \bmod 2 \neq a_j \bmod 2$ 时，才可以交换第 $i$ 个和第 $j$ 个玩具，其中 $\bmod$ 表示整数除法的余数。
现在，他想知道，使用这根坏魔法棒，他能得到的字典序最小的排列是什么。
*注：* 如果存在某个下标 $i$，对于任意 $j<i$ 均有 $p_j=q_j$，且 $p_i<q_i$，则序列 $p$ 的字典序小于序列 $q$。
但伊萨马特丁一直不喜欢把玩具排好，于是他的朋友 JahonaliX 给了他一根魔法棒来帮忙。不幸的是，JahonaliX 在制作魔法棒时犯了个小错误。
然而，伊萨马特丁已经等不及了，还是决定使用这根坏了的魔法棒。这根魔法棒只能交换两个整数奇偶性不同（一个是偶数，一个是奇数）的玩具。也就是说，只有当 $a_i \bmod 2 \neq a_j \bmod 2$ 时，才可以交换第 $i$ 个和第 $j$ 个玩具，其中 $\bmod$ 表示整数除法的余数。
现在，他想知道，使用这根坏魔法棒，他能得到的字典序最小的排列是什么。
*注：* 如果存在某个下标 $i$，对于任意 $j<i$ 均有 $p_j=q_j$，且 $p_i<q_i$，则序列 $p$ 的字典序小于序列 $q$。
输入格式
每组测试数据包含多组用例。第一行为测试用例组数 $t$，其中 $1 \le t \le 10^4$。
每组用例的第一行为一个整数 $n$，表示玩具数，$1 \le n \le 2 \cdot 10^5$。
每组用例的第二行为 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示玩具上的整数，$1 \le a_i \le 10^9$。
保证所有用例中 $n$ 的总和不超过 $2 \cdot 10^5$。
每组用例的第一行为一个整数 $n$，表示玩具数，$1 \le n \le 2 \cdot 10^5$。
每组用例的第二行为 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示玩具上的整数，$1 \le a_i \le 10^9$。
保证所有用例中 $n$ 的总和不超过 $2 \cdot 10^5$。
输出格式
对于每个测试用例，输出 $n$ 个整数，表示用上述操作能够得到的字典序最小的序列。
输入输出样例
输入 #1
7 4 2 3 1 4 5 3 2 1 3 4 4 3 7 5 1 2 1000000000 2 3 1 3 5 5 2 5 3 1 7 4 2 4 8 6
输出 #1
1 2 3 4 1 2 3 3 4 3 7 5 1 1000000000 2 1 3 5 1 2 3 5 7 2 4 8 6
说明/提示
在第一个测试用例中，我们可以交换 $(1, 3)$ 位置，之后交换 $(2, 3)$ 位置。
在第二个测试用例中，我们可以依次交换 $(1, 2)$、$(1, 3)$，再交换 $(2, 3)$ 位置。
在第三和第四个测试用例中，所有玩具整数的奇偶性均相同，无法进行任何交换。
在第二个测试用例中，我们可以依次交换 $(1, 2)$、$(1, 3)$，再交换 $(2, 3)$ 位置。
在第三和第四个测试用例中，所有玩具整数的奇偶性均相同，无法进行任何交换。