結果

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

ソースコード

diff #
raw source code 

import sys
from bisect import bisect_left

def small(n,X,Y,Z):
    if n==1:return [X[0]] if X[0]==Y[0]==Z[0] else None
    M=(1<<max(max(X),max(Y),max(Z)).bit_length())-1
    if n==2:
        a,q,d=Z; A=[a,0,0,d]; r=M
        for b in (0,M):
            c=b^q
            e=(X[0]^(a&b))|(X[1]^(c&d))|(Y[0]^(a|c))|(Y[1]^(b|d))
            t=r&(M^e); A[1]|=b&t; A[2]|=c&t; r^=t
        return None if r else A
    a,i=Z[0],Z[4]; A=[a,0,0,0,0,0,0,0,i]; r=M
    for s in range(16):
        b=M if s&1 else 0; c=M if s&2 else 0
        e=M if s&4 else 0; f=M if s&8 else 0
        d=b^Z[1]; g=c^e^Z[2]; h=f^Z[3]
        v=(X[0]^(a&b&c))|(X[1]^(d&e&f))|(X[2]^(g&h&i))
        v|=(Y[0]^(a|d|g))|(Y[1]^(b|e|h))|(Y[2]^(c|f|i))
        t=r&(M^v)
        if t:
            A[1]|=b&t; A[2]|=c&t; A[3]|=d&t; A[4]|=e&t
            A[5]|=f&t; A[6]|=g&t; A[7]|=h&t; r^=t
            if not r:break
    return None if r else A

def build(n,p,q):
    m=n-1; u=bytearray(n); A=[]; c=0
    for d,v in enumerate(q):
        if d==m or not v:continue
        l=max(0,d-m); r=min(m,d); k=bisect_left(p,l)
        if k==len(p) or p[k]>r:return
        j=p[k]; A.append((d-j)*n+j); u[j]=1; c=1
    if not c and (len(p)&1)!=q[m]:
        for d,v in enumerate(q):
            if d==m or v:continue
            l=max(0,d-m); r=min(m,d); k=bisect_left(p,l)
            if k+1<len(p) and p[k+1]<=r:
                for j in p[k:k+2]:A.append((d-j)*n+j); u[j]=1
                break
        else:return
    s=0; f=-1
    for j in p:
        if u[j]:f=j
        else:A.append((m-j)*n+j); s^=1
    if s!=q[m]:
        if f<0:return
        A.append((m-f)*n+f)
    return A

def solve(n,X,Y,Z):
    if n<4:return small(n,X,Y,Z)
    L=max(max(X),max(Y),max(Z)).bit_length(); D=2*n-1
    M=(1<<L)-1; ox=0; ay=M
    for v in X:ox|=v
    for v in Y:ay&=v
    if ox&(M^ay):return
    A=[0]*(n*n); off=[0]*(n*n); s=M^ay
    while s:
        w=s&-s; s-=w
        p=[j for j,v in enumerate(Y) if v&w]
        a=build(n,p,[bool(v&w) for v in Z])
        if a is None:return
        for k in a:A[k]|=w
    s=ox
    while s:
        w=s&-s; s-=w
        p=[i for i,v in enumerate(X) if not v&w]
        a=build(n,p,[bool(v&w)^bool(min(d+1,D-d)&1) for d,v in enumerate(Z)])
        if a is None:return
        for k in a:
            i,j=divmod(k,n); off[j*n+i]|=w
    g=ay^ox
    if g:
        q=bytearray(D)
        for i in range(n):
            j=(i+2)%n; A[i*n+j]|=g; q[i+j]^=1
        for d,v in enumerate(Z):
            A[(d//2)*n+(d+1)//2]|=(v^(g if q[d] else 0))&g
    for i in range(n*n):A[i]=(A[i]|ox)^off[i]
    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)]
    A=solve(n,X,Y,Z)
    if A is None:out.append("-1")
    else:
        for i in range(n):
            out.append(" ".join(map(str,A[i*n:(i+1)*n])))
sys.stdout.write("\n".join(out)+"\n")
0