Danil Fadeev
Ученик
(178),
на голосовании
2 месяца назад
В предыдущей задаче была рассмотрена система исполнения процессов «T-Saurus». В этой задаче вам предстоит реализовать core-функционал этой системы. Вместо минимального времени, за которое могут быть выполнены все процессы, вам необходимо перечислить их порядок, при котором достигается это время.
Для этого вам необходимо разбить все процессы на непересекающиеся множества процессов (пронумеруем их от 1 1 до ? k) так, чтобы сначала исполнитель «T-Saurus» параллельно выполнил все процессы первого множества, затем второго множества и т.д., и исполнение процессов удовлетворяло условию из предыдущей задачи. Т. е. в ? i-ом множестве процессов должны присутствовать только те процессы, для которых все необходимые для их исполнения процессы включены в множествах с меньшими номерами ? j: 1 ≤ ? < ? 1≤j<i. Напоминаем, что функционал системы «T-Saurus» состоит в том, что при последовательном исполнении предыдущих множеств процессов, все процессы в очередном множестве смогут исполниться.
Входные данные совпадают с входными данными из предыдущей задачи. Обратите внимание на то, как должно выводиться каждое множество — все процессы в рамках множества должны быть отсортированы.
Формат входных данных
В первой строке дано число ? n ( 1 ≤ ? ≤ 1 0 5 ) (1≤n≤10 5 ) — количество процессов. Далее дано ? n строк. В ? i-й строке первым числом идёт ? ? a i — количество необходимых ? i-му процессу процессов. Далее идет ? ? a i чисел через пробел — их номера.
Формат выходных данных
В единственной строке выведите число ? k — количество множеств, на которое необходимо разбить все процессы. В следующих ? k строках выведите описание этих множеств: первым числом укажите размер множества ? ? k i , а далее через пробел ? ? k i чисел в порядке возрастания — номера процессов очередного множества.
Для этого вам необходимо разбить все процессы на непересекающиеся множества процессов (пронумеруем их от
1
1 до
?
k) так, чтобы сначала исполнитель «T-Saurus» параллельно выполнил все процессы первого множества, затем второго множества и т.д., и исполнение процессов удовлетворяло условию из предыдущей задачи. Т. е. в
?
i-ом множестве процессов должны присутствовать только те процессы, для которых все необходимые для их исполнения процессы включены в множествах с меньшими номерами
?
j:
1
≤
?
<
?
1≤j<i. Напоминаем, что функционал системы «T-Saurus» состоит в том, что при последовательном исполнении предыдущих множеств процессов, все процессы в очередном множестве смогут исполниться.
Входные данные совпадают с входными данными из предыдущей задачи. Обратите внимание на то, как должно выводиться каждое множество — все процессы в рамках множества должны быть отсортированы.
Формат входных данных
В первой строке дано число
?
n
(
1
≤
?
≤
1
0
5
)
(1≤n≤10
5
) — количество процессов. Далее дано
?
n строк. В
?
i-й строке первым числом идёт
?
?
a
i
— количество необходимых
?
i-му процессу процессов. Далее идет
?
?
a
i
чисел через пробел — их номера.
Формат выходных данных
В единственной строке выведите число
?
k — количество множеств, на которое необходимо разбить все процессы. В следующих
?
k строках выведите описание этих множеств: первым числом укажите размер множества
?
?
k
i
, а далее через пробел
?
?
k
i
чисел в порядке возрастания — номера процессов очередного множества.