Elemental Decompress solution codeforces – You are given an array 𝑎a of 𝑛n integers.
Find two permutations†† 𝑝p and 𝑞q of length 𝑛n such that max(𝑝𝑖,𝑞𝑖)=𝑎𝑖max(pi,qi)=ai for all 1≤𝑖≤𝑛1≤i≤n or report that such 𝑝p and 𝑞q do not exist.
Elemental Decompress solution codeforces
†† A permutation of length 𝑛n is an array consisting of 𝑛n distinct integers from 11 to 𝑛n in arbitrary order. For example, [2,3,1,5,4][2,3,1,5,4] is a permutation, but [1,2,2][1,2,2] is not a permutation (22 appears twice in the array), and [1,3,4][1,3,4] is also not a permutation (𝑛=3n=3 but there is 44 in the array).
The first line contains a single integer 𝑡t (1≤𝑡≤1041≤t≤104) — the number of test cases. The description of test cases follows.
The first line of each test case contains a single integer 𝑛n (1≤𝑛≤2⋅1051≤n≤2⋅105).
The second line of each test case contains 𝑛n integers 𝑎1,𝑎2,…,𝑎𝑛a1,a2,…,an (1≤𝑎𝑖≤𝑛1≤ai≤n) — the array 𝑎a.
It is guaranteed that the total sum of 𝑛n over all test cases does not exceed 2⋅1052⋅105.
Elemental Decompress solution codeforces
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 22 lines. The first line should contain 𝑛n integers 𝑝1,𝑝2,…,𝑝𝑛p1,p2,…,pn and the second line should contain 𝑛n integers 𝑞1,𝑞2,…,𝑞𝑛q1,q2,…,qn.
Also read: Quick Sort solution codeforces
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).
Elemental Decompress solution codeforces
input
output
YES 1 1 YES 1 3 4 2 5 5 2 3 1 4 NO
Elemental Decompress solution codeforces
In the first test case, 𝑝=𝑞=[1]p=q=[1]. It is correct since 𝑎1=𝑚𝑎𝑥(𝑝1,𝑞1)=1a1=max(p1,q1)=1.
In the second test case, 𝑝=[1,3,4,2,5]p=[1,3,4,2,5] and 𝑞=[5,2,3,1,4]q=[5,2,3,1,4]. It is correct since:
- 𝑎1=max(𝑝1,𝑞1)=max(1,5)=5a1=max(p1,q1)=max(1,5)=5,
- 𝑎2=max(𝑝2,𝑞2)=max(3,2)=3a2=max(p2,q2)=max(3,2)=3,
- 𝑎3=max(𝑝3,𝑞3)=max(4,3)=4a3=max(p3,q3)=max(4,3)=4,
- 𝑎4=max(𝑝4,𝑞4)=max(2,1)=2a4=max(p4,q4)=max(2,1)=2,
- 𝑎5=max(𝑝5,𝑞5)=max(5,4)=5a5=max(p5,q5)=max(5,4)=5.
In the third test case, one can show that no such 𝑝p and 𝑞q exist.