← 返回题目列表

Codeforces · 1918/B

B. 尽量减少反转

中文机器翻译题面 查看原题

给你两个排列 $$$a$$$ 和 $$$b$$$,长度为 $$$n$$$。排列是从 $$$1$$$ 到 $$$n$$$ 的 $$$n$$$ 元素数组,其中所有元素都是不同的。例如,数组 [$$$2,1,3$$$] 是一个排列,但 [$$$0,1$$$] 和 [$$$1,3,1$$$] 不是。

您可以(根据需要多次)选择两个索引 $$$i$$$ 和 $$$j$$$,然后同时将 $$$a_i$$$ 与 $$$a_j$$$ 以及 $$$b_i$$$ 与 $$$b_j$$$ 交换。

您讨厌反转,因此您希望最大限度地减少两种排列中反转的总数。

排列 $$$p$$$ 中的反转是一对索引 $$$(i, j)$$$,使得 $$$i < j$$$ 且 $$$p_i > p_j$$$。例如,如果 $$$p=[3,1,4,2,5]$$$ 则其中存在 $$$3$$$ 反转(索引对为 $$$(1,2)$$$、$$$(1,4)$$$ 和 $$$(3,4)$$$)。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 20\,000$$$) — 测试用例的数量。

每个测试用例由三行组成。第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 2\cdot10^5$$$) — 排列 $$$a$$$ 和 $$$b$$$ 的长度。第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq n$$$) — 排列 $$$a$$$。第三行包含类似格式的$$$b$$$。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot10^5$$$。

输出

对于每个测试用例,输出两个排列 $$$a'$$$ 和 $$$b'$$$ (与输入中的格式相同)——所有操作后的排列。 $$$a'$$$ 和 $$$b'$$$ 中的反转总数应该是使用语句中的操作可以获得的所有排列对中可能的最小值。

如果有多个解决方案,请打印其中任何一个。

示例

输入 #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

注意

在第一个测试用例中,最小可能的反转次数是 $$$10$$$。

在第二个测试用例中,我们可以同时对两个排列进行排序。为此,可以进行以下操作:

- 在两个排列中交换位置 $$$1$$$ 和 $$$3$$$ 中的元素。运算后,$$$a =$$$[$$$2,1,3$$$],$$$b =$$$[$$$2,1,3$$$]。
- 交换位置 $$$1$$$ 和 $$$2$$$ 中的元素。操作完成后,$$$a$$$ 和 $$$b$$$ 已排序。

在第三个测试用例中,最小可能的反转次数是 $$$7$$$。