Задача №112329. Магистраль "Урал"
Под будущей магистралью залегают \(n\) горизонтальных пластов. Геологическое исследование позволило определить точки магистрали, под которыми начинается и заканчивается каждый из них. При этом порядок залегания пластов по глубине определить не удалось.
В заданных местах вдоль планируемой магистрали пробурены вертикальные скважины. Каждая из них пересекает несколько верхних пластов, находящихся под точкой бурения. Для каждой скважины известно, в каком порядке располагаются пробуренные пласты сверху вниз, начиная от поверхности. Если скважина не пересекает какой-то из пластов, находящихся под точкой бурения, значит он проходит ниже дна скважины.
Требуется написать программу, которая определяет возможный порядок залегания пластов по глубине, не противоречащий полученным данным.
Первая строка входного файла содержит целое число \(n\) — количество пластов. Пласты пронумерованы целыми числами от 1 до \(n\) в произвольном порядке.
В \(i\)-й из следующих \(n\) строк содержатся целые числа \(l_i\) и \(r_i\) (0 <= \(l_i\) < \(r_i\) <= \(10^9\) ) — расстояния от начала магистрали до точек, под которыми начинается и заканчивается \(i\)-й пласт.
В следующей строке записано целое число \(m\) — количество скважин, в которых проводилось бурение. Следующие \(m\) строк описывают результаты бурения: в каждой строке сначала указаны два целых числа \(x\) (0 <= \(x\) <= \(10^9\) ) и \(k\) (0 <= \(k\) <= \(n\)) — расстояние от начала магистрали до скважины и количество обнаруженных в данной скважине пластов, затем — целые числа \(s_1\); \(s_2\), ..., \(s_k\) — номера пробуренных пластов, перечисленные в порядке залегания сверху вниз. Скважины перечислены в порядке возрастания расстояния \(x\).
Гарантируется, что решение существует.
Первая строка выходного файла должна содержать n целых чисел \(p_1\); \(p_2\), ..., \(p_n\), описывающих возможный порядок залегания пластов сверху вниз. Среди чисел \(p_1\), \(p_2\), ..., \(p_n\) каждый номер пласта должен встретиться ровно один раз. При этом пласт с номером \(p_j\) не должен нигде проходить выше пластов с номерами \(p_1\), ..., pj-1 или ниже пластов с номерами pj+1, ..., \(p_n\)
Если возможных расположений пластов несколько, выведите любое из них.
Данная задача содержит пять подзадач. Для оценки каждой подзадачи используется своя группа тестов. Баллы за подзадачу начисляются только в том случае, если все тесты из этой группы пройдены.
1 <= \(n\), \(m\) <= 1000
Каждая скважина пересекает все пласты, залегающие под ней
Подзадача оценивается в 20 баллов
1 <= \(n\), \(m\) <= 1000
Подзадача оценивается в 20 баллов
1 <= \(n\), \(m\) <= 30000
Суммарное количество пластов, найденных при бурении скважин, не более \(10^6\).
Подзадача оценивается в 20 баллов
1 <= \(n\), \(m\) <= \(10^5\)
Суммарное количество пластов, найденных при бурении скважин, не более \(10^5\).
Подзадача оценивается в 20 баллов
1 <= \(n\), \(m\) <= \(10^5\)
Суммарное количество пластов, найденных при бурении скважин, не более \(10^6\).
Подзадача оценивается в 20 баллов
4 1 5 2 7 7 10 1 11 3 1 1 1 4 1 2 7 2 2 3
2 1 3 4