Odd Swap Sort (Codeforces 1638B)
Tags: Math, sortings

You are given an array $$$a_1, a_2, \dots, a_n$$$. You can perform operations on the array. In each operation you can choose an integer $$$i$$$ ($$$1 \le i < n$$$), and swap elements $$$a_i$$$ and $$$a_{i+1}$$$ of the array, if $$$a_i + a_{i+1}$$$ is odd.Determine whether it can be sorted in non-decreasing order using this operation any number of times.

Input: Each test contains multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^5$$$) — the number of test cases. Description of the test cases follows.The first line of each test case contains a single 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, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the elements of the array.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output: For each test case, print "Yes" or "No" depending on whether you can or can not sort the given array.You may print each letter in any case (for example, "YES", "Yes", "yes", "yEs" will all be recognized as positive answer).

Note: In the first test case, we can simply swap $$$31$$$ and $$$14$$$ ($$$31 + 14 = 45$$$ which is odd) and obtain the non-decreasing array $$$[1,6,14,31]$$$.In the second test case, the only way we could sort the array is by swapping $$$4$$$ and $$$2$$$, but this is impossible, since their sum $$$4 + 2 = 6$$$ is even.In the third test case, there is no way to make the array non-decreasing.In the fourth test case, the array is already non-decreasing.

Sample Inputs:
4
4
1 6 31 14
2
4 2
5
2 9 6 7 10
3
6 6 6

Sample Outputs:
Yes
No
No
Yes

Solution (Python):
import sys
for _ in range(int(sys.stdin.readline())):
    n = int(sys.stdin.readline())
    l = [int(x) for x in sys.stdin.readline().split()]
    if n == 1:
        print('YES')
    else:
        st1 = 0
        st2 = 0
        ans = False
        for i in l:
            if i % 2 == 0:
                if i >= st1:
                    st1 = i
                else:
                    ans = True
            elif i >= st2:
                st2 = i
            else:
                ans = True
            if ans:
                break
        if not ans:
            print('YES')
        else:
            print('NO')

Solution (Python):
for s in [*open(0)][2::2]:
    a = [[], []]
    for x in map(int, s.split()):
        a[x & 1] += (x,)
    print('YNeos'[any((x > sorted(x) for x in a))::2])

Solution (Python):
import sys
import copy
import heapq
import bisect
import functools
from math import *
from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import groupby
import itertools
from itertools import accumulate
from decimal import Decimal, ROUND_HALF_UP
readline = lambda : sys.stdin.readline().rstrip()

def solve():
    n = int(readline())
    a = list(map(int, readline().split()))
    (odd, even) = ([], [])
    for x in a:
        if x % 2 == 0:
            even.append(x)
        else:
            odd.append(x)
    for i in range(len(odd) - 1):
        if odd[i] > odd[i + 1]:
            print('NO')
            return
    for i in range(len(even) - 1):
        if even[i] > even[i + 1]:
            print('NO')
            return
    print('YES')

def main():
    t = 1
    t = int(readline())
    for i in range(t):
        solve()
if __name__ == '__main__':
    main()