CF1918B.Minimize Inversions

普及/提高-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

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)$ ).

输入格式

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$ .

输出格式

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.

输入输出样例

输入#1

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

输出#1

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

说明/提示

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$ .

首页