1. Идея

Все задания приходят в момент времени 0, то есть новых заявок во время работы принтера не появляется.

Значит, порядок печати можно определить сразу:

• сначала идут задания с большим приоритетом;
• если приоритет одинаковый, раньше печатается задание с меньшим номером.

После того как этот порядок найден, остаётся просто пройти по нему слева направо и накапливать время печати. Если у задания c_i страниц, то оно завершится через c_i секунд после окончания предыдущих заданий.

Итак, задача сводится к двум действиям:

1. отсортировать задания по правилу выбора принтера;
2. посчитать префиксные суммы количества страниц.

2. Наблюдения

Наблюдение 1

Так как все задания поступили одновременно, принтер в каждый момент выбирает не из "новых и старых", а просто из одного фиксированного набора ещё не напечатанных заданий.

Поэтому моделировать работу принтера по секундам или использовать очередь с приоритетом не нужно.

Наблюдение 2

Правило выбора задания полностью эквивалентно сортировке по двум ключам:

1. приоритет по убыванию;
2. номер задания по возрастанию.

Именно в таком порядке задания будут напечатаны.

Наблюдение 3

Если задания идут в порядке печати j1, j2, ..., jn, то момент завершения:

• первого задания равен его числу страниц;
• каждого следующего — сумме страниц всех заданий от начала до него.

То есть достаточно вести переменную current_time и прибавлять к ней число страниц текущего задания.

3. Алгоритм

1. Считываем n.
2. Для каждого задания с номером от 1 до n считываем:
   • приоритет,
   • количество страниц.
3. Сохраняем для каждого задания тройку:
   • номер,
   • приоритет,
   • количество страниц.
4. Сортируем все задания:
   • по приоритету по убыванию;
   • при равных приоритетах по номеру по возрастанию.
5. Заводим current_time = 0.
6. Идём по отсортированному списку:
   • прибавляем к current_time число страниц текущего задания;
   • выводим номер задания и current_time.

4. Почему это работает

Докажем, что алгоритм выводит задания в правильном порядке и с правильными моментами завершения.

Почему порядок верный

В любой момент, когда принтер освобождается, среди всех ожидающих он выбирает:

• задание с максимальным приоритетом;
• при равенстве — с минимальным номером.

Но все задания были поданы в момент 0, и новых уже не появится. Значит, множество ожидающих заданий в любой момент — это просто ещё не обработанные элементы исходного списка.

Следовательно, первым будет напечатано задание, минимальное по правилу:

• максимальный приоритет,
• затем минимальный номер.

После удаления первого задания по тому же правилу выбирается второе, затем третье и так далее.

Это в точности совпадает с сортировкой всех заданий:

• по приоритету по убыванию;
• по номеру по возрастанию.

Значит, отсортированный список — это именно фактический порядок печати.

Почему времена завершения верные

Печать выполняется без прерываний, на одну страницу уходит 1 секунда.

Если до текущего задания уже было напечатано суммарно T страниц, а у текущего задания c страниц, то оно завершится через T + c секунд от начала.

Переменная current_time как раз хранит количество секунд, потраченных на все уже завершённые задания. После прибавления pages текущего задания она становится временем его завершения.

Значит, для каждого задания алгоритм выводит правильный момент окончания печати.

5. Сложность

Основное время уходит на сортировку.

• Время: O(n log n)
• Память: O(n)

6. Код на C++17

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Job {
    int id;
    int priority;
    int pages;
};

int main() {
    int n;
    cin >> n;

    vector<Job> jobs(n);
    for (int i = 0; i < n; i++) {
        cin >> jobs[i].priority >> jobs[i].pages;
        jobs[i].id = i + 1;
    }

    sort(jobs.begin(), jobs.end(), [](const Job& a, const Job& b) {
        if (a.priority != b.priority) return a.priority > b.priority;
        return a.id < b.id;
    });

    long long current_time = 0;
    for (int i = 0; i < n; i++) {
        current_time += jobs[i].pages;
        cout << jobs[i].id << " " << current_time << "\n";
    }

    return 0;
}

7. Код на Python 3

n = int(input())

jobs = []
for i in range(1, n + 1):
    p, c = map(int, input().split())
    jobs.append((-p, i, c))

jobs.sort()

current_time = 0
for neg_p, job_id, pages in jobs:
    current_time += pages
    print(job_id, current_time)