Codeforces Round 659 (Div. 1) |
---|
Закончено |
Коала Коа имеет матрицу $$$A$$$ из $$$n$$$ строк и $$$m$$$ столбцов. Элементы этой матрицы — различные целые числа от $$$1$$$ до $$$n \cdot m$$$ (каждое число от $$$1$$$ до $$$n \cdot m$$$ встречается в матрице ровно один раз).
Для любой матрицы $$$M$$$ из $$$n$$$ строк и $$$m$$$ столбцов определим следующее:
Коа определяет $$$S(A) = (X, Y)$$$ как спектр $$$A$$$, где $$$X$$$ — множество максимумов в строках $$$A$$$, а $$$Y$$$ — множество максимумов в столбцах $$$A$$$ соответственно.
Более формально:
Коа просит вас найти некоторую матрицу $$$A'$$$ из $$$n$$$ строк и $$$m$$$ столбцов такую, чтобы каждое число от $$$1$$$ до $$$n \cdot m$$$ встречалось в матрице ровно один раз, и выполнялись следующие условия:
Более формально: $$$t$$$ является битоническим, если существует некоторая позиция $$$p$$$ ($$$1 \le p \le k$$$) такая, что: $$$t_1 < t_2 < \ldots < t_p > t_{p+1} > \ldots > t_k$$$.
Помогите Коа найти такую матрицу, или определить, что ее не существует.
Первая строка содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n, m \le 250$$$) — количества строк и столбцов в $$$A$$$.
Каждая из следующих $$$n$$$ строк содержит $$$m$$$ целых чисел. $$$j$$$-е целое число в $$$i$$$-й строке обозначает элемент $$$A_{ij}$$$ ($$$1 \le A_{ij} \le n \cdot m$$$) матрицы $$$A$$$. Гарантируется, что каждое число от $$$1$$$ до $$$n \cdot m$$$ встречается ровно один раз среди элементов матрицы.
Если такой матрицы не существует, в отдельной строке выведите $$$-1$$$.
В противном случае вы должны вывести $$$n$$$ строк, каждая из которых должная состоять из $$$m$$$ целых чисел, разделенных пробелом — описание $$$A'$$$.
$$$j$$$-е число в $$$i$$$-й строке обозначает элемент $$$A'_{ij}$$$.
Каждое число от $$$1$$$ до $$$n \cdot m$$$ должно встречаться в $$$A'$$$ ровно один раз, каждая строка и столбец в $$$A'$$$ должны быть битоническими и должно выполняться $$$S(A) = S(A')$$$.
Если ответов несколько, выведите любой.
3 3 3 5 6 1 7 9 4 8 2
9 5 1 7 8 2 3 6 4
2 2 4 1 3 2
4 1 3 2
3 4 12 10 8 6 3 4 5 7 2 11 9 1
12 8 6 1 10 11 9 2 3 4 5 7
Проанализируем первый пример:
Для матрицы $$$A$$$:
Для матрицы $$$A'$$$:
Название |
---|