Задача №115368. Два массива
Участникам, использующим язык Python3 , рекомендуется отправлять решения на проверку с использованием интерпретатора PyPy3 .
Даны два массива \(a\) и \(b\) длины \(n\). Можно сколько угодно раз выполнить следующую операцию:
- Выбрать \(i\) от \(1\) до \(n\) и поменять местами \(a_i\) и \(b_i\).
Пусть \(f(c)\) — количество различных чисел в массиве \(c\). Найдите максимальное значение \(f(a) + f(b)\). Также требуется восстановить массивы \(a\) и \(b\) после выполнения операций.
Первая строка содержит единственное целое \(n\) (\(1 \le n \le 100\,000\)) — размер массивов.
Вторая строка содержит \(n\) целых чисел \(a_1\), \(\ldots\), \(a_n\) (\(1 \le a_i \le 2 \cdot n\)) — элементы массива \(a\).
Третья строка содержит \(n\) целых чисел \(b_1\), \(\ldots\), \(b_n\) (\(1 \le b_i \le 2 \cdot n\)) — элементы массива \(b\).
В первой строке выведите максимальное значение \(f(a) + f(b)\).
Во второй строке выведите \(n\) целых чисел — элементы массива \(a\) после выполнения операций.
В третьей строке выведите \(n\) целых чисел — элементы массива \(b\) после выполнения операций.
Тесты к этой задаче состоят из примеров и \(6\) групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов некоторых из предыдущих групп.
| Доп. ограничения | |||||
| Группа | Баллы | \(n\) | \(a, b\) | Необх. группы | Комментарий |
| 0 | 0 | – | – | – | Тесты из условия. |
| 1 | 17 | \(n \le 18\) | – | 0 | 0 |
| 2 | 10 | – | \(a_i \le 2\) и \(b_i \le 2\) | – | – |
| 3 | 15 | – | – | – | \(a_i = i\) или \(b_i = i\) |
| 4 | 15 | – | – | – | Каждое число встречается не более 2 раз суммарно |
| 5 | 15 | – | – | – | Каждое число суммарно встречается чётное количество раз |
| 6 | 28 | – | – | 0 – 5 | – |
В первом примере после применения трёх операций с \(i=2\), \(i=4\) и \(i=5\) получаем \(a = [1, 3, 4, 5, 2]\) и \(b = [1, 2, 3, 4, 4]\). После этого \(f(a) + f(b) = 5 + 4 = 9\). Можно показать, что нельзя добиться большего ответа.
Во втором примере после применения необходимых обменов получим: \(\)f([2, 3, 4, 2, 1, 5, 6]) + f([1, 2, 3, 4, 5, 6, 5]) = 6 + 6 = 12\(\)
5 1 2 4 4 4 1 3 3 5 2
9 1 3 4 5 2 1 2 3 4 4
7 2 2 4 4 5 5 5 1 3 3 2 1 6 6
12 2 3 4 2 1 5 6 1 2 3 4 5 6 5
7 12 3 3 4 5 6 4 1 2 13 8 10 13 7
14 12 3 13 8 10 6 4 1 2 3 4 5 13 7