Задание EGEINFAD6F70: Сортировка, отбор и моделирование

Решение.

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

В файле N = 9992 занятых мест, M = 99906 рядов и K = 6661 мест в каждом ряду. Для каждого номера места c найдём номер первого занятого кресла f[c]. Если весь столбец свободен, положим f[c] = M + 1.

Пара мест c и c + 1 в ряду r подходит ровно тогда, когда r < f[c] и r < f[c + 1]. Эти неравенства одновременно гарантируют, что сами покупаемые кресла и все кресла перед ними свободны. Самый дальний допустимый ряд для этой пары: r = min(f[c], f[c + 1]) − 1. Значение 0 означает, что подходящего ряда для пары нет.

Перебираем все K − 1 соседние пары. Сначала максимизируем номер ряда. При равенстве выбираем наименьший левый номер места. Так явно соблюдается приоритет обоих критериев. За пределами мест 1…K пары не рассматриваются.

Для каждой пары взят её предельный ряд, поэтому более дальний ответ невозможен: он пересечёт первое занятое кресло хотя бы одного из двух столбцов. Время O(N + K), память O(K); строить всю огромную матрицу зала не требуется.

Полная программа на Python:

with open("data.txt", encoding="utf-8-sig") as f:
    n, rows, seats = map(int, f.readline().split())
    first = [rows + 1] * (seats + 1)
    for _ in range(n):
        r, s = map(int, f.readline().split())
        first[s] = min(first[s], r)
best_row = 0
best_seat = 0
for left in range(1, seats):
    r = min(first[left], first[left + 1]) - 1
    s = left
    if r > best_row or (r == best_row and (best_seat == 0 or s < best_seat)):
        best_row, best_seat = r, s
print(best_row, best_seat)

Проверка результата.

У выбранной пары левое место 6660, правое 6661. Первые занятые ряды этих столбцов: 99907 и 21029. Поэтому min(99907, 21029) − 1 = 21028. В ответе указываем левое место 6660.

Ответ: 21028 6660.