#1184881 (PyPy3) No.3736 Purely Bool Hell

• 問題: No.3736 Purely Bool Hell
• ユーザー: 👑 kencho
• 提出日時: 2026-09-08 00:31:24
• 言語: PyPy3 (7.3.23 + ACL)
• 結果: AC
• 実行時間: 883 ms / 3,000 ms
• コード長: 5,517 bytes
• コンパイル時間: 65 ms
• コンパイル使用メモリ: 82,200 KB
• 実行使用メモリ: 133,892 KB
• 最終ジャッジ日時: 2026-09-19 13:15:08
• 合計ジャッジ時間: 12,831 ms
• ジャッジサーバーID （参考情報）: judge4_0 / judge3_0

ファイルパターン	結果
sample	AC * 1
other	AC * 39

ソースコード

import sys


def prepare_small_tables():
    """N=2,3 の全 0/1 行列から、指定値に対応する解を求めておく。"""
    tables = {}
    for n in (2, 3):
        table = {}
        for mask in range(1 << (n * n)):
            rows = [1] * n
            columns = [0] * n
            diagonals = [0] * (2 * n - 1)
            positions = []
            for r in range(n):
                for c in range(n):
                    value = (mask >> (r * n + c)) & 1
                    rows[r] &= value
                    columns[c] |= value
                    diagonals[r + c] ^= value
                    if value:
                        positions.append(r * n + c)

            # 下位から順に、行 AND・列 OR・反対角線 XOR を並べる。
            key = sum(value << i for i, value in
                      enumerate(rows + columns + diagonals))
            table[key] = positions
        tables[n] = table
    return tables


def solve_small(n, x, y, z, table):
    """N=2,3 は、各ビットの解を共通の全探索表から取り出す。"""
    answer = [0] * (n * n)
    values = x + y + z
    reversed_values = values[::-1]

    # 入力に現れない上位ビットは、全マスを 0 にすればよい。
    for bit in range(max(values).bit_length()):
        key = 0
        for value in reversed_values:
            key = (key << 1) | ((value >> bit) & 1)
        positions = table.get(key)
        if positions is None:
            return None
        bit_value = 1 << bit
        for position in positions:
            answer[position] |= bit_value
    return answer


def build_columns(n, active, target):
    """各列の OR と各反対角線の XOR を満たす 0/1 行列を構築する。"""
    center = n - 1
    matrix = bytearray(n * n)
    covered = bytearray(n)

    # 中央反対角線以外には、指定 XOR を満たす最大数の 1 を置く。
    for d in range(2 * n - 1):
        if d == center:
            continue
        left = max(0, d - n + 1)
        right = min(n - 1, d)
        columns = [c for c in range(left, right + 1) if active[c]]
        if (len(columns) & 1) != target[d]:
            if not columns:
                return None
            columns.pop()
        for c in columns:
            matrix[(d - c) * n + c] = 1
            covered[c] = 1

    # まだ 1 がない列を埋め、自由なマスがあれば中央反対角線の XOR を調整する。
    parity = 0
    optional = -1
    for c in range(n):
        if not active[c]:
            continue
        if covered[c]:
            optional = c
        else:
            matrix[(center - c) * n + c] = 1
            parity ^= 1
    if parity != target[center]:
        if optional < 0:
            return None
        matrix[(center - optional) * n + optional] = 1
    return matrix


def solve_large(n, x, y, z):
    """N>=4 は、解説の三つの場合に分けて各ビットを構築する。"""
    answer = [0] * (n * n)
    for bit in range(30):
        xb = [(value >> bit) & 1 for value in x]
        yb = [(value >> bit) & 1 for value in y]
        zb = [(value >> bit) & 1 for value in z]
        bit_value = 1 << bit
        has_x_one = any(xb)
        has_y_zero = not all(yb)

        if has_x_one and has_y_zero:
            return None

        if has_y_zero:
            # 全ての行の AND は 0。列に関する構築をそのまま使う。
            matrix = build_columns(n, yb, zb)
            if matrix is None:
                return None
            for position, value in enumerate(matrix):
                if value:
                    answer[position] |= bit_value

        elif has_x_one:
            # 転置・反転すると、同じ列に関する構築に帰着できる。
            active = [1 - value for value in xb]
            target = [
                zb[d] ^ (min(d + 1, 2 * n - 1 - d) & 1)
                for d in range(2 * n - 1)
            ]
            matrix = build_columns(n, active, target)
            if matrix is None:
                return None
            for r in range(n):
                for c in range(n):
                    if not matrix[c * n + r]:
                        answer[r * n + c] |= bit_value

        else:
            # 全ての行 AND が 0、全ての列 OR が 1。
            parity = bytearray(2 * n - 1)
            for r in range(n):
                c = (r + 2) % n
                answer[r * n + c] |= bit_value
                parity[r + c] ^= 1
            for d in range(2 * n - 1):
                r, c = d // 2, (d + 1) // 2
                if zb[d] != parity[d]:
                    answer[r * n + c] |= bit_value
    return answer


def solve(n, x, y, z, small_tables):
    if n == 1:
        return [x[0]] if x[0] == y[0] == z[0] else None
    if n <= 3:
        return solve_small(n, x, y, z, small_tables[n])
    return solve_large(n, x, y, z)


def main():
    small_tables = prepare_small_tables()
    it = iter(map(int, sys.stdin.buffer.read().split()))
    out = []
    for _ in range(next(it)):
        n = next(it)
        x = [next(it) for _ in range(n)]
        y = [next(it) for _ in range(n)]
        z = [next(it) for _ in range(2 * n - 1)]
        answer = solve(n, x, y, z, small_tables)
        if answer is None:
            out.append("-1")
        else:
            out.extend(" ".join(map(str, answer[r * n:(r + 1) * n]))
                       for r in range(n))
    print("\n".join(out))


if __name__ == "__main__":
    main()