У вас есть последовательность $$$a$$$ из $$$n$$$ элементов $$$1, 2, 3, \dots, k - 1, k, k - 1, k - 2, \dots, k - (n - k)$$$ ($$$k \le n < 2k$$$).
Назовем инверсией в $$$a$$$ пару индексов $$$i < j$$$ таких, что $$$a[i] > a[j]$$$.
Предположим, что у вас есть некоторая перестановка $$$p$$$ размера $$$k$$$ и вы строите последовательность $$$b$$$ размера $$$n$$$ следующим образом: $$$b[i] = p[a[i]]$$$.
Ваша задача — найти такую перестановку $$$p$$$, что суммарное количество инверсий в $$$b$$$ не превосходит суммарного количества инверсий в $$$a$$$, и $$$b$$$ лексикографически максимальна.
Напоминание: последовательность из $$$k$$$ целых чисел называется перестановкой, если она содержит все числа от $$$1$$$ по $$$k$$$ ровно по одному разу.
Еще одно напоминание: последовательность $$$s$$$ лексикографически меньше последовательности $$$t$$$, если либо $$$s$$$ — префикс $$$t$$$, или для первого $$$i$$$, для которого $$$s_i \ne t_i$$$, выполняется $$$s_i < t_i$$$ (в первой позиции, в которой эти последовательности различаются, элемент в $$$s$$$ меньше элемента в $$$t$$$).
В первой строке задано одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных.
В первой и единственной строке каждого набора заданы два целых числа $$$n$$$ и $$$k$$$ ($$$k \le n < 2k$$$; $$$1 \le k \le 10^5$$$) — длина последовательности $$$a$$$ и ее максимум.
Гарантируется, что сумма $$$k$$$ по всем наборам входных данных не превосходит $$$10^5$$$.
Для каждого набора входных данных, выведите $$$k$$$ целых чисел — перестановку $$$p$$$, которая максимизирует $$$b$$$ лексикографически, не увеличивая суммарное количество инверсий.
Можно доказать, что $$$p$$$ существует и единственная.
4 1 1 2 2 3 2 4 3
1 1 2 2 1 1 3 2
В первом наборе входных данных, последовательность $$$a = [1]$$$, поэтому существует только одна перестановка $$$p = [1]$$$.
Во втором наборе, последовательность $$$a = [1, 2]$$$. В $$$a$$$ нет инверсий, а потому только одна перестановка $$$p = [1, 2]$$$ не увеличивает количество инверсий.
В третьем наборе, $$$a = [1, 2, 1]$$$ и имеет $$$1$$$ инверсию. Если мы используем $$$p = [2, 1]$$$, то $$$b = [p[a[1]], p[a[2]], p[a[3]]] = [2, 1, 2]$$$ и также имеет $$$1$$$ инверсию.
В четвертом наборе, $$$a = [1, 2, 3, 2]$$$, и так как $$$p = [1, 3, 2]$$$ то $$$b = [1, 3, 2, 3]$$$. И $$$a$$$, и $$$b$$$ имеют по $$$1$$$ инверсии и $$$b$$$ — лексикографически максимальна.
Название |
---|