Задача №114981. Рейнджеры в автобусе
Не каждый день могучие рейнджеры надевают свои костюмы. Сами посудите: как нелепо они бы смотрелись, скажем, в общественном транспорте, если бы не снимали их!
Это создаёт определённые трудности злодеям, которые хотят выследить их. Вот и сегодня Рита Репульса не может их поймать, потому что не знает, как они выглядят без костюмов.
Рита следит за автобусом, в котором, по её мнению, едет кто-то из рейнджеров. В салоне автобуса n рядов сидений, в каждом из которых по два места — слева и справа от прохода. Ряды пронумерованы от 1 до n , начиная с передней части автобуса. На конечной остановке в автобус по очереди зашли k человек, и Рита знает, кто на какое место сел и в каком порядке. Кроме того, ей известно, как каждый из рейнджеров выбирает себе место, когда заходит в автобус:
- Красный рейнджер любит сидеть впереди. Поэтому среди свободных мест он всегда выбирает место в ряду с наименьшим номером. Если же в этом ряду свободно два места, он садится слева от прохода.
- Синий рейнджер тоже любит сидеть впереди. Но, в отличие от красного, когда в ряду с наименьшим номером свободно два места, Синий садится справа.
- Чёрный рейнджер любит сидеть сзади. Среди свободных мест он всегда выбирает место в ряду с наибольшим номером, а если там свободно два места, то садится слева от прохода.
- Жёлтый рейнджер тоже, любит сидеть сзади. Но, в отличие от чёрного, когда в ряду с наибольшим номером свободно два места, жёлтый садится справа.
- Розовый рейнджер не имеет никаких предпочтений и может сесть на любое свободное место.
Про каждого из рейнджеров Рита хочет узнать, кто из k пассажиров мог бы быть им. По известным местам, куда садились пассажиры, выведите эту информацию. Обратите внимание, что совсем не обязательно все рейнджеры ехали на этом автобусе.
В первой строке входного файла заданы числа n и k — количество рядов в автобусе и количество пассажиров ( 1 ≤ n ≤ 10 9 , 1 ≤ k ≤ min (2·10 5 , 2 n ) ).
В следующих k строках описаны пассажиры в том порядке, в котором они заходили в автобус.
В i -й из этих строк заданы числа x i и y i — место, на которое сел i -й пассажир ( 1 ≤ x i ≤ n , 1 ≤ y i ≤ 2 ), x i — это номер ряда, y i = 1 , если это место слева от прохода, и y i = 2 , если справа.
Все места, на которые сели пассажиры, различны.
В первой строке выходного файла выведите число s 1 — количество пассажиров, которые могли бы быть красным рейнджером, а затем, через пробел, s 1 чисел — номера этих пассажиров в порядке возрастания (пассажиры нумеруются с 1 по k в том порядке, в котором они заданы во входном файле).
В следующих четырёх строках выведите в том же формате информацию об остальных рейнджерах: синем, чёрном, жёлтом и розовом соответственно.
Первая группа тестов состоит из тестов, для которых выполняются ограничения n , k ≤ 5000 . Баллы за эту группу начисляются только при прохождении всех тестов группы. Стоимость группы составляет 25 баллов.
Вторая группа тестов состоит из тестов, для которых выполняются ограничения k ≤ 5000 . Баллы за эту группу начисляются только при прохождении всех тестов этой и предыдущих групп. Стоимость группы составляет 25 баллов.
Третья группа тестов состоит из тестов, для которых выполняются полные ограничения. Баллы за эту группу начисляются только при прохождении всех тестов этой и предыдущих групп. Стоимость группы составляет 50 баллов.
Обратите внимание на возможность узнать результат проверки вашего решения на всех тестах, нажав на ссылку « Запросить информацию о проверке » на вкладке « Решения ».
3 4 1 1 1 2 3 2 2 1
3 1 2 4 1 2 0 1 3 4 1 2 3 4