printРабочее место участника

printЗадачи

1435. Катание на лифте

Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Однажды `k` учеников решили прогулять школу и покататься на лифте. Для этого они направились в дом с самым большим в городе лифтом.
Катание на лифте проходило следующим образом: школьники одновременно нажимали на случайные кнопки этажей (несколько школьников могли нажать на одну и ту же кнопку). При этом срабатывала одна из нажатых кнопок, после чего лифт всегда ехал либо вверх, либо вниз на соответствующий этаж. Далее операция повторялась.
После `n`-го раза лифт приехал на какой-то этаж и сломался – не открыл двери. Школьники помнят, какие кнопки были ими нажаты перед каждой поездкой и в каком направлении при этом перемещался лифт (вверх или вниз). Для вызова диспетчера необходимо узнать, на каких этажах может находиться лифт. Помогите им это выяснить. Известно, что сначала лифт стоял на первом этаже.
Формат входного файла
Первая строка входного файла содержит целые числа `n\ k` – количество поездок на лифте и количество школьников соответственно.
Следующие n строк содержат `k\ +\ 1` чисел каждая: `d_i\ f_{1,i}\ …\ f_{k,i}` – направление движения лифта и номера этажей, кнопки которых были нажаты. Этажи нумеруются с 1. Если `d_i` равно 1, то после одновременного нажатия на кнопки этажей `f_{1,i},\ …,\ f_{k,i}` лифт поехал вверх, на один из этих этажей. Если `d_i` равно `-1` – лифт поехал вниз.
Формат выходного файла
Выходной файл должен содержать последовательность целых чисел – номеров этажей, на которых может находится сломанный лифт, упорядоченную по возрастанию.
Если данные школьников противоречивы (т. е. хотя бы одна из описанных поездок невозможна), выходной файл должен содержать единственное число `-1`.
Ограничения
`1\ ≤\ n,\ k\ ≤\ 100`, `1\ ≤\ f_{i,j}\ ≤\ 1000`

Пример ввода 1

4 4
 1  4 8 5 7
 1  3 6 9 3
 1  1 2 4 4
-1  1 2 1 4

Пример вывода 1

-1

Пример ввода 2

3 4
 1  4 8 5 4
-1  6 9 6 4
-1  3 8 5 6

Пример вывода 2

3 5

Пример ввода 3

2 2
1  1 1
1  1 2

Пример вывода 3

-1
Источник: Весенний турнир ДВГУ, 2010
loading