Ограничение по времени: 1 секунда Ограничение по памяти: 256 мегабайт Вы настраиваете предобработку данных для компьютерного зрения. Камера выдаёт бинарный кадр — прямоугольную…

Коротко о задаче

• Можно инвертировать произвольную подмножество строк и произвольную подмножество столбцов.
• Нужно получить однородный кадр (все нули или все единицы).
• Пусть исходная матрица A размеру Q x N. Пусть r_i = 1, если инвертируем строку i, иначе 0; c_j аналогично для столбца j.
• После инверсий клетка (i, j) станет A[i][j] XOR r_i XOR c_j.
• Требуется либо A[i][j] XOR r_i XOR c_j = 0 для всех i,j, либо = 1 для всех i,j.

Идея решения

• Попробуем оба варианта: сделать кадр нулём (k = 0) или единицей (k = 1).
• Для фиксированного k запишем B[i][j] = A[i][j] XOR k. Нам нужно разложить B как r_i XOR c_j. Для этого достаточно подобрать r и c так, чтобы B[i][j] = r_i XOR c_j для всех i,j.
• Одно конструктивное решение: зафиксируем r_0 = 0. Тогда:
  • c_j = B[0][j] (значения первой строки задают столбцовые инверсии).
  • r_i = B[i][0] XOR c_0 (значение первого столбца вместе с c_0 задаёт остальные строки).
  • Проверяем, что для всех i,j выполняется B[i][j] = r_i XOR c_j.
• Если для k = 0 или k = 1 найдётся такая пара (r, c), значит можно получить однородный кадр; выведем YES и сами маски r и c. Иначе – NO.

Пошаговый алгоритм

1. Прочитать Q, N и матрицу A (символы '0'/'1').
2. Для k в {0, 1}:
   • Вычислить B[i][j] = A[i][j] XOR k.
   • Задать r_0 = 0.
   • Задать c_j = B[0][j] для всех j.
   • Задать r_i = B[i][0] XOR c_0 для всех i.
   • Проверить: для всех i, j выполняется B[i][j] == (r_i XOR c_j).
   • Если выполняется, вывести: YES строку из Q бит (r_i, где 1 означает инверсию строки) строку из N бит (c_j, где 1 означает инверсию столбца) и завершить программу.
3. Если ни для k=0, ни для k=1 подход не нашёлся, вывести NO.

Пояснение корректности

• Если существует набор r и c такой, что A[i][j] XOR r_i XOR c_j ровно равен константе k, то для этого k матрица B = A XOR k удовлетворяет B[i][j] = r_i XOR c_j. Первая строка даёт c_j, а первый столбец вместе с c_0 задаёт остальные r_i. Проверка на всех клетках гарантирует корректность.
• Это решение зафиксировано в O(QN) для каждого k, итого O(QN), что комфортно для Q,N ≤ 100.

Пример разборов

• Пример 1: Ввод: 3 4 0110 0010 1111 Попробуем k=0, получаем B=A. Конструктивно строим r и c и проверяем. Проверка не проходит, значит соответствие не найдено для k=0. Попробуем k=1, B = A XOR 1. Повторяем построение и проверку. Проверка снова не проходит. Значит: NO.
• Пример 2: Ввод: 2 2 10 01 k=0 даёт совместимость: можно выбрать r=[0,1], c=[1,0] (или эквивалентные). Вывод может быть: YES 10 01 Здесь строки инвертируются: только 2-я, столбцы: только 1-й.
• Пример 3: Ввод: 1 1 0 k=0 даёт r=[0], c=[0]. Вывод: YES 0 0

Формат вывода

• Если восстановить однородный кадр невозможно: вывести NO.
• Иначе: YES затем строка из Q символов 0/1 — маска инверсий строк (1 означает инвертировать соответствующую строку) затем строка из N символов 0/1 — маска инверсий столбцов (1 означает инвертировать соответствующий столбец)

Замечания по реализации

• Обработку можно выполнять в памяти целиком, размеры ≤ 100x100.
• Можно реализовать на любом языке; в псевдокоде выше приведён понятный алгоритм.
• При наличии нескольких решений можно вывести любое.

Если хотите, могу привести конкретную реализацию на выбранном языке (например, Python) или прогнать ещё один конкретный пример пошагово.