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

Ниже подробное решение задачи с объяснениями и рабочий код на Python.

Идея решения

• Пусть мы решаем задачу так, чтобы после инверсий все элементы стали одинаковыми (0 или 1). Пусть r_i — флаг инверсии строки i, c_j — флаг инверсии столбца j.
• После инверсий значение в клетке (i, j) станет a_ij xor r_i xor c_j.
• Пусть итоговое значение равно t (0 или 1). Тогда для всех i, j выполняется: a_ij xor r_i xor c_j = t. Это эквивалентно a_ij xor t = r_i xor c_j.
• Возьмем фиксированное t (попробуем t = 0 и t = 1). Пусть строка 0 не инвертируется (r_0 = 0). Тогда столбцы можно определить как c_j = a_0j xor t (для каждой j). Далее для каждой строки i нужно найти r_i так, чтобы для всех столбцов j выполнялось a_ij xor t = r_i xor c_j.
• Если для некоторой i и любого j равенство нарушается, то для данного t решение невозможно. Пробуем другое t. Если для t = 0 или t = 1 решение находится — выводим YES и соответствующие маски для строк и столбцов. Если ни для одного t решения нет — NO.

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

1. Прочитать матрицу A размером Q x N (символы '0'/'1').
2. Для t в {0, 1}:
   • Вычислить c_j = (a_0j xor t) для всех j.
   • Для i = 0 задать r_0 = 0.
   • Для каждой i > 0 вычислить r_i = (a_i0 xor t) xor c_0.
   • Проверить, что для всех i, j выполняется (a_ij xor t) == (r_i xor c_j). Если да — нашли решение.
3. Если нашли решение для хотя бы одного t, вывести YES, затем строки из r_i и c_j (1 — инвертировать такую строку/столбец, 0 — оставить как есть). Если решений нет — NO.

Сложность

• Время: O(2 * Q * N) ∈ O(QN).
• Память: O(Q + N) для хранения флагов.

Рабочий код на Python

import sys

def solve(): data = sys.stdin.read().strip().split() if not data: return it = iter(data) Q = int(next(it)) N = int(next(it)) mat = [] for _ in range(Q): s = next(it) # При необходимости можно проверить длину, но предполагаем корректный вход mat.append(s)

def attempt(t):
    # c_j = a_0j xor t
    c = [ ((1 if mat[0][j] == '1' else 0) ^ t) for j in range(N) ]
    r = [0] * Q
    # r_0 уже 0
    for i in range(1, Q):
        # r_i = (a_i0 xor t) xor c_0
        ri = ((1 if mat[i][0] == '1' else 0) ^ t) ^ c[0]
        r[i] = ri
        for j in range(N):
            bij = ((1 if mat[i][j] == '1' else 0) ^ t)
            if (ri ^ c[j]) != bij:
                return None
    return r, c

ans = None
for t in (0, 1):
    res = attempt(t)
    if res is not None:
        ans = res
        break

if ans is None:
    print("NO")
    return

r, c = ans
print("YES")
print(''.join('1' if x else '0' for x in r))
print(''.join('1' if x else '0' for x in c))

if name == "main": solve()

Как использовать

• Вход: Первая строка: Q N (1 ≤ Q, N ≤ 100) Далее Q строк по N символов 0/1 — исходный кадр.

• Выход: NO — если восстановить однородный кадр невозможно; иначе YES, затем две строки:

  • строка из Q символов 0/1 — инвертировать ли соответствующие строки (1 — инверсия);
  • строка из N символов 0/1 — инвертировать ли столбцы (1 — инверсия).

Если корректных ответов несколько, можно вернуть любой.