Codeforces Round 794 (Div. 1) |
---|
Закончено |
Это сложная версия задачи. Разница между простой и сложной версиями в том, что в этой версии вы должны вывести лексикографически минимальную перестановку с наименьшим весом.
Вам дана перестановка $$$p_1, p_2, \ldots, p_n$$$ целых чисел от $$$1$$$ до $$$n$$$.
Определим вес перестановки $$$q_1, q_2, \ldots, q_n$$$ целых чисел от $$$1$$$ до $$$n$$$ как $$$$$$|q_1 - p_{q_{2}}| + |q_2 - p_{q_{3}}| + \ldots + |q_{n-1} - p_{q_{n}}| + |q_n - p_{q_{1}}|$$$$$$
Вы хотите, чтобы ваша перестановка была как можно легче. Среди перестановок $$$q$$$ с наименьшим возможным весом найдите лексикографически минимальную.
Перестановка $$$a_1, a_2, \ldots, a_n$$$ называется лексикографически меньшей, чем перестановка $$$b_1, b_2, \ldots, b_n$$$, если существует некоторое $$$1 \le i \le n$$$ такое, что $$$a_j = b_j$$$ для всех $$$1 \le j < i$$$ и $$$a_i<b_i$$$.
Первая строка входных данных содержит одно целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$2 \le n \le 200$$$) — размер перестановки.
Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$, все $$$p_i$$$ различны) — элементы перестановки.
Сумма $$$n$$$ по всем наборам входных данных не превышает $$$400$$$.
Для каждого набора входных данных выведите $$$n$$$ целых чисел $$$q_1, q_2, \ldots, q_n$$$ ($$$1 \le q_i \le n$$$, все $$$q_i$$$ различны) — одну из перестановок с наименьшим весом.
322 142 3 1 455 4 3 2 1
1 2 1 3 4 2 1 3 4 2 5
В первом наборе входных данных есть две перестановки длины $$$2$$$: $$$(1, 2)$$$ и $$$(2, 1)$$$. Перестановка $$$(1, 2)$$$ имеет вес $$$|1 - p_2| + |2 - p_1| = 0$$$, а перестановка $$$(2, 1)$$$ имеет тот же вес: $$$|2 - p_1| + |1 - p_2| = 0$$$. В этой версии мы должны вывести лексикографически меньшую из них — $$$(1, 2)$$$.
Во втором наборе входных данных вес перестановки $$$(1, 3, 4, 2)$$$ равен $$$|1 - p_3| + |3 - p_4| + |4 - p_2| + |2 - p_1| = |1 - 1| + |3 - 4| + |4 - 3| + |2 - 2| = 2$$$. Перестановок с меньшими весами не существует.
В третьем наборе входных данных вес перестановки $$$(1, 3, 4, 2, 5)$$$ равен $$$|1 - p_3| + |3 - p_4| + |4 - p_2| + |2 - p_5| + |5 - p_1| = |1 - 3| + |3 - 2| + |4 - 4| + |2 - 1| + |5 - 5| = 4$$$. Перестановок с меньшими весами не существует.
Название |
---|