Heapq на Python: обновление приоритетов в очереди событий

Напишите решение на Python и проверьте его на странице.

Другие упражнения по этой теме: Heapq и bisect в Python: задачи на кучи и приоритетные очереди.

Бортовой журнал спасательного батискафа

Бортовой журнал спасательного батискафа непрерывно фиксирует сигналы тревоги от глубоководных датчиков, каждый из которых имеет собственный уникальный номер. Вместе с вызовом передаётся оценка критичности неполадки. Приборы могут выходить на связь повторно: каждое новое сообщение обновляет критичность до последнего переданного значения, причём эта оценка может как вырасти, так и снизиться.

Когда команда батискафа готова приступить к ремонту, бортовая система выбирает из всех ещё не обслуженных датчиков устройство с наибольшей текущей критичностью. Если несколько датчиков требуют внимания в равной степени срочно, предпочтение отдаётся тому, чей первый сигнал тревоги был принят раньше — последующие обновления критичности на это первенство не влияют.

Как только поломка устранена, датчик исключается из дальнейшей работы, и его прежние сообщения уже не могут вызвать повторный выезд. Определите, в каком порядке батискаф проведёт ремонтные работы по всем поступившим вызовам.

Что уже дано

Заготовка программы уже считывает поток событий и передаёт их в функцию rescue_order, а затем выводит результат в поток вывода.

Что нужно сделать

Реализуйте функцию rescue_order(events: list[tuple]) -> list[int].

Функция принимает список событий events в порядке их поступления. Элементы списка представляют собой кортежи двух видов:

("S", sensor_id, criticality) — сигнал от датчика с целочисленным номером sensor_id и целочисленной оценкой criticality;
("R",) — готовность провести ремонт одного датчика.

Правила обработки событий:

Первый сигнал ("S", sensor_id, criticality) регистрирует датчик в очереди ожидания с указанной критичностью.
Повторные сигналы S для того же датчика (до его ремонта) обновляют его критичность до последнего переданного значения (оценка может вырасти, снизиться или остаться прежней). При этом исходный момент первой регистрации датчика остаётся неизменным.
При событии ("R",) батискаф выбирает среди всех активных датчиков тот, у которого текущая критичность максимальна. Если таких датчиков несколько, выбирается датчик, чей самый первый сигнал S поступил раньше всех среди претендентов.
Выбранный датчик считается отремонтированным и навсегда удаляется из системы: его номер добавляется в итоговый список, а любые его предыдущие сигналы больше не могут привести к повторному ремонту (гарантируется, что после ремонта новые сигналы для этого датчика не поступают).
Если на момент события ("R",) в очереди нет ни одного неисправного датчика, это событие игнорируется.
Оставшиеся после окончания журнала датчики автоматически не ремонтируются.

Функция должна вернуть список номеров датчиков (list[int]) строго в порядке их фактического ремонта.

Ввод и вывод

Программа работает со стандартными потоками ввода stdin и вывода stdout.

Формат ввода

В первой строке передаётся целое число $q$ ( $0 \leq q \leq 9000$ ) — количество событий.
В следующих $q$ строках записаны описания событий: либо S sensor_id criticality, где sensor_id и criticality — целые положительные числа от $1$ до $1 0^{9}$ , либо строка R.

Формат вывода

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

Пример

Ввод: 5 S 90 3 S 10 6 S 90 6 R R
Вывод: 90 10

РешениеPython

Без регистрации. Гостевая проверка не сохраняет прогресс. Для сохранения перейдите к уроку.

Отправьте решение, чтобы увидеть результаты тестов.