CS
Задачник Базовый курс EN

Задача

Хроника из региональных каталогов

сортировка куча потоковая обработка наука и физика журнал

Землетрясения записывают k региональных сетей, у каждой свой каталог, упорядоченный по времени. Для общей хроники каталоги нужно слить в один, тоже по времени. Если у событий разных сетей время совпадает, раньше идёт событие сети с меньшим номером; события одной сети сохраняют порядок своего каталога. Выведите, из какой сети каждое событие хроники.

Один из тестов — настоящий каталог USGS: 19 073 землетрясения силой от 5 за 2015–2025 годы, разделённые на 36 сетей по долготе (полосы по 10°), время — в секундах от начала 2015 года.

Вход

В первой строке k (1 ≤ k ≤ 100 000). Дальше k строк: i-я начинается с числа событий mi ≥ 1, за которым идут mi моментов времени — целых чисел от 0 до 10⁹ в порядке неубывания. Всего событий не больше 100 000.

Выход

Для каждого события хроники по порядку — номер его сети (от 1 до k), по одному в строке.

Примеры

Пример 1

Вход
3
3 10 40 70
2 20 30
2 5 80
Выход
3
1
2
2
1
1
3

Пример 2

Вход
3
2 100 100
1 100
2 50 100
Выход
3
1
1
2
3

Ограничения

Время · Python
4000 мс
Время · Go
1000 мс
Память
256 МБ
Проверка
10 тестов

Разбор

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

1Подсказка 1

Два каталога сливает обычное слияние двумя указателями. Что, если сливать по очереди: первый со вторым, результат с третьим, потом с четвёртым? Сколько раз будет переписано самое первое событие?

2Подсказка 2

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

3Идея

Держим в куче первое непрочитанное событие каждой сети — ключом служит пара (время, номер сети), так что при равном времени первой выходит сеть с меньшим номером. Достаём минимум, печатаем номер его сети и кладём в кучу следующее событие этой сети, если оно есть. Куча никогда не больше k, и каждая операция стоит O(log k).

Есть и решение без кучи — турнир слияний, как в сортировке слиянием: слить каталоги парами, потом пары пар и так далее. Уровней ⌈log₂ k⌉, на каждом переписывается не больше N событий, итого тоже O(N log k). Сливать же по очереди плохо: первый каталог переписывается при каждом из k − 1 слияний, и при k = 100 000 сетей по одному событию это пять миллиардов операций.

4Разбор

В Python пара (время, номер сети, место в каталоге) сравнивается как кортеж: сначала по времени, при равенстве — по номеру сети. Именно это и нужно. Вместо «достать и положить» удобно вызвать heapreplace: он заменяет вершину кучи и восстанавливает порядок за одно просеивание. В Go то же делает heap.Fix(&h, 0) после замены h[0].

Годится и совсем короткое решение: выписать все события как пары (время, номер сети) и отсортировать их. Это O(N log N) — чуть больше, чем O(N log k), но в пределах ограничений. Куча хороша другим: ей не нужно держать все каталоги в памяти, достаточно читать каждый по одному событию. Так сливают файлы, которые не помещаются в память, — во внешней сортировке.

4+Решение
5Сложность

Куча: O(N log k) времени и O(k) памяти сверх входа. Слияние по очереди: O(N·k) в худшем случае.

6Типичные ошибки
  • Слияние по очереди. Каждое отдельное слияние верное, но вместе они квадратичны по числу сетей: пятый тест — сто тысяч сетей по одному событию.
  • Не тот порядок при равном времени. Если положить в кучу (время, место в каталоге, номер сети), при совпадении времени победит событие, которое стоит раньше в своём каталоге, а не сеть с меньшим номером. Во втором примере в момент 100 случились четыре события трёх сетей.
  • Медленный вывод. Сто тысяч строк лучше собрать и напечатать разом, а не вызывать print на каждую.

Алгоритмы задачи

SRT Алгоритм Сортировка слиянием Делит пополам, сортирует половины и сливает: n log n на любом входе, устойчиво, годится для внешней памяти. O(n log n) 2 задачи DS Структура данных Двоичная куча Минимум под рукой, добавление и извлечение за O(log n): дерево в массиве, на котором живут календари событий. O(log n) 2 задачи
Каталог алгоритмов