Elemental Decompress (Codeforces 1768C)
Tags: Greedy, sortings

You are given an array $$$a$$$ of $$$n$$$ integers.Find two permutations$$$^\dagger$$$ $$$p$$$ and $$$q$$$ of length $$$n$$$ such that $$$\max(p_i,q_i)=a_i$$$ for all $$$1 \leq i \leq n$$$ or report that such $$$p$$$ and $$$q$$$ do not exist.$$$^\dagger$$$ A permutation of length $$$n$$$ is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array), and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$ but there is $$$4$$$ in the array).

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. The description of test cases follows.The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$).The second line of each test case contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \leq a_i \leq n$$$) — the array $$$a$$$.It is guaranteed that the total sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$. 

Output: For each test case, if there do not exist $$$p$$$ and $$$q$$$ that satisfy the conditions, output "NO" (without quotes).Otherwise, output "YES" (without quotes) and then output $$$2$$$ lines. The first line should contain $$$n$$$ integers $$$p_1,p_2,\ldots,p_n$$$ and the second line should contain $$$n$$$ integers $$$q_1,q_2,\ldots,q_n$$$.If there are multiple solutions, you may output any of them.You can output "YES" and "NO" in any case (for example, strings "yEs", "yes" and "Yes" will be recognized as a positive response).

Note: In the first test case, $$$p=q=[1]$$$. It is correct since $$$a_1 = max(p_1,q_1) = 1$$$.In the second test case, $$$p=[1,3,4,2,5]$$$ and $$$q=[5,2,3,1,4]$$$. It is correct since:  $$$a_1 = \max(p_1, q_1) = \max(1, 5) = 5$$$,  $$$a_2 = \max(p_2, q_2) = \max(3, 2) = 3$$$,  $$$a_3 = \max(p_3, q_3) = \max(4, 3) = 4$$$,  $$$a_4 = \max(p_4, q_4) = \max(2, 1) = 2$$$,  $$$a_5 = \max(p_5, q_5) = \max(5, 4) = 5$$$. In the third test case, one can show that no such $$$p$$$ and $$$q$$$ exist.

Sample Inputs:
3
1
1
5
5 3 4 2 5
2
1 1

Sample Outputs:
YES
1 
1 
YES
1 3 4 2 5 
5 2 3 1 4 
NO

Solution (Python):
def getAns(n, a):
    cnt = [0 for i in range(n + 1)]
    pp = [0 for i in range(n + 1)]
    for x in a:
        cnt[x] += 1
        if cnt[x] > 2:
            return (False, None, None)
    b = []
    for i in reversed(range(1, n + 1)):
        if cnt[i] == 0:
            b.append(i)
    l = 0
    for x in reversed(sorted(a)):
        if cnt[x] == 2 and pp[x] == 0:
            if l < len(b) and b[l] < x:
                pp[x] = b[l]
                l += 1
            else:
                return (False, None, None)
        elif cnt[x] == 1:
            pp[x] = x
    ans1 = []
    ans2 = []
    ans1_has = [False for i in range(n + 1)]
    for x in a:
        if cnt[x] == 2:
            if ans1_has[x] == False:
                ans1.append(x)
                ans2.append(pp[x])
                ans1_has[x] = True
            else:
                ans1.append(pp[x])
                ans2.append(x)
        else:
            ans1.append(x)
            ans2.append(x)
    return (True, ans1, ans2)
t = int(input())
while t > 0:
    t -= 1
    n = int(input())
    a = list(map(int, input().split(' ')))
    (yes, ans1, ans2) = getAns(n, a)
    if yes == False:
        print('NO')
    else:
        print('YES')
        print(' '.join(map(str, ans1)))
        print(' '.join(map(str, ans2)))

Solution (Python):
def getAns(n, a):
    cnt = [0 for i in range(n + 1)]
    pp = [0 for i in range(n + 1)]
    for x in a:
        cnt[x] += 1
        if cnt[x] > 2:
            return (False, None, None)
    b = []
    for i in reversed(range(1, n + 1)):
        if cnt[i] == 0:
            b.append(i)
            b.append(i)
    l = 0
    for x in reversed(sorted(a)):
        if cnt[x] == 2:
            if b[l] < x:
                pp[x] = b[l]
                l += 1
            else:
                return (False, None, None)
        else:
            pp[x] = x
    ans1 = []
    ans2 = []
    ans1_has = [False for i in range(n + 1)]
    for x in a:
        if cnt[x] == 2:
            if ans1_has[x] == False:
                ans1.append(x)
                ans2.append(pp[x])
                ans1_has[x] = True
            else:
                ans1.append(pp[x])
                ans2.append(x)
        else:
            ans1.append(x)
            ans2.append(x)
    return (True, ans1, ans2)
t = int(input())
while t > 0:
    t -= 1
    n = int(input())
    a = list(map(int, input().split(' ')))
    (yes, ans1, ans2) = getAns(n, a)
    if yes == False:
        print('NO')
    else:
        print('YES')
        print(' '.join(map(str, ans1)))
        print(' '.join(map(str, ans2)))

Solution (Python):
from sys import stdin

def solve():
    n = int(stdin.readline())
    a = list(map(int, stdin.readline().split()))
    pos = [[] for _ in range(n)]
    for (i, x) in enumerate(a):
        pos[x - 1].append(i)
    p1 = [-1] * n
    s1 = []
    p2 = [-1] * n
    s2 = []
    for (x_, px) in enumerate(pos[::-1]):
        x = n - x_
        if len(px) == 1:
            p1[px[0]] = p2[px[0]] = x
        elif len(px) == 2:
            p1[px[0]] = p2[px[1]] = x
            s1.append(px[1])
            s2.append(px[0])
        elif len(px) == 0 and s1 and s2:
            p1[s1.pop()] = x
            p2[s2.pop()] = x
        else:
            print('NO')
            return
    print('YES')
    print(' '.join(map(str, p1)))
    print(' '.join(map(str, p2)))

def main():
    t = int(stdin.readline())
    for _ in range(t):
        solve()
main()