結果

問題 No.3736 Purely Bool Hell
コンテスト
ユーザー 👑 kencho
提出日時 2026-09-03 04:45:01
言語 PyPy3
(7.3.23 + ACL)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 2,119 ms / 3,000 ms
+ 559µs
コード長 3,822 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 73 ms
コンパイル使用メモリ 82,560 KB
実行使用メモリ 135,808 KB
最終ジャッジ日時 2026-09-19 13:02:18
合計ジャッジ時間 16,744 ms
ジャッジサーバーID
（参考情報） 		judge1_1 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 39
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys

small = [None] * 4
for n in range(1, 4):
    table = {}
    for mask in range(1 << (n * n)):
        xm = ym = zm = 0
        for r in range(n):
            bit = 1
            for c in range(n): bit &= mask >> (r * n + c) & 1
            xm |= bit << r
        for c in range(n):
            bit = 0
            for r in range(n): bit |= mask >> (r * n + c) & 1
            ym |= bit << c
        for r in range(n):
            for c in range(n):
                if mask >> (r * n + c) & 1: zm ^= 1 << (r + c)
        table[xm | ym << n | zm << (2 * n)] = mask
    small[n] = table

def build_columns(n, active, target):
    center = n - 1
    a = bytearray(n * n)
    covered = bytearray(n)
    for d in range(2 * n - 1):
        if d == center or not target[d]: continue
        for c in range(max(0, d - n + 1), min(n - 1, d) + 1):
            if active[c]:
                a[(d - c) * n + c] = 1; covered[c] = 1; break
        else: return None
    active_count = sum(active)
    if not any(active[c] and covered[c] for c in range(n)) and (active_count & 1) != target[center]:
        found = False
        for d in range(2 * n - 1):
            if d == center or target[d]: continue
            cols = [c for c in range(max(0, d - n + 1), min(n - 1, d) + 1) if active[c]][:2]
            if len(cols) == 2:
                for c in cols: a[(d - c) * n + c] = 1; covered[c] = 1
                found = True; break
        if not found: return None
    parity = 0
    optional = -1
    for c in range(n):
        if not active[c]: continue
        if covered[c]: optional = c
        else: a[(center - c) * n + c] = 1; parity ^= 1
    if parity != target[center]:
        if optional < 0: return None
        a[(center - optional) * n + optional] = 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)
    possible = True
    for bit in range(30):
        xb = [(v >> bit) & 1 for v in x]
        yb = [(v >> bit) & 1 for v in y]
        zb = [(v >> bit) & 1 for v in z]
        if n <= 3:
            key = sum(v << i for i, v in enumerate(xb)) | sum(v << (n + i) for i, v in enumerate(yb)) | sum(v << (2 * n + i) for i, v in enumerate(zb))
            mask = small[n].get(key)
            if mask is None: possible = False; break
            for p in range(n * n):
                if mask >> p & 1: answer[p] |= 1 << bit
            continue
        has_x_one, has_y_zero = any(xb), not all(yb)
        if has_x_one and has_y_zero:
            possible = False; break
        if has_y_zero:
            matrix = build_columns(n, yb, zb)
            if matrix is None: possible = False; break
            for p, value in enumerate(matrix):
                if value: answer[p] |= 1 << bit
        elif has_x_one:
            active = [not value for value in xb]
            target = [zb[d] ^ ((d + 1 if d < n else 2 * n - 1 - d) & 1) for d in range(2 * n - 1)]
            matrix = build_columns(n, active, target)
            if matrix is None: possible = False; break
            for r in range(n):
                for c in range(n):
                    if not matrix[c * n + r]: answer[r * n + c] |= 1 << bit
        else:
            parity = bytearray(2 * n - 1)
            for r in range(n):
                c = (r + 2) % n
                answer[r * n + c] |= 1 << bit; parity[r + c] ^= 1
            for d in range(2 * n - 1):
                r, c = d // 2, d - d // 2
                if zb[d] ^ parity[d]: answer[r * n + c] |= 1 << bit
    if not possible: out.append("-1")
    else: out.extend(" ".join(map(str, answer[r * n:(r + 1) * n])) for r in range(n))
print("\n".join(out))
0