Олимпиадный тренинг

Задача . E. Стоянка


Задача

Темы: Структуры данных *2200

Автомобильная стоянка в городе N представляет собой n парковочных мест, расположенных в ряд. Парковочные места пронумерованы от 1 до n слева направо.

Когда автомобилист приезжает на стоянку, дежурный определяет для него свободное парковочное место. В целях безопасности выбранное место должно находиться как можно дальше от уже занятых мест, то есть самое близкое занятое парковочное место должно быть как можно дальше. Если таких мест несколько, то среди них выбирается место с наименьшим номером. Если все места на стоянке свободны, то автомобилист получает парковочное место с номером 1.

Считается, что расстояние между i-м и j-м парковочными местами равно 4·|i - j| метров.

Вам заданы записи о приезде на стоянку и отъезде со стоянки автомобилистов в хронологическом порядке. Для каждой записи о приезде автомобилиста, выведите номер выделенного для него парковочного места.

Входные данные

В первой строке записаны через пробел два целых числа n и m (1 ≤ n, m ≤ 2·105) — количество парковочных мест и количество записей соответственно.

В следующих m строках заданы описания записей, одна запись в строке. В i-й строке даны числа ti, idi (1 ≤ ti ≤ 2; 1 ≤ idi ≤ 106). Если ti равно 1, то соответствующая запись информирует о приезде автомобилиста с номером idi на стоянку. Если ti равно 2, то соответствующая запись информирует об отъезде автомобилиста с номером idi со стоянки.

Записи о приезде на стоянку и об отъезде со стоянки автомобилистов заданы в хронологическом порядке. Все события происходили последовательно, никакие два события не происходили одновременно.

Гарантируется, что все записи корректны:

  • каждый автомобилист не более одного раза приезжал на стоянку и не более одного раза уезжал со стоянки,
  • не бывает записи об отъезде автомобилиста, который еще не приехал на стоянку,
  • автомобилистов на стоянке не более n в любой момент времени.

Считайте, что автомобилистам присвоены произвольные номера от 1 до 106, все присвоенные номера — различны. Первоначально все парковочные места на стоянке свободны.

Выходные данные

Для каждой записи о приезде автомобилиста, выведите номер выделенного для него парковочного места. Номера выделенных мест выводите в порядке приезда автомобилистов на стоянку.


Примеры
№Входные данныеВыходные данные
1 7 11
1 15
1 123123
1 3
1 5
2 123123
2 15
1 21
2 3
1 6
1 7
1 8 
1
7
4
2
7
4
1
3

time 2000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w645
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет