#1171300 (Python3) No.3736 Purely Bool Hell

• 問題: No.3736 Purely Bool Hell
• ユーザー: 👑 kencho
• 提出日時: 2026-07-13 02:43:50
• 言語: Python3 (3.14.7 + numpy 2.5.2 + scipy 1.18.0 + ACL)
• 結果: TLE
• 実行時間: -
• コード長: 5,009 bytes
• コンパイル時間: 58 ms
• コンパイル使用メモリ: 15,872 KB
• 実行使用メモリ: 33,696 KB
• 最終ジャッジ日時: 2026-09-19 12:35:00
• 合計ジャッジ時間: 7,128 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge3_0

ファイルパターン	結果
sample	AC * 1
other	TLE * 1 -- * 38

ソースコード

import sys

# N<=3, X=0...0, Y=1...1 の場合だけ全探索
small = [{} for _ in range(4)]

for n in range(1, 4):
    full = (1 << n) - 1

    for a in range(1 << (n * n)):
        rows = [(a >> (i * n)) & full for i in range(n)]

        # 各行に0が必要
        if any(row == full for row in rows):
            continue

        # 各列に1が必要
        if any(not any(row >> j & 1 for row in rows)
               for j in range(n)):
            continue

        z = 0
        for i, row in enumerate(rows):
            for j in range(n):
                z ^= (row >> j & 1) << (i + j)

        small[n][z] = a


# active[j]=1 の各列に少なくとも1個の1を置き、
# 各反対角線の XOR を target にする
def build(n, active, target):
    a = [0] * (n * n)
    used = [0] * n
    middle = n - 1

    # 中央以外の XOR を合わせる
    for d, value in enumerate(target):
        if d == middle or value == 0:
            continue

        left = max(0, d - n + 1)
        right = min(n, d + 1)

        j = next(
            (j for j in range(left, right) if active[j]),
            -1
        )

        if j < 0:
            return None

        a[(d - j) * n + j] = 1
        used[j] = 1

    # 中央の XOR を調整する自由度が必要な場合、
    # XOR=0 の反対角線に2個置く
    if not any(used) and (sum(active) & 1) != target[middle]:
        for d, value in enumerate(target):
            if d == middle or value:
                continue

            left = max(0, d - n + 1)
            right = min(n, d + 1)

            columns = [
                j for j in range(left, right)
                if active[j]
            ][:2]

            if len(columns) == 2:
                for j in columns:
                    a[(d - j) * n + j] = 1
                    used[j] = 1
                break
        else:
            return None

    # 未使用の active 列を中央で埋める
    parity = 0
    free_column = -1

    for j in range(n):
        if not active[j]:
            continue

        if used[j]:
            free_column = j
        else:
            a[(middle - j) * n + j] = 1
            parity ^= 1

    if parity != target[middle]:
        if free_column < 0:
            return None
        a[(middle - free_column) * n + free_column] = 1

    return a


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 = [0] * (n * n)

    for bit in range(30):
        x = [value >> bit & 1 for value in X]
        y = [value >> bit & 1 for value in Y]
        z = [value >> bit & 1 for value in Z]

        has_x_one = any(x)
        all_y_one = all(y)

        # 全て1の行と全て0の列が交差する
        if has_x_one and not all_y_one:
            a = None

        elif not all_y_one:
            # Y=0 の列によって全行の AND=0 が保証される
            a = build(n, y, z)

        elif has_x_one:
            # B=1-A を転置して build を使う
            diagonal_count = 2 * n - 1

            target = [
                z[d] ^ (min(d + 1, diagonal_count - d) & 1)
                for d in range(diagonal_count)
            ]

            b_transposed = build(
                n,
                [1 - value for value in x],
                target
            )

            if b_transposed is None:
                a = None
            else:
                a = [
                    1 - b_transposed[j * n + i]
                    for i in range(n)
                    for j in range(n)
                ]

        elif n <= 3:
            z_mask = sum(value << d for d, value in enumerate(z))
            matrix_mask = small[n].get(z_mask)

            if matrix_mask is None:
                a = None
            else:
                a = [
                    matrix_mask >> position & 1
                    for position in range(n * n)
                ]

        else:
            # 全 X=0, 全 Y=1, N>=4
            diagonal_count = 2 * n - 1
            a = [0] * (n * n)
            parity = [0] * diagonal_count

            # 各列に1個ずつ1を置く
            for i in range(n):
                j = (i + 2) % n
                a[i * n + j] = 1
                parity[i + j] ^= 1

            # 各反対角線の代表マスで XOR を調整する
            for d in range(diagonal_count):
                i = d // 2
                j = d - i
                a[i * n + j] = z[d] ^ parity[d]

        if a is None:
            answer = None
            break

        for position, value in enumerate(a):
            answer[position] |= value << bit

    if answer is None:
        out.append("-1")
    else:
        out += [
            " ".join(map(
                str,
                answer[i * n:(i + 1) * n]
            ))
            for i in range(n)
        ]

print("\n".join(out))