Эффективная обработка операций с очередями для больших n ⇐ C++

[Anonymous]

У нас есть n человек, каждый из которых имеет свой номер (от 1 до n). Изначально эти люди выстраиваются в очередь так, что человек с номером 1 находится впереди, человек 2 — вторым и так далее.
Мы можем выполнить две операции:
Перенесите конкретного человека в начало очереди.
Дайте приз человеку, находящемуся в начале очереди, и переместите его в конец очереди.
Формат ввода :
В первой строке записано два числа: n (число людей) и m (количество операций).
Следующие m строк содержат целое число, обозначающее операцию:
Если целое число равно 0, это означает, что нужно дать приз человеку впереди и двигаться их назад.
Если целое число является любым числом, отличным от 0, это означает, что человек с этим номером будет помещен в начало очереди.
Формат вывода:
Для каждой операции предоставления приз (0), выведите номер человека, получившего приз приз.
Ограничения:
n может быть очень большим, до 1 миллиарда, поэтому мы не можем хранить всю очередь в памяти напрямую.
Мы не можем использовать обычную очередь и назначать в нее каждого человека. , поскольку это превысит наш максимальный лимит памяти в 256 МБ. Например, если у нас есть 1 миллиард человек и мы храним их в очереди, это займет 4 ГБ ОЗУ.
Например:
Input100000 6
0
0
10000
0
0
20
Выход
1
2
10000
3

Подробнее здесь: https://stackoverflow.com/questions/793 ... fficiently