Codeforces Round 922 (Div. 2) |
---|
Закончено |
Вам даны две перестановки $$$a$$$ и $$$b$$$ длины $$$n$$$. Перестановкой называется массив из $$$n$$$ элементов от $$$1$$$ до $$$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'$$$ должно быть минимально возможным среди всех пар перестановок, которые возможно получить с помощью операций из условия.
Если существует несколько решений, выведите любое из них.
351 2 3 4 55 4 3 2 133 1 23 1 262 5 6 1 3 41 5 3 6 2 4
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$$$.
Во втором наборе входных данных можно отсортировать обе перестановки одновременно. Для этого можно применить следующие операции:
В третьем тесте минимальное достижимое количество инверсий равно $$$7$$$.
Название |
---|