Codeforces Round 777 (Div. 2) |
---|
Закончено |
После ошеломительного успеха у пятого класса, Мадоке решили доверить преподавать уже шестиклассникам.
Всего в её классе есть $$$n$$$ одноместных парт. Изначально Мадока за $$$i$$$-ю парту посадила ученика под номером $$$b_i$$$ ($$$1 \le b_i \le n$$$), а за дверью образовалась бесконечная очередь учеников с номерами $$$n + 1, n + 2, n + 3, \ldots$$$ в надежде оказаться на её уроке. Обратите внимание, что все ученики имеют различные номера.
После каждого урока происходит следующие события по порядку.
Обратите внимание, что в итоге за каждой партой снова находится ровно один ученик. Гарантируется, что числа $$$p$$$ таковы, что как минимум один ученик покидает класс после каждого урока. Обратите внимание на пояснение к первому примеру для лучшего понимания.
После нескольких (возможно нуля) уроков за партой $$$i$$$ сидит ученик $$$a_i$$$. По данным значениям $$$a_1, a_2, \ldots, a_n$$$ и $$$p_1, p_2, \ldots, p_n$$$, найдите лексикографически наименьшую подходящую перестановку $$$b_1, b_2, \ldots, b_n$$$, описывающую возможную начальную рассадку.
Перестановкой называется массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$ в произвольном порядке. Например, $$$[2,3,1,5,4]$$$ является перестановкой, но $$$[1,2,2]$$$ не является перестановкой ($$$2$$$ встречается дважды в массиве) и $$$[1,3,4]$$$ тоже не является перестановкой ($$$n=3$$$, но $$$4$$$ присутствует в массиве).
Для двух различных перестановок равной длины $$$a$$$ и $$$b$$$, $$$a$$$ лексикографически меньше $$$b$$$, если в первой позиции, где $$$a$$$ и $$$b$$$ различны, в $$$a$$$ элемент меньше, чем соответствующий элемент в $$$b$$$.
Первая строка входных данных содержит одно целое число $$$n$$$ ($$$2 \le n \le 10^5$$$) — количество парт в классе.
Вторая строка содержит $$$n$$$ целых чисел $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \leq p_i \leq n$$$) — места, куда пересаживаются ученики. Гарантируется, что $$$p$$$ содержит хотя бы два равных элемента.
Третья строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — конечная рассадка учеников. Гарантируется, что существует изначальная перестановка, из которой получилась рассадка $$$a$$$.
В единственной строке выведите $$$n$$$ целых чисел $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \le b_i \le n$$$) — лексикографически минимальную перестановку, описывающую начальную рассадку учеников, из которой могла получится конечная рассадка $$$a$$$.
5 5 5 3 3 1 1 8 2 9 4
1 3 2 5 4
5 1 3 2 5 2 3 2 5 4 1
3 2 5 4 1
10 10 8 5 3 7 8 6 6 1 1 5 26 24 27 21 4 18 2 28 1
5 4 2 6 7 8 3 9 1 10
Описание первого теста находится ниже:
На первой картинке показана стартовая рассадка, являющаяся ответом. Затем ученики, сидящие за партами $$$1, 2$$$ пересаживаются за $$$5$$$ парту. Также за $$$1$$$ парту пересел ученик с парты $$$5$$$, а за парту под номером $$$3$$$ пересаживается ученик с $$$4$$$ парты.
Таким образом, после всех этих пересадок, получается рассадка, показаная на втором изображении. Затем за партой под номером $$$5$$$ выгоняют ученика с номером $$$3$$$, а за партой под номером $$$3$$$ выгоняют ученика с номером $$$5$$$. (Поскольку их номера не самые маленькие) Затем за парты под номерами $$$2, 4$$$ садятся новые ученики с номерами $$$6, 7$$$. И эта рассадка (после конца первого урока) показана на третьем изображении.
На $$$4$$$ изображении показана рассадка, после второго урока до того, как всех лишних выгнали. А на пятой показана финальная рассадка после $$$2$$$ урока.
Название |
---|