Problem:


Score : 600 points

Problem Statement

Given are an integer N and arrays S, T, U, and V, each of length N.
Construct an N×N matrix a that satisfy the following conditions:

a_{i,j} is an integer.

0 \leq a_{i,j}  \lt 2^{64}.

If S_{i} = 0, the bitwise AND of the elements in the i-th row is U_{i}.

If S_{i} = 1, the bitwise OR of the elements in the i-th row is U_{i}.

If T_{i} = 0, the bitwise AND of the elements in the i-th column is V_{i}.

If T_{i} = 1, the bitwise OR of the elements in the i-th column is V_{i}.

However, there may be cases where no matrix satisfies the conditions.

Constraints

All values in input are integers.

 1 \leq N \leq 500 

 0 \leq S_{i} \leq 1 

 0 \leq T_{i} \leq 1  

 0 \leq U_{i} \lt 2^{64}  

 0 \leq V_{i} \lt 2^{64}  

Input

Input is given from Standard Input in the following format:

N
S_{1} S_{2} ...  S_{N}
T_{1} T_{2} ...  T_{N}
U_{1} U_{2} ...  U_{N}
V_{1} V_{2} ...  V_{N}

Output

If there exists a matrix that satisfies the conditions, print one such matrix in the following format:

a_{1,1} ...  a_{1,N}
:
a_{N,1} ...  a_{N,N}

Note that any matrix satisfying the conditions is accepted.

If no matrix satisfies the conditions, print -1.

Sample Input 1

2
0 1
1 0
1 1
1 0

Sample Output 1

1 1
1 0

In Sample Input 1, we need to find a matrix such that:

the bitwise AND of the elements in the 1-st row is 1;

the bitwise OR of the elements in the 2-nd row is 1;

the bitwise OR of the elements in the 1-st column is 1;

the bitwise AND of the elements in the 2-nd column is 0.

Sample Input 2

2
1 1
1 0
15 15
15 11

Sample Output 2

15 11
15 11



Sample input:
2
0 1
1 0
1 1
1 0


Sample output:
1 1
1 0

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    def ok():
        for s,u,row in zip(ss,uu,ans):
            b=row[0]
            if s:
                for a in row[1:]:b|=a
                if b!=u:return False
            else:
                for a in row[1:]:b&=a
                if b!=u:return False
        for t,v,col in zip(tt,vv,zip(*ans)):
            b=col[0]
            if t:
                for a in col[1:]:b|=a
                if b!=v:return False
            else:
                for a in col[1:]:b&=a
                if b!=v:return False
        return True

    mxk=64
    n=II()
    ss=LI()
    tt=LI()
    uu=LI()
    vv=LI()
    # 2進数の各桁ごとに考える
    # bit[k][i][j]...答えのi行j列目のkけた目が入る
    bit=[[[-1]*n for _ in range(n)] for _ in range(mxk)]
    # ORが0⇒その行（または列）はすべて0
    # ANDが1⇒その行（または列）はすべて1
    # と、確定するので、そのマスを埋める
    for i,(s,u) in enumerate(zip(ss,uu)):
        for k in range(mxk):
            if u>>k&1==1-s:
                for j in range(n):bit[k][i][j]=1-s
    for j,(t,v) in enumerate(zip(tt,vv)):
        for k in range(mxk):
            if v>>k&1==1-t:
                for i in range(n):bit[k][i][j]=1-t
    # 確定しなかった（値が初期値-1の）マスについて決めていく
    # ORが1ならば、少なくとも1マスは1が必要
    # ANDが0ならば、少なくとも1マスは0が必要
    for k in range(mxk):
        # -1を含む行と列を調べる
        ii=[]
        jj=[]
        for i,row in enumerate(bit[k]):
            if -1 in row:ii.append(i)
        for j,col in enumerate(zip(*bit[k])):
            if -1 in col:jj.append(j)
        # -1がなければ何もしない
        if not ii:continue
        # 行が1つしかない場合
        # 行の条件を満たすデフォルト値dfを決めておく
        # それぞれの列の条件をみながら、すでに条件を満たしていればデフォルト値を
        # 満たしていなければ、満たすような値を-1と置き換えていく
        if len(ii)==1:
            df=ss[ii[0]]
            for j in jj:
                for i in range(n):
                    if bit[k][i][j]==tt[j]:
                        bit[k][ii[0]][j]=df
                        break
                else:
                    bit[k][ii[0]][j] = tt[j]
        # 列が1つしかない場合
        # 行のときと同じやり方
        elif len(jj) == 1:
            df = tt[jj[0]]
            for i in ii:
                for j in range(n):
                    if bit[k][i][j] == ss[i]:
                        bit[k][i][jj[0]] = df
                        break
                else:
                    bit[k][i][jj[0]] = ss[i]
        # 行も列も2つ以上あるとき
        # すべての行と列に0と1が入るようにすればいい
        else:
            # まず、すべて0にする
            for i in ii:
                for j in jj:
                    bit[k][i][j] = 0
            # 行と列の要素数が違う場合、短い方に付け足して同じ長さにする
            # 付け足すのはどの要素でもいい（今回は先頭にした）
            if len(ii)<len(jj):ii+=[ii[0]]*(len(jj)-len(ii))
            if len(ii)>len(jj):jj+=[jj[0]]*(len(ii)-len(jj))
            # 行と列を同時にずらしながら1を埋める
            # 各行列に最低1つは1を入れていく感じ
            for i,j in zip(ii,jj):
                bit[k][i][j]=1
    #for k in range(mxk):
        #print("k=",k)
        #p2D(bit[k])
    # 各桁をみながら答えを作る
    ans=[[0]*n for _ in range(n)]
    for k in range(mxk):
        for i in range(n):
            for j in range(n):
                ans[i][j]+=bit[k][i][j]<<k
    # 条件を満たしているかの確認
    if ok():
        for row in ans:
            print(*row)
    else:print(-1)

