Codeforces Round 945 (Div. 2) |
---|
Закончено |
Лиса любит перестановки! Она придумала следующую задачу, и предложила Коту её решить:
Вам дано четное целое положительное число $$$n$$$ и перестановка$$$^\dagger$$$ $$$p$$$ длины $$$n$$$.
Счет другой перестановки $$$q$$$ длины $$$n$$$ определим как количество локальных максимумов в массиве $$$a$$$ длины $$$n$$$, где $$$a_i = p_i + q_i$$$ для всех индексов $$$i$$$ ($$$1 \le i \le n$$$). Другими словами, счет $$$q$$$ — это количество $$$i$$$ таких, что $$$1 < i < n$$$ (обратите внимание на строгие неравенства), $$$a_{i-1} < a_i$$$ и $$$a_i > a_{i+1}$$$ (еще раз обратите внимание на строгие неравенства).
Найдите перестановку $$$q$$$, которая достигает максимального счета при заданных $$$n$$$ и $$$p$$$. Если таких перестановок несколько, вы можете вывести любую из них.
$$$^\dagger$$$ Перестановкой длины $$$n$$$ является массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$ в произвольном порядке. Например, $$$[2,3,1,5,4]$$$ — перестановка, но $$$[1,2,2]$$$ — не перестановка ($$$2$$$ встречается в массиве дважды) и $$$[1,3,4]$$$ тоже не перестановка ($$$n=3$$$, но в массиве встречается $$$4$$$).
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит одно четное целое число $$$n$$$ ($$$4 \leq n \leq 10^5$$$, $$$n$$$ — четное) — длину перестановки $$$p$$$.
Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \leq p_i \leq n$$$). Гарантируется, что $$$p$$$ действительно является перестановкой длины $$$n$$$.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$.
Для каждого набора входных данных выведите одну строку, содержащую любую перестановку чисел длины $$$n$$$ (массив $$$q$$$) такую, что счёт $$$q$$$ максимален при заданных ограничениях.
441 2 3 444 3 1 266 5 1 4 2 381 2 4 5 7 6 8 3
2 4 1 3 3 1 4 2 2 5 1 4 3 6 5 4 8 2 7 1 6 3
В первом примере $$$a = [3, 6, 4, 7]$$$. Массив имеет только один локальный максимум (на второй позиции), поэтому счет выбранной перестановки $$$q$$$ равен $$$1$$$. Можно доказать, что этот счет оптимален при заданных ограничениях.
В последнем примере полученный массив $$$a = [6, 6, 12, 7, 14, 7, 14, 6]$$$ имеет $$$3$$$ максимума — на третьей, пятой и седьмой позициях.
Название |
---|