Один процессор
Отправить решение
Решать в редакторе
Сложность:
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
Комментарии