main()

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
s=list(map(int,input().split()))
t=list(map(int,input().split()))
f=list(map(int,input().split()))
g=list(map(int,input().split()))
ans=[n*[0]for _ in range(n)]
for b in range(64):
  e=1<<b
  u=[a&e for a in f]
  v=[a&e for a in g]
  l=[0]*n
  m=[0]*n
  for i in range(n):
    for j in range(n):
      if(u[i]&v[j])|((s[i]^1)*u[i])|((t[j]^1)*v[j]):ans[i][j]|=e;l[i]+=1;m[j]+=1
  for i in range(n):
    for j in range(n):
      if s[i]*u[i]*(l[i]==0)*(t[j]^1)*(n-m[j]>1):ans[i][j]|=e;l[i]+=1;m[j]+=1
      if t[j]*v[j]*(m[j]==0)*(s[i]^1)*(n-l[i]>1):ans[i][j]|=e;l[i]+=1;m[j]+=1
h=ans[0][:]
w=[i[0]for i in ans]
for i in range(n):
  for j in range(n):
    if s[i]:w[i]|=ans[i][j]
    else:w[i]&=ans[i][j]
    if t[j]:h[j]|=ans[i][j]
    else:h[j]&=ans[i][j]
if(g!=h)|(f!=w):print(-1);exit() 
for i in ans:print(*i)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
s=list(map(int,input().split()))
t=list(map(int,input().split()))
f=list(map(int,input().split()))
g=list(map(int,input().split()))
ans=[n*[0]for _ in range(n)]
for b in range(64):
  u=[(a&1<<b)//(1<<b)for a in f]
  v=[(a&1<<b)//(1<<b)for a in g]
  q=[n*[0]for _ in range(n)]
  l=[0]*n
  m=[0]*n
  for i in range(n):
    for j in range(n):
      if(u[i]&v[j])|((s[i]^1)*u[i])|((t[j]^1)*v[j]):q[i][j]+=1;l[i]+=1;m[j]+=1
  for i in range(n):
    if s[i]*u[i]*(l[i]==0):
      for j in range(n):
        if(t[j]^1)*(n-m[j]>1):q[i][j]=u[i];m[j]+=1;break
  for j in range(n):
    if t[j]*v[j]*(m[j]==0):
      for i in range(n):
        if(s[i]^1)*(n-l[i]>1):q[i][j]=v[j];l[i]+=1;break
  for i in range(n):
    for j in range(n):ans[i][j]|=q[i][j]<<b
h=ans[0][:]
w=[i[0]for i in ans]
for i in range(n):
  for j in range(n):
    if s[i]:w[i]|=ans[i][j]
    else:w[i]&=ans[i][j]
    if t[j]:h[j]|=ans[i][j]
    else:h[j]&=ans[i][j]
if(g!=h)|(f!=w):print(-1);exit() 
for i in ans:print(*i)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
s=list(map(int,input().split()))
t=list(map(int,input().split()))
f=list(map(int,input().split()))
g=list(map(int,input().split()))
ans=[n*[0]for _ in range(n)]
for b in range(64):
  u=[(a&1<<b)>>b for a in f]
  v=[(a&1<<b)>>b for a in g]
  q=[n*[0]for _ in range(n)]
  l=[0]*n
  m=[0]*n
  for i in range(n):
    for j in range(n):
      if(u[i]&v[j])|((s[i]^1)*u[i])|((t[j]^1)*v[j]):q[i][j]+=1;l[i]+=1;m[j]+=1
  for i in range(n):
    for j in range(n):
      if s[i]*u[i]*(l[i]==0)*(t[j]^1)*(n-m[j]>1):q[i][j]=u[i];l[i]+=1;m[j]+=1
      if t[j]*v[j]*(m[j]==0)*(s[i]^1)*(n-l[i]>1):q[i][j]=v[j];l[i]+=1;m[j]+=1
  for i in range(n):
    for j in range(n):ans[i][j]|=q[i][j]<<b
h=ans[0][:]
w=[i[0]for i in ans]
for i in range(n):
  for j in range(n):
    if s[i]:w[i]|=ans[i][j]
    else:w[i]&=ans[i][j]
    if t[j]:h[j]|=ans[i][j]
    else:h[j]&=ans[i][j]
if(g!=h)|(f!=w):print(-1);exit() 
for i in ans:print(*i)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
s=list(map(int,input().split()))
t=list(map(int,input().split()))
f=list(map(int,input().split()))
g=list(map(int,input().split()))
ans=[n*[0]for _ in range(n)]
for b in range(64):
  u=[(a&1<<b)//(1<<b)for a in f]
  v=[(a&1<<b)//(1<<b)for a in g]
  q=[n*[0]for _ in range(n)]
  l=[0]*n
  m=[0]*n
  for i in range(n):
    for j in range(n):
      if(u[i]&v[j])|((s[i]^1)*u[i])|((t[j]^1)*v[j]):q[i][j]+=1;l[i]+=1;m[j]+=1
  for i in range(n):
    if s[i]*u[i]*(l[i]==0):
      for j in range(n):
        if(t[j]^1)*(n-m[j]>1):q[i][j]=u[i];m[j]+=1;break
  for j in range(n):
    if t[j]*v[j]*(m[j]==0):
      for i in range(n):
        if(s[i]^1)*(n-l[i]>1):q[i][j]=v[j];l[i]+=1;break
  h=q[0][:]
  w=[i[0]for i in q]
  for i in range(n):
    for j in range(n):
      if s[i]:w[i]|=q[i][j]
      else:w[i]&=q[i][j]
      if t[j]:h[j]|=q[i][j]
      else:h[j]&=q[i][j]
      ans[i][j]|=q[i][j]<<b
  if(v!=h)|(u!=w):print(-1);exit() 
for i in ans:print(*i)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
s=list(map(int,input().split()))
t=list(map(int,input().split()))
f=list(map(int,input().split()))
g=list(map(int,input().split()))
ans=[n*[0]for _ in range(n)]
for b in range(64):
  u=[(a&1<<b)//(1<<b)for a in f]
  v=[(a&1<<b)//(1<<b)for a in g]
  q=[[(u[i]&v[j])|((s[i]^1)*u[i])|((t[j]^1)*v[j])for j in range(n)]for i in range(n)]
  l=[sum(q[i])for i in range(n)]
  m=[sum(k[j]for k in q)for j in range(n)]
  for i in range(n):
    if s[i]*u[i]*(l[i]==0):
      for j in range(n):
        if(t[j]^1)*(n-m[j]>1):q[i][j]=u[i];m[j]+=1;break
  for j in range(n):
    if t[j]*v[j]*(m[j]==0):
      for i in range(n):
        if(s[i]^1)*(n-l[i]>1):q[i][j]=v[j];l[i]+=1;break
  h=q[0][:]
  w=[i[0]for i in q]
  for i in range(n):
    for j in range(n):
      if s[i]:w[i]|=q[i][j]
      else:w[i]&=q[i][j]
      if t[j]:h[j]|=q[i][j]
      else:h[j]&=q[i][j]
      ans[i][j]|=q[i][j]<<b
  if(v!=h)|(u!=w):print(-1);exit() 
for i in ans:print(*i)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
s=list(map(int,input().split()))
t=list(map(int,input().split()))
f=list(map(int,input().split()))
g=list(map(int,input().split()))
ans=[n*[0]for _ in range(n)]
for b in range(64):
  u=[(a&1<<b)//(1<<b)for a in f]
  v=[(a&1<<b)//(1<<b)for a in g]
  q=[[(u[i]&v[j])|((s[i]^1)*u[i])|((t[j]^1)*v[j])for j in range(n)]for i in range(n)]
  l=[sum(q[i])for i in range(n)]
  m=[sum(k[j]for k in q)for j in range(n)]
  for i in range(n):
    if s[i]*u[i]*(l[i]==0):
      for j in range(n):
        if(t[j]^1)*(n-m[j]>1):q[i][j]=u[i];m[j]+=1;break
  for j in range(n):
    if t[j]*v[j]*(m[j]==0):
      for i in range(n):
        if(s[i]^1)*(n-l[i]>1):q[i][j]=v[j];l[i]+=1;break
  h=q[0][:]
  w=[i[0]for i in q]
  for i in range(n):
    for j in range(n):
      if s[i]:w[i]|=q[i][j]
      else:w[i]&=q[i][j]
      if t[j]:h[j]|=q[i][j]
      else:h[j]&=q[i][j]
      ans[i][j]|=q[i][j]<<b
  if(v!=h)|(u!=w):print(-1);exit() 
for i in ans:print(*i)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
s=list(map(int,input().split()))
t=list(map(int,input().split()))
f=list(map(int,input().split()))
g=list(map(int,input().split()))
ans=[n*[0]for _ in range(n)]
for b in range(64):
  u=[(a&1<<b)//(1<<b)for a in f]
  v=[(a&1<<b)//(1<<b)for a in g]
  q=[[(u[i]&v[j])|((s[i]^1)*u[i])|((t[j]^1)*v[j])for j in range(n)]for i in range(n)]
  for i in range(n):
    if s[i]*u[i]*(sum(q[i])==0):
      for j in range(n):
        if(t[j]^1)*(n-sum(k[j]for k in q)>1):q[i][j]=u[i];break
  for j in range(n):
    if t[j]*v[j]*(sum(k[j]for k in q)==0):
      for i in range(n):
        if(s[i]^1)*(n-sum(q[i])>1):q[i][j]=v[j];break
  h=q[0][:]
  w=[i[0]for i in q]
  for i in range(n):
    for j in range(n):
      if s[i]:w[i]|=q[i][j]
      else:w[i]&=q[i][j]
      if t[j]:h[j]|=q[i][j]
      else:h[j]&=q[i][j]
      ans[i][j]|=q[i][j]<<b
  if(v!=h)|(u!=w):print(-1);exit() 
for i in ans:print(*i)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
s=list(map(int,input().split()))
t=list(map(int,input().split()))
f=list(map(int,input().split()))
g=list(map(int,input().split()))
ans=[n*[0]for _ in range(n)]
for b in range(64):
  u=[a&1<<b for a in f]
  v=[a&1<<b for a in g]
  q=[[(u[i]&v[j])|(0if s[i]else u[i])|(0if t[j]else v[j])for j in range(n)]for i in range(n)]
  for i in range(n):
    if s[i]*u[i]*(u[i]not in q[i]):
      for j in range(n):
        if(t[j]^1)*([k[j]for k in q].count(0)>1):q[i][j]=u[i];break
  for j in range(n):
    if t[j]*v[j]*(v[j]not in[k[j]for k in q]):
      for i in range(n):
        if(s[i]^1)*(q[i].count(0)>1):q[i][j]=v[j];break
  h=q[0][:]
  w=[i[0]for i in q]
  for i in range(n):
    for j in range(n):
      if s[i]:w[i]|=q[i][j]
      else:w[i]&=q[i][j]
      if t[j]:h[j]|=q[i][j]
      else:h[j]&=q[i][j]
      ans[i][j]|=q[i][j]
  if(v!=h)|(u!=w):print(-1);exit() 
for i in ans:print(*i)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
s=list(map(int,input().split()))
t=list(map(int,input().split()))
u=list(map(int,input().split()))
v=list(map(int,input().split()))
ans=[n*[0]for _ in range(n)]
def f(u,v):
  q=[[(u[i]&v[j])|(0if s[i]else u[i])|(0if t[j]else v[j])for j in range(n)]for i in range(n)]
  for i in range(n):
    if s[i]*u[i]*(u[i]not in q[i]):
      for j in range(n):
        if(t[j]^1)*([k[j]for k in q].count(0)>1):q[i][j]=u[i];break
  for j in range(n):
    if t[j]*v[j]*(v[j]not in[k[j]for k in q]):
      for i in range(n):
        if(s[i]^1)*(q[i].count(0)>1):q[i][j]=v[j];break
  h=q[0][:]
  w=[i[0]for i in q]
  for i in range(n):
    for j in range(n):
      if s[i]:w[i]|=q[i][j]
      else:w[i]&=q[i][j]
      if t[j]:h[j]|=q[i][j]
      else:h[j]&=q[i][j]
  if(v!=h)|(u!=w):print(-1);exit() 
  return q
for k in range(64):
  r=f([a&1<<k for a in u],[a&1<<k for a in v])
  ans=[[r[i][j]|ans[i][j]for j in range(n)]for i in range(n)]
for i in ans:print(*i)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = list(map(int,input().split()))
T = list(map(int,input().split()))
U = list(map(int,input().split()))
V = list(map(int,input().split()))

ans = [[0]*N for _ in range(N)]
possible = True
for n in range(64):
    n = 2**n
    n1 = 0
    n2 = 0
    S_ = [False]*N
    T_ = [False]*N
    i1 = -1
    j1 = -1
    i2 = -1
    j2 = -1
    for i in range(N):
        s = S[i]
        u = U[i]&n
        if u>0:
            u = 1
        for j in range(N):
            t = T[j]
            v = V[j]&n
            if v>0:
                v = 1
            if (s,u)==(0,1):
                if (t,v)!=(1,0):
                    ans[i][j] += n
                else:
                    possible = False
                    break
            elif (s,u)==(1,0):
                if (t,v)==(0,1):
                    possible = False
                    break
            elif (t,v)==(0,1) or (t,v)==(1,0):
                ans[i][j] += v*n
            elif (s,u)==(t,v):
                ans[i][j] += u*n
            elif (s,u)==(0,0):
                if n1==0:
                    i1 = i
                    j1 = j
                else:
                    if i==i1 or j==j1:
                        ans[i][j] += n
                n1 += 1
            elif (s,u)==(1,1):
                if n2==0:
                    i2 = i
                    j2 = j
                else:
                     if i==i2 or j==j2:
                         ans[i][j] += n
                n2 += 1
            if u*n==ans[i][j]&n:
                S_[i] = True
            if v*n==ans[i][j]&n:
                T_[j] = True
    if sum(S_)!=N:
        ans[i2][j2] += n
        m = n
        for i in range(N):
            m &= ans[i][j2]
        if m&n:
            possible = False
    if sum(T_)!=N:
        ans[i1][j1] += n
        m = n
        for j in range(N):
            m &= ans[i1][j]
        if m&n:
            possible = False
    if not possible:
        break

if possible:
    for i in range(N):
        print(*ans[i])
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = list(map(int,input().split()))
T = list(map(int,input().split()))
U = list(map(int,input().split()))
V = list(map(int,input().split()))

ans = [[0]*N for _ in range(N)]
possible = True
for n in range(64):
    n = 2**n
    n1 = 0
    n2 = 0
    S_ = [False]*N
    T_ = [False]*N
    i1 = -1
    j1 = -1
    i2 = -1
    j2 = -1
    for i in range(N):
        s = S[i]
        u = U[i]&n
        if u>0:
            u = 1
        for j in range(N):
            t = T[j]
            v = V[j]&n
            if v>0:
                v = 1
            if (s,u)==(0,1):
                if (t,v)!=(1,0):
                    ans[i][j] += n
                else:
                    possible = False
            elif (s,u)==(1,0):
                if (t,v)==(0,1):
                    possible = False
            elif (t,v)==(0,1) or (t,v)==(1,0):
                ans[i][j] += v*n
            elif (s,u)==(t,v):
                ans[i][j] += u*n
            elif (s,u)==(0,0):
                if n1==0:
                    i1 = i
                    j1 = j
                else:
                    if i==i1 or j==j1:
                        ans[i][j] += n
                n1 += 1
            elif (s,u)==(1,1):
                if n2==0:
                    i2 = i
                    j2 = j
                else:
                     if i==i2 or j==j2:
                         ans[i][j] += n
                n2 += 1
            if u*n==ans[i][j]&n:
                S_[i] = True
            if v*n==ans[i][j]&n:
                T_[j] = True
    if sum(S_)!=N:
        ans[i2][j2] += n
        m = n
        for i in range(N):
            m &= ans[i][j2]
        if m&n:
            possible = False
    if sum(T_)!=N:
        ans[i1][j1] += n
        m = n
        for j in range(N):
            m &= ans[i1][j]
        if m&n:
            possible = False

if possible:
    for i in range(N):
        print(*ans[i])
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
# simple-sat program by sahands
# https://github.com/sahands/simple-sat
# Licensed under MIT License


from collections import deque
import sys


class SATInstance(object):
    def parse_and_add_clause(self, line):
        clause = []
        for literal in line.split():
            negated = 1 if literal.startswith('~') else 0
            variable = literal[negated:]
            if variable not in self.variable_table:
                self.variable_table[variable] = len(self.variables)
                self.variables.append(variable)
            encoded_literal = self.variable_table[variable] << 1 | negated
            clause.append(encoded_literal)
        self.clauses.append(tuple(set(clause)))

    def __init__(self):
        self.variables = []
        self.variable_table = dict()
        self.clauses = []

    @classmethod
    def from_file(cls, file):
        instance = cls()
        for line in file:
            line = line.strip()
            if len(line) > 0 and not line.startswith('#'):
                instance.parse_and_add_clause(line)
        return instance

    @classmethod
    def from_stuv(cls, ss, ts, us, vs):
        instance = cls()
        n = len(ss)
        for i in range(n * n):
            instance.variable_table[i] = i
            instance.variables.append(i)
        for i, (s, u) in enumerate(zip(ss, us)):
            if s == 0 and u == 0:
                clause = []
                for j in range(n):
                    negated = 1
                    encoded_literal = (i * n + j) << 1 | negated
                    clause.append(encoded_literal)
                instance.clauses.append(tuple(set(clause)))
            if s == 0 and u == 1:
                for j in range(n):
                    clause = []
                    negated = 0
                    encoded_literal = (i * n + j) << 1 | negated
                    clause.append(encoded_literal)
                    instance.clauses.append(tuple(set(clause)))
            if s == 1 and u == 1:
                clause = []
                for j in range(n):
                    negated = 0
                    encoded_literal = (i * n + j) << 1 | negated
                    clause.append(encoded_literal)
                instance.clauses.append(tuple(set(clause)))
            if s == 1 and u == 0:
                for j in range(n):
                    clause = []
                    negated = 1
                    encoded_literal = (i * n + j) << 1 | negated
                    clause.append(encoded_literal)
                    instance.clauses.append(tuple(set(clause)))
        for i, (t, v) in enumerate(zip(ts, vs)):
            if t == 0 and v == 0:
                clause = []
                for j in range(n):
                    negated = 1
                    encoded_literal = (j * n + i) << 1 | negated
                    clause.append(encoded_literal)
                instance.clauses.append(tuple(set(clause)))
            if t == 0 and v == 1:
                for j in range(n):
                    clause = []
                    negated = 0
                    encoded_literal = (j * n + i) << 1 | negated
                    clause.append(encoded_literal)
                    instance.clauses.append(tuple(set(clause)))
            if t == 1 and v == 1:
                clause = []
                for j in range(n):
                    negated = 0
                    encoded_literal = (j * n + i) << 1 | negated
                    clause.append(encoded_literal)
                instance.clauses.append(tuple(set(clause)))
            if t == 1 and v == 0:
                for j in range(n):
                    clause = []
                    negated = 1
                    encoded_literal = (j * n + i) << 1 | negated
                    clause.append(encoded_literal)
                    instance.clauses.append(tuple(set(clause)))

        return instance

    def literal_to_string(self, literal):
        s = '~' if literal & 1 else ''
        return s + self.variables[literal >> 1]

    def clause_to_string(self, clause):
        return ' '.join(self.literal_to_string(l) for l in clause)

    def assignment_to_string(self, assignment, brief=False, starting_with=''):
        literals = []
        for a, v in ((a, v) for a, v in zip(assignment, self.variables)
                     if v.startswith(starting_with)):
            if a == 0 and not brief:
                literals.append('~' + v)
            elif a:
                literals.append(v)
        return ' '.join(literals)


def setup_watchlist(instance):
    watchlist = [deque() for __ in range(2 * len(instance.variables))]
    for clause in instance.clauses:
        # Make the clause watch its first literal
        watchlist[clause[0]].append(clause)
    return watchlist


def update_watchlist(watchlist,
                     false_literal,
                     assignment):
    """
    Updates the watch list after literal 'false_literal' was just assigned
    False, by making any clause watching false_literal watch something else.
    Returns False it is impossible to do so, meaning a clause is contradicted
    by the current assignment.
    """
    while watchlist[false_literal]:
        clause = watchlist[false_literal][0]
        found_alternative = False
        for alternative in clause:
            v = alternative >> 1
            a = alternative & 1
            if assignment[v] is None or assignment[v] == a ^ 1:
                found_alternative = True
                del watchlist[false_literal][0]
                watchlist[alternative].append(clause)
                break

        if not found_alternative:
            return False
    return True


def solve(instance, watchlist, assignment, d):
    """
    Iteratively solve SAT by assigning to variables d, d+1, ..., n-1. Assumes
    variables 0, ..., d-1 are assigned so far. A generator for all the
    satisfying assignments is returned.
    """

    # The state list wil keep track of what values for which variables
    # we have tried so far. A value of 0 means nothing has been tried yet,
    # a value of 1 means False has been tried but not True, 2 means True but
    # not False, and 3 means both have been tried.
    n = len(instance.variables)
    state = [0] * n

    while True:
        if d == n:
            yield assignment
            d -= 1
            continue
        # Let's try assigning a value to v. Here would be the place to insert
        # heuristics of which value to try first.
        tried_something = False
        for a in [0, 1]:
            if (state[d] >> a) & 1 == 0:
                tried_something = True
                # Set the bit indicating a has been tried for d
                state[d] |= 1 << a
                assignment[d] = a
                if not update_watchlist(watchlist,
                                        d << 1 | a,
                                        assignment):
                    assignment[d] = None
                else:
                    d += 1
                    break

        if not tried_something:
            if d == 0:
                # Can't backtrack further. No solutions.
                return
            else:
                # Backtrack
                state[d] = 0
                assignment[d] = None
                d -= 1


n = int(input())
ss = list(map(int, input().split()))
ts = list(map(int, input().split()))
us = list(map(int, input().split()))
vs = list(map(int, input().split()))


ans = [0] * (n * n)
for bit in range(64):
    instance = SATInstance.from_stuv(
        ss, ts,
        [(s >> bit) & 1 for s in us],
        [(s >> bit) & 1 for s in vs])
    n2 = len(instance.variables)
    watchlist = setup_watchlist(instance)
    assignment = [None] * n2
    solution = solve(instance, watchlist, assignment, 0)
    solutions = []
    for v in solution:
        solutions.append(v)
        break
    if len(solutions) == 0:
        print(-1)
        sys.exit()
    for i, v in enumerate(solutions[0]):
        ans[i] |= v << bit

for x in range(n):
    print(' '.join(map(str, ans[(x * n):((x + 1) * n)])))

Submission status: Accepted

Solution code:
def numba_compile(numba_config):
    import os, sys
    if sys.argv[-1] == "ONLINE_JUDGE":
        from numba import njit
        from numba.pycc import CC
        cc = CC("my_module")
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature)(func)
            cc.export(func.__name__, signature)(func)
        cc.compile()
        exit()
    elif os.name == "posix":
        exec(f"from my_module import {','.join(func.__name__ for func, _ in numba_config)}")
        for func, _ in numba_config:
            globals()[func.__name__] = vars()[func.__name__]
    else:
        from numba import njit
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature, cache=True)(func)
        print("compiled!", file=sys.stderr)


import numpy as np

def solve_1bit(N, rps, cps, rv, cv):
    res = np.full((N, N), 2, dtype=np.uint64)
    if N == 1:
        res[0, 0] = rv[0]
        return res
    r_all = np.array([False, False])
    for i, (ps, v) in enumerate(zip(rps, rv)):
        if ps ^ v == 1:
            res[i, :] = v
            r_all[v] = True
    c_all = np.array([False, False])
    for i, (ps, v) in enumerate(zip(cps, cv)):
        if ps ^ v == 1:
            res[:, i] = v
            c_all[v] = True
    if (r_all[0] and c_all[1]) or (r_all[1] and c_all[0]):
        return res
    if r_all[0] and c_all[0]:
        return np.where(res==2, np.uint64(1), res)
    if r_all[1] and c_all[1]:
        return np.where(res==2, np.uint64(0), res)
    if np.all(r_all):
        for y in range(N):
            for x in range(N):
                if res[y, x] == 2:
                    res[y, x] = rv[y]
        return res
    if np.all(c_all):
        for y in range(N):
            for x in range(N):
                if res[y, x] == 2:
                    res[y, x] = cv[x]
        return res
    if r_all[0]:
        if (cv==0).any():
            x = (cv==0).nonzero()[0][0]
            res[:, x] = 0
            return np.where(res==2, np.uint64(1), res)
        x = 0
        for y in range(N):
            v = rv[y]
            if v == 0 and res[y, 0] == 2:
                res[y, x] = 0
                x = (x+1) % N
        return np.where(res==2, np.uint64(1), res)
    if r_all[1]:
        if (cv==1).any():
            x = (cv==1).nonzero()[0][0]
            res[:, x] = 1
            return np.where(res==2, np.uint64(0), res)
        x = 0
        for y in range(N):
            v = rv[y]
            if v == 1 and res[y, 0] == 2:
                res[y, x] = 1
                x = (x+1) % N
        return np.where(res==2, np.uint64(0), res)
    if c_all[0]:
        if (rv==0).any():
            y = (rv==0).nonzero()[0][0]
            res[y, :] = 0
            return np.where(res==2, np.uint64(1), res)
        y = 0
        for x in range(N):
            v = cv[x]
            if v == 0 and res[0, x] == 2:
                res[y, x] = 0
                y = (y+1) % N
        return np.where(res==2, np.uint64(1), res)
    if c_all[1]:
        if (rv==1).any():
            y = (rv==1).nonzero()[0][0]
            res[y, :] = 1
            return np.where(res==2, np.uint64(0), res)
        y = 0
        for x in range(N):
            v = cv[x]
            if v == 1 and res[0, x] == 2:
                res[y, x] = 1
                y = (y+1) % N
        return np.where(res==2, np.uint64(0), res)
    for y in range(N):
        for x in range(N):
            res[y, x] = (y^x)&1
    return res

def solve(N, row_prod_sum, col_prod_sum, row_val, col_val):
    res = np.zeros((N, N), dtype=np.uint64)
    for i in range(64):
        rps = row_prod_sum
        cps = col_prod_sum
        rv = row_val>>i&1
        cv = col_val>>i&1
        r = solve_1bit(N, rps, cps, rv, cv)
        res |= r<<i
    #print(res)
    prod = res[0].copy()
    sum_ = res[0].copy()
    for y in range(1, N):
        prod &= res[y]
        sum_ |= res[y]
    #print(prod, sum_)
    if (prod[col_prod_sum==0] != col_val[col_prod_sum==0]).any():
        return 0, np.array([[-1]], dtype=np.int64)
    if (sum_[col_prod_sum==1] != col_val[col_prod_sum==1]).any():
        return 0, np.array([[-1]], dtype=np.int64)
    prod = res[:, 0].copy()
    sum_ = res[:, 0].copy()
    for x in range(1, N):
        prod &= res[:, x]
        sum_ |= res[:, x]
    #print(prod, sum_)
    if (prod[row_prod_sum==0] != row_val[row_prod_sum==0]).any():
        return 0, np.array([[-1]], dtype=np.int64)
    if (sum_[row_prod_sum==1] != row_val[row_prod_sum==1]).any():
        return 0, np.array([[-1]], dtype=np.int64)
    return 1, res


numba_compile([
    [solve_1bit, "u8[:,:](i8,u8[:],u8[:],u8[:],u8[:])"],
])


def main():
    N = int(input())
    row_prod_sum = np.array(input().split(), dtype=np.uint64)
    col_prod_sum = np.array(input().split(), dtype=np.uint64)
    row_val = np.array(input().split(), dtype=np.uint64)
    col_val = np.array(input().split(), dtype=np.uint64)
    t, ans = solve(N, row_prod_sum, col_prod_sum, row_val, col_val)
    if t:
        for lst in ans.tolist():
            print(" ".join(map(str, lst)))
    else:
        print(-1)

main()