Minimize Inversions (Codeforces 1918B)
Tags: Greedy, sortings

You are given two permutations $$$a$$$ and $$$b$$$ of length $$$n$$$. A permutation is an array of $$$n$$$ elements from $$$1$$$ to $$$n$$$ where all elements are distinct. For example, an array [$$$2,1,3$$$] is a permutation, but [$$$0,1$$$] and [$$$1,3,1$$$] aren't.You can (as many times as you want) choose two indices $$$i$$$ and $$$j$$$, then swap $$$a_i$$$ with $$$a_j$$$ and $$$b_i$$$ with $$$b_j$$$ simultaneously. You hate inversions, so you want to minimize the total number of inversions in both permutations.An inversion in a permutation $$$p$$$ is a pair of indices $$$(i, j)$$$ such that $$$i < j$$$ and $$$p_i > p_j$$$. For example, if $$$p=[3,1,4,2,5]$$$ then there are $$$3$$$ inversions in it (the pairs of indices are $$$(1,2)$$$, $$$(1,4)$$$ and $$$(3,4)$$$).

Input: The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 20\,000$$$) — the number of test cases.Each test case consists of three lines. The first line contains an integer $$$n$$$ ($$$1 \leq n \leq 2\cdot10^5$$$) — the length of the permutations $$$a$$$ and $$$b$$$. The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq n$$$) — permutation $$$a$$$. The third line contains $$$b$$$ in a similar format. It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot10^5$$$.

Output: For each test case, output two permutations $$$a'$$$ and $$$b'$$$ (in the same format as in the input) — the permutations after all operations. The total number of inversions in $$$a'$$$ and $$$b'$$$ should be the minimum possible among all pairs of permutations that can be obtained using operations from the statement.If there are multiple solutions, print any of them.

Note: In the first test case, the minimum possible number of inversions is $$$10$$$.In the second test case, we can sort both permutations at the same time. For this, the following operations can be done:  Swap the elements in the positions $$$1$$$ and $$$3$$$ in both permutations. After the operation, $$$a =$$$ [$$$2,1,3$$$], $$$b =$$$ [$$$2,1,3$$$].  Swap the elements in the positions $$$1$$$ and $$$2$$$. After the operations, $$$a$$$ and $$$b$$$ are sorted. In the third test case, the minimum possible number of inversions is $$$7$$$.

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

Sample Outputs:
3 2 5 1 4
3 4 1 5 2
1 2 3
1 2 3
2 3 4 6 5 1
1 2 4 3 5 6

Solution (Python):
def solve(a, b, n):
    c = [0 for i in range(n)]
    for i in range(n):
        c[a[i] - 1] = b[i]
    print(' '.join(list(map(str, list(range(1, n + 1))))))
    print(' '.join(list(map(str, c))))

def question():
    n = int(input())
    a = list(map(int, input().split(' ')))
    b = list(map(int, input().split(' ')))
    solve(a, b, n)
t = int(input())
for j in range(t):
    question()

Solution (Python):
import sys

def read_int():
    return int(sys.stdin.readline().rstrip())

def read_int_list():
    return list(map(int, sys.stdin.readline().split()))

def read_ints():
    return map(int, sys.stdin.readline().split())

def solve():
    n = read_int()
    a = read_int_list()
    b = read_int_list()
    mp = dict(zip(a, b))
    a.sort()
    vi = [mp[it] for it in a]
    print(' '.join(map(str, a)))
    print(' '.join(map(str, vi)))
if __name__ == '__main__':
    t = read_int()
    for _ in range(t):
        solve()

Solution (Python):
t = int(input())
while t > 0:
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    d = {}
    for i in range(n):
        d[a[i]] = b[i]
    a.sort()
    print(' '.join(map(str, a)))
    print(' '.join(map(str, [d[j] for j in a])))
    t -= 1