Codeforces Round 555 (Div. 3) |
---|
Закончено |
Задана двоичная матрица $$$a$$$ размера $$$n \times m$$$. Двоичная матрица — это такая матрица, в которой каждый элемент равен либо $$$0$$$, либо $$$1$$$.
Вы можете совершить несколько (возможно, ноль) операций над этой матрицей. В течение каждой операции вы можете обратить либо строку этой матрицы, либо столбец этой матрицы. Формально, обращение строки — это изменение всех значений в этой строке на противоположные ($$$0$$$ на $$$1$$$, $$$1$$$ на $$$0$$$). Обращение столбца — это изменение всех значений в этом столбце на противоположные.
Ваша задача — отсортировать изначальную матрице при помощи какой-то последовательности операций. Матрица является отсортированной, если массив $$$[a_{1, 1}, a_{1, 2}, \dots, a_{1, m}, a_{2, 1}, a_{2, 2}, \dots, a_{2, m}, \dots, a_{n, m - 1}, a_{n, m}]$$$ отсортирован в неубывающем порядке.
Первая строка входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n, m \le 200$$$) — количество строк и количество столбцов в матрице.
Следующие $$$n$$$ строк содержат $$$m$$$ целых чисел каждая. $$$j$$$-й элемент в $$$i$$$-й строке равен $$$a_{i, j}$$$ ($$$0 \le a_{i, j} \le 1$$$) — элементу $$$a$$$, стоящему на позиции $$$(i, j)$$$.
Если невозможно получить отсортированную матрицу, выведите «NO» в первой строке.
Иначе выведите «YES» в первой строке. Во второй строке выведите строку $$$r$$$ длины $$$n$$$. $$$i$$$-й символ этой строки $$$r_i$$$ должен быть равен '1', если $$$i$$$-я строка матрицы должна быть обращена, и '0' иначе. В третьей строке выведите строку $$$c$$$ длины $$$m$$$. $$$j$$$-й символ этой строки $$$c_j$$$ должен быть равен '1', если $$$j$$$-й столбец матрицы должен быть обращен, и '0' иначе. Если существует несколько возможных ответов, вы можете вывести любой из них.
2 2 1 1 0 1
YES 00 10
3 4 0 0 0 1 0 0 0 0 1 1 1 1
YES 010 0000
3 3 0 0 0 1 0 1 1 1 0
NO
Название |
---|