Codeforces Round 707 (Div. 1, по задачам Открытой олимпиады школьников по программированию) |
---|
Закончено |
Даны две таблицы $$$A$$$ и $$$B$$$ размера $$$n \times m$$$.
Назовём сортировкой по столбцу следующее действие: выбирается столбец, и все строки упорядочиваются по значению в этом столбце, от строк, содержащих меньшие значения, к строкам с большими. В случае, если две строки имеют одинаковое значение в этом столбце, их порядок не меняется (такие сортировки называются стабильными).
Подобное поведение сортировки по столбцу можно найти практически в любом офисном приложении для работы с таблицами. Петя работает в одном из таких приложений, и у него открыта таблица $$$A$$$. Он хочет проделать ноль или более операций сортировки по столбцу, чтобы получить таблицу $$$B$$$.
Определите, может ли он это сделать, и если может, предложите ему алгоритм действий — последовательность столбцов, по которым нужно применить сортировку по столбцу. Обратите внимание, что не требуется минимизировать число действий.
В первой строке даны два числа $$$n$$$ и $$$m$$$ ($$$1 \le n, m \le 1500$$$) — размеры таблицы.
Каждая из следующих $$$n$$$ строк содержит $$$m$$$ целых чисел $$$a_{i,j}$$$ ($$$1 \le a_{i, j} \le n$$$) — элементы таблицы $$$A$$$.
Каждая из следующих $$$n$$$ строк содержит $$$m$$$ целых чисел $$$b_{i, j}$$$ ($$$1 \le b_{i, j} \le n$$$) — элементы таблицы $$$B$$$.
Если превратить таблицу $$$A$$$ в таблицу $$$B$$$ невозможно, выведите $$$-1$$$.
В противном случае выведите $$$k$$$ ($$$0 \le k \le 5000$$$) — количество сортировок, которые нужно сделать.
Затем выведите $$$k$$$ целых чисел $$$c_1, \ldots, c_k$$$ ($$$1 \le c_i \le m$$$) — номера столбцов, по которым нужно сделать сортировку.
Можно доказать, что если Петя может осуществить желаемое, то $$$5000$$$ действий ему хватит.
2 2 2 2 1 2 1 2 2 2
1 1
3 3 2 3 2 1 3 3 1 1 2 1 1 2 1 3 3 2 3 2
2 1 2
2 2 1 1 2 1 2 1 1 1
-1
4 1 2 2 2 1 1 2 2 2
1 1
Рассмотрим второй пример. После сортировки по первому столбцу таблица имеет вид
$$$$$$\begin{matrix} 1&3&3\\ 1&1&2\\ 2&3&2. \end{matrix}$$$$$$
После того, как мы отсортируем таблицу по второму столбцу, она станет
$$$$$$\begin{matrix} 1&1&2\\ 1&3&3\\ 2&3&2, \end{matrix}$$$$$$
что нам и нужно.
В третьем тесте любая сортировка не меняет таблицу, так как все столбцы уже отсортированы.
Название |
---|