Задача №115366. Шулер
Участникам, использующим язык Python3 , рекомендуется отправлять решения на проверку с использованием интерпретатора PyPy3 .
Вы играете в новую карточную игру в казино со следующими правилами:
- В игре используется колода из \(2n\) карт с различными номиналами.
- Колода делится поровну между игроком и дилером: каждый получает по \(n\) карт.
- В течение \(n\) раундов игрок и дилер одновременно выкладывают по одной верхней карте из своей руки. Карты сравниваются, и очко получает тот, чья карта имеет больший номинал. Победившая карта убирается из игры, а проигравшая возвращается обратно в руку и кладётся поверх остальных карт в руку того, кто её выложил.
- Итоговый счёт игрока — его количество очков.
В первой строке задано одно целое число \(n\) (\(1 \leq n \leq 2 \cdot 10^{5}\)) — количество карт в руке игрока.
Во второй строке заданы \(n\) целых чисел \(a_{1}, a_{2}, \ldots, a_{n}\) (\(1 \leq a_{i} \leq 2n\)) — номиналы карт в руке игрока.
В третьей строке заданы \(n\) целых чисел \(b_{1}, b_{2}, \ldots, b_{n}\) (\(1 \leq b_{i} \leq 2n\)) — номиналы карт в руке дилера.
Гарантируется, что номиналы всех карт различны.
Выведите единственное число — максимальный счёт, который можно получить.
В данной задаче \(50\) тестов, помимо тестов из условия, каждый из них оценивается в \(2\) балла.
Решения, корректно работающие при \(n \le 500\), наберут не менее \(36\) баллов.
Решения, корректно работающие при \(n \le 5000\), наберут не менее \(60\) баллов.
Дополнительно, решения, корректно работающие при условии \(a_{1} > a_{2} > \ldots > a_{n}\) и \(b_{1} > b_{2} > \ldots > b_{n}\), наберут не менее \(14\) баллов.
В первом наборе входных данных можно поменять карты с номиналами 1 и 5, тогда рука игрока выглядит следующим образом [5, 6, 1] . Игровой процесс будет устроен следующим образом:
- Сравниваются карты с номиналами 5 и 2. Побеждает игрок и получает очко.
- Сравниваются карты с номиналами 6 и 2. Побеждает игрок и получает очко.
- Сравниваются карты с номиналами 1 и 2. Побеждает дилер.
Во втором наборе входных данных можно поменять карты с номиналами 3 и 10, тогда рука игрока выглядит следующим образом [8, 6, 10, 3, 1] . Игровой процесс будет устроен следующим образом:
- Сравниваются карты с номиналами 8 и 7. Побеждает игрок и получает очко.
- Сравниваются карты с номиналами 6 и 7. Побеждает дилер.
- Сравниваются карты с номиналами 6 и 9. Побеждает дилер.
- Сравниваются карты с номиналами 6 и 5. Побеждает игрок и получает очко.
- Сравниваются карты с номиналами 10 и 5. Побеждает игрок и получает очко.
В третьем наборе входных данных можно не менять карты. Игровой процесс будет устроен следующим образом:
- Сравниваются карты с номиналами 13 и 6. Побеждает игрок и получает очко.
- Сравниваются карты с номиналами 7 и 6. Побеждает игрок и получает очко.
- Сравниваются карты с номиналами 4 и 6. Побеждает дилер.
- Сравниваются карты с номиналами 4 и 1. Побеждает игрок и получает очко.
- Сравниваются карты с номиналами 9 и 1. Побеждает игрок и получает очко.
- Сравниваются карты с номиналами 12 и 1. Побеждает игрок и получает очко.
- Сравниваются карты с номиналами 10 и 1. Побеждает игрок и получает очко.
Обратите внимание, что игра всегда длится ровно \(n\) раундов.
3 1 6 5 2 3 4
2
5 8 6 3 10 1 7 9 5 2 4
3
7 13 7 4 9 12 10 2 6 1 14 3 8 5 11
6