Один процессор


Отправить решение Решать в редакторе

Сложность: 40%
Очки: 100 (частичный балл)
Ограничение по времени: 3.0s
Ограничение по памяти: 256M

Автор:
Тип задачи
Разрешённые языки
C, C#, C++, F#, Go, Java, JavaScript, Kotlin, Pascal, Python, Scratch

Один процессор

Процессор выполняет n задач по одной. Задача i появляется в момент a_i и требует d_i времени. Когда процессор свободен, он берёт из появившихся задач ту, у которой d_i меньше всего (при равенстве - с меньшим номером) и выполняет без прерывания. Если задач нет, ждёт ближайшую. В каком порядке выполнятся задачи?

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

В первой строке число n (1 ≤ n ≤ 200000). В следующих n строках пары a_i d_i (1 ≤ a_i, d_i ≤ 10^9).

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

Номера задач (с единицы) в порядке выполнения через пробел.

Примеры

Пример 1

Ввод:

3
1 2
2 4
3 2

Вывод:

1 3 2
Пример 2

Ввод:

2
1 3
1 3

Вывод:

1 2

Комментарии

Еще нет ни одного комментария.