Условие:
B. Св. Хрома
ограничение по времени на тест2 секунды
ограничение по памяти на тест256 мегабайт
Дана перестановка∗
p
длины n
, которая содержит каждое целое число от 0
до n−1
, и полоса из n
ячеек. Св. Хрома будет окрашивать i
-ю ячейку полосы в цвет MEX(p1,p2,...,pi)
†
Например, пусть p=[1,0,3,2]
. Тогда Св. Хрома будет окрашивать ячейки полосы следующим образом: [0,2,2,4]
Вам даны два целых числа n
и x
. Поскольку Св. Хрома любит цвет x
, постройте перестановку p
, чтобы количество ячеек в полосе, окрашенных в цвет x
, было максимально.
∗
Перестановка длины n
— это последовательность из n
элементов, содержащая каждое целое число от 0
до n−1
ровно один раз. Например, [0,3,1,2]
является перестановкой, но [1,2,0,1]
не является таковой, поскольку 1
встречается дважды, а [1,3,2]
не является таковой, поскольку 0
вообще не встречается.
†
Функция MEX
для последовательности определяется как первое неотрицательное целое число, которое в ней не встречается. Например, MEX(1,3,0,2)=4
, а MEX(3,1,2)=0
.
Входные данные
Первая строка входных данных содержит одно целое число t
(1≤t≤4000
) — количество наборов входных данных.
Единственная строка каждого набора входных данных содержит два целых числа n
и x
(1≤n≤2⋅105
, 0≤x≤n
) — количество ячеек и цвет, который вы хотите максимизировать.
Гарантируется, что сумма n
по всем наборам входных данных не превышает 2⋅105
.
Выходные данные
Выведите перестановку p
длины n
, чтобы количество ячеек в полосе, окрашенных в цвет x
, было максимально. Если существует несколько таких перестановок, выведите любую из них.
Пример
Входные данныеСкопировать
7
4 2
4 0
5 0
1 1
3 3
1 0
4 3
Выходные данныеСкопировать
1 0 3 2
2 3 1 0
3 2 4 1 0
0
0 2 1
0
1 2 0 3
Решение:
Для решения задачи необходимо построить перестановку p длины n, чтобы максимизировать количество ячеек, окрашенных в цвет x. Цвет ячейки определяется как MEX (minimum excluded value) для первых i элементов перестановки.
Подход к решению
1. Понимание MEX: MEX для последовательности — это наименьшее неотрицательное целое число, которое не присутствует в последовательности. Например, для последовательности
[0, 1, 2] MEX равен 3, а для [0, 2] MEX равен 1.2. Максимизация цвета
x:- Если
x меньше n, то мы можем включить x в перестановку и сделать так, чтобы MEX стал равным x как можно чаще.- Если
x равно n, то MEX никогда не может быть равным n, так как все числа от 0 до n-1 присутствуют в перестановке.3. Стратегия:
- Если
x n, мы можем создать перестановку, которая включает x и все числа от 0 до n-1, исключая x на определенных позициях, чтобы MEX стал равным x.- Если
x = n, мы просто можем вернуть перестановку, которая не включает n, например, [0, 1, 2, ..., n-1].Реализация
Теперь давайте реализуем это в коде:
1. : - Если равно , возвращаем стандартную перестановку от до . - В противном случае создаем список от до , удаляем и добавляем его в конец списка. 2. : - Читает входные данные и обрабатывает каждый набор. - Вызывает функцию для получения перестановки и собирает результаты. 3. : Результаты выводятся в формате, требуемом задачей. Этот код эффективно решает задачу с учетом ограничений и гарантирует, что MEX будет равен как можно чаще.