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
input = sys.stdin.readline

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=[[[-1]*N for i in range(N)] for b in range(64)]

for b in range(64):
    for i in range(N):
        if S[i]==0 and (1<<b) & U[i]!=0:
            for j in range(N):
                if ANS[b][i][j]==0:
                    print(-1)
                    sys.exit()
                ANS[b][i][j]=1

        if S[i]==1 and (1<<b) & U[i]==0:
            for j in range(N):
                if ANS[b][i][j]==1:
                    print(-1)
                    sys.exit()
                ANS[b][i][j]=0


        if T[i]==0 and (1<<b) & V[i]!=0:
            for j in range(N):
                if ANS[b][j][i]==0:
                    print(-1)
                    sys.exit()
                ANS[b][j][i]=1

        if T[i]==1 and (1<<b) & V[i]==0:
            for j in range(N):
                if ANS[b][j][i]==1:
                    print(-1)
                    sys.exit()
                ANS[b][j][i]=0

for rep in range(2):
    for b in range(64):
        for i in range(N):
            if S[i]==0 and (1<<b)& U[i]==0:
                count_mi1=0
                okflag=0
                for j in range(N):
                    if ANS[b][i][j]==0:
                        okflag=1
                        break
                    if ANS[b][i][j]==-1:
                        count_mi1+=1
                    
                if okflag==0 and count_mi1==0:
                    print(-1)
                    sys.exit()

                if okflag==0 and count_mi1==1:
                    for j in range(N):
                        if ANS[b][i][j]==-1:
                            ANS[b][i][j]=0
                            break

            if S[i]==1 and (1<<b) & U[i]!=0:
                count_mi1=0
                okflag=0
                for j in range(N):
                    if ANS[b][i][j]==1:
                        okflag=1
                        break
                    if ANS[b][i][j]==-1:
                        count_mi1+=1
                    
                if okflag==0 and count_mi1==0:
                    print(-1)
                    sys.exit()

                if okflag==0 and count_mi1==1:
                    for j in range(N):
                        if ANS[b][i][j]==-1:
                            ANS[b][i][j]=1
                            break

            if T[i]==0 and (1<<b)& V[i]==0:
                count_mi1=0
                okflag=0
                for j in range(N):
                    if ANS[b][j][i]==0:
                        okflag=1
                        break
                    if ANS[b][j][i]==-1:
                        count_mi1+=1
                    
                if okflag==0 and count_mi1==0:
                    print(-1)
                    sys.exit()

                if okflag==0 and count_mi1==1:
                    for j in range(N):
                        if ANS[b][j][i]==-1:
                            ANS[b][j][i]=0
                            break

            if T[i]==1 and (1<<b) & V[i]!=0:
                count_mi1=0
                okflag=0
                for j in range(N):
                    if ANS[b][j][i]==1:
                        okflag=1
                        break
                    if ANS[b][j][i]==-1:
                        count_mi1+=1
                    
                if okflag==0 and count_mi1==0:
                    print(-1)
                    sys.exit()

                if okflag==0 and count_mi1==1:
                    for j in range(N):
                        if ANS[b][j][i]==-1:
                            ANS[b][j][i]=1
                            break

for b in range(64):
    for i in range(N):
        for j in range(N):
            if ANS[b][i][j]==-1:
                ANS[b][i][j]=(i+j)%2

for i in range(N):
    for j in range(N):
        S=[]
        for b in range(63,-1,-1):
            if ANS[b][i][j]==-1:
                S.append((i+j)%2)
            else:
                S.append(ANS[b][i][j])

        print(int("".join(map(str,S)),2),end=" ")
    print()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

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=[[[-1]*N for i in range(N)] for b in range(64)]

for b in range(64):
    for i in range(N):
        if S[i]==0 and (1<<b) & U[i]!=0:
            for j in range(N):
                if ANS[b][i][j]==0:
                    print(-1)
                    sys.exit()
                ANS[b][i][j]=1

        if S[i]==1 and (1<<b) & U[i]==0:
            for j in range(N):
                if ANS[b][i][j]==1:
                    print(-1)
                    sys.exit()
                ANS[b][i][j]=0


        if T[i]==0 and (1<<b) & V[i]!=0:
            for j in range(N):
                if ANS[b][j][i]==0:
                    print(-1)
                    sys.exit()
                ANS[b][j][i]=1

        if T[i]==1 and (1<<b) & V[i]==0:
            for j in range(N):
                if ANS[b][j][i]==1:
                    print(-1)
                    sys.exit()
                ANS[b][j][i]=0

for rep in range(2):
    for b in range(64):
        for i in range(N):
            if S[i]==0 and (1<<b)& U[i]==0:
                count_mi1=0
                okflag=0
                for j in range(N):
                    if ANS[b][i][j]==0:
                        okflag=1
                        break
                    if ANS[b][i][j]==-1:
                        count_mi1+=1
                    
                if okflag==0 and count_mi1==0:
                    print(-1)
                    sys.exit()

                if okflag==0 and count_mi1==1:
                    for j in range(N):
                        if ANS[b][i][j]==-1:
                            ANS[b][i][j]=0
                            break

            if S[i]==1 and (1<<b) & U[i]!=0:
                count_mi1=0
                okflag=0
                for j in range(N):
                    if ANS[b][i][j]==1:
                        okflag=1
                        break
                    if ANS[b][i][j]==-1:
                        count_mi1+=1
                    
                if okflag==0 and count_mi1==0:
                    print(-1)
                    sys.exit()

                if okflag==0 and count_mi1==1:
                    for j in range(N):
                        if ANS[b][i][j]==-1:
                            ANS[b][i][j]=1
                            break

            if T[i]==0 and (1<<b)& V[i]==0:
                count_mi1=0
                okflag=0
                for j in range(N):
                    if ANS[b][j][i]==0:
                        okflag=1
                        break
                    if ANS[b][j][i]==-1:
                        count_mi1+=1
                    
                if okflag==0 and count_mi1==0:
                    print(-1)
                    sys.exit()

                if okflag==0 and count_mi1==1:
                    for j in range(N):
                        if ANS[b][j][i]==-1:
                            ANS[b][j][i]=0
                            break

            if T[i]==1 and (1<<b) & V[i]!=0:
                count_mi1=0
                okflag=0
                for j in range(N):
                    if ANS[b][j][i]==1:
                        okflag=1
                        break
                    if ANS[b][j][i]==-1:
                        count_mi1+=1
                    
                if okflag==0 and count_mi1==0:
                    print(-1)
                    sys.exit()

                if okflag==0 and count_mi1==1:
                    for j in range(N):
                        if ANS[b][j][i]==-1:
                            ANS[b][j][i]=1
                            break

for b in range(64):
    for i in range(N):
        for j in range(N):
            if ANS[b][i][j]==-1:
                ANS[b][i][j]=(i+j)%2

for i in range(N):
    for j in range(N):
        S=""
        for b in range(63,-1,-1):
            S+=str(ANS[b][i][j])
        print(int(S,2),end=" ")
    print()

Submission status: Time Limit Exceeded

Solution code:
def main():
  import sys
  input = sys.stdin.readline
  
  n = int(input())
  s = [[],[]]
  for i in range(2):
    s[i] = tuple(map(int,input().split()))
  u = [[],[]]
  for i in range(2):
    u[i] = tuple(map(int,input().split()))
  
  val = [[0 for _ in range(n)] for _ in range(2)]
  d = [[0 for _ in range(n)] for _ in range(n)]
  ans = [[0 for _ in range(n)] for _ in range(n)]
  
  def flip():
    for i in range(n):
      for j in range(i,n):
        d[i][j],d[j][i] = d[j][i],d[i][j]
    
  def solve():
    for i in range(n):
      for j in range(n):
        d[i][j] = -1
    for k in range(2):
      for i in range(n):
        if s[k][i] != val[k][i]:
          for j in range(n):
            if d[i][j] != -1 and d[i][j] != val[k][i]:
              return False
            d[i][j] = val[k][i]
      flip()
    #print(d)
    for l in range(2):
      for k in range(2):
        for i in range(n):
          if s[k][i] == val[k][i]:
            p = []
            ok = False
            for j in range(n):
              if d[i][j] == val[k][i]:
                ok = True
              if d[i][j] == -1:
                p.append(j)
            if ok:
              continue
            if len(p) == 0:
              return False
            elif len(p) == 1:
              d[i][p[0]] = val[k][i]
        flip()
    #print(d)
    start = 0
    for i in range(n):
      num = start
      flag = False
      for j in range(n):
        if d[i][j] == -1:
          flag = True
          d[i][j] = num
          num ^= 1
      if flag:
        start ^= 1
    return True
  
  for b in range(64):
    for i in range(2):
      for j in range(n):
        val[i][j] = (u[i][j]>>b)&1
    if solve():
      for i in range(n):
        for j in range(n):
          ans[i][j] |= d[i][j]<<b
    else:
      print(-1)
      exit()
  
  for i in range(n):
    print(*ans[i])

main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  import sys
  input = sys.stdin.readline
  
  n = int(input())
  s = [[],[]]
  for i in range(2):
    s[i] = tuple(map(int,input().split()))
  u = [[],[]]
  for i in range(2):
    u[i] = tuple(map(int,input().split()))
  
  val = [[0 for _ in range(n)] for _ in range(2)]
  d = [[0 for _ in range(n)] for _ in range(n)]
  ans = [[0 for _ in range(n)] for _ in range(n)]
  
  def flip():
    for i in range(n):
      for j in range(i,n):
        d[i][j],d[j][i] = d[j][i],d[i][j]
    
  def solve():
    for i in range(n):
      for j in range(n):
        d[i][j] = -1
    for i in range(n):
      if s[0][i] != val[0][i]:
        for j in range(n):
          if d[i][j] != -1 and d[i][j] != val[0][i]:
            return False
          d[i][j] = val[0][i]
    for i in range(n):
      if s[1][i] != val[1][i]:
        for j in range(n):
          if d[j][i] != -1 and d[j][i] != val[1][i]:
            return False
          d[j][i] = val[1][i]
    #for k in range(2):
    #  for i in range(n):
    #    if s[k][i] != val[k][i]:
    #      for j in range(n):
    #        if d[i][j] != -1 and d[i][j] != val[k][i]:
    #          return False
    #        d[i][j] = val[k][i]
    #  flip()
    #print(d)
    
    for l in range(2):
      for i in range(n):
        if s[0][i] == val[0][i]:
          p = []
          ok = False
          for j in range(n):
            if d[i][j] == val[0][i]:
              ok = True
              break
            if d[i][j] == -1:
              p.append(j)
          if ok:
            continue
          if len(p) == 0:
            return False
          elif len(p) == 1:
            d[i][p[0]] = val[0][i]
      for i in range(n):
        if s[1][i] == val[1][i]:
          p = []
          ok = False
          for j in range(n):
            if d[j][i] == val[1][i]:
              ok = True
              break
            if d[j][i] == -1:
              p.append(j)
          if ok:
            continue
          if len(p) == 0:
            return False
          elif len(p) == 1:
            d[p[0]][i] = val[1][i]
      #for k in range(2):
      #  for i in range(n):
      #    if s[k][i] == val[k][i]:
      #      p = []
      #      ok = False
      #      for j in range(n):
      #        if d[i][j] == val[k][i]:
      #          ok = True
      #         break
      #        if d[i][j] == -1:
      #          p.append(j)
      #      if ok:
      #        continue
      #      if len(p) == 0:
      #        return False
      #      elif len(p) == 1:
      #        d[i][p[0]] = val[k][i]
      #  flip()
    
    #print(d)
    start = 0
    for i in range(n):
      num = start
      flag = False
      for j in range(n):
        if d[i][j] == -1:
          flag = True
          d[i][j] = num
          num ^= 1
      if flag:
        start ^= 1
    return True
  
  for b in range(64):
    for i in range(2):
      for j in range(n):
        val[i][j] = (u[i][j]>>b)&1
    if solve():
      for i in range(n):
        for j in range(n):
          ans[i][j] |= d[i][j]<<b
    else:
      print(-1)
      exit()
  
  for i in range(n):
    print(*ans[i])

main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  import sys
  input = sys.stdin.readline
  
  n = int(input())
  s = [[],[]]
  for i in range(2):
    s[i] = tuple(map(int,input().split()))
  u = [[],[]]
  for i in range(2):
    u[i] = tuple(map(int,input().split()))
  
  val = [[0 for _ in range(n)] for _ in range(2)]
  d = [[0 for _ in range(n)] for _ in range(n)]
  ans = [[0 for _ in range(n)] for _ in range(n)]
  
  def flip():
    for i in range(n):
      for j in range(i,n):
        d[i][j],d[j][i] = d[j][i],d[i][j]
    
  def solve():
    for i in range(n):
      for j in range(n):
        d[i][j] = -1
    for k in range(2):
      for i in range(n):
        if s[k][i] != val[k][i]:
          for j in range(n):
            if d[i][j] != -1 and d[i][j] != val[k][i]:
              return False
            d[i][j] = val[k][i]
      flip()
    #print(d)
    for l in range(2):
      for k in range(2):
        for i in range(n):
          if s[k][i] == val[k][i]:
            p = []
            ok = False
            for j in range(n):
              if d[i][j] == val[k][i]:
                ok = True
                break
              if d[i][j] == -1:
                p.append(j)
            if ok:
              continue
            if len(p) == 0:
              return False
            elif len(p) == 1:
              d[i][p[0]] = val[k][i]
        flip()
    #print(d)
    start = 0
    for i in range(n):
      num = start
      flag = False
      for j in range(n):
        if d[i][j] == -1:
          flag = True
          d[i][j] = num
          num ^= 1
      if flag:
        start ^= 1
    return True
  
  for b in range(64):
    for i in range(2):
      for j in range(n):
        val[i][j] = (u[i][j]>>b)&1
    if solve():
      for i in range(n):
        for j in range(n):
          ans[i][j] |= d[i][j]<<b
    else:
      print(-1)
      exit()
  
  for i in range(n):
    print(*ans[i])

main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = [[],[]]
for i in range(2):
  s[i] = list(map(int,input().split()))
u = [[],[]]
for i in range(2):
  u[i] = list(map(int,input().split()))

val = [[0 for _ in range(n)] for _ in range(2)]
d = [[0 for _ in range(n)] for _ in range(n)]
ans = [[0 for _ in range(n)] for _ in range(n)]

def flip():
  for i in range(n):
    for j in range(i,n):
      d[i][j],d[j][i] = d[j][i],d[i][j]
  
def solve():
  for i in range(n):
    for j in range(n):
      d[i][j] = -1
  for k in range(2):
    for i in range(n):
      if s[k][i] != val[k][i]:
        for j in range(n):
          if d[i][j] != -1 and d[i][j] != val[k][i]:
            return False
          d[i][j] = val[k][i]
    flip()
  #print(d)
  for l in range(2):
    for k in range(2):
      for i in range(n):
        if s[k][i] == val[k][i]:
          p = []
          ok = False
          for j in range(n):
            if d[i][j] == val[k][i]:
              ok = True
            if d[i][j] == -1:
              p.append(j)
          if ok:
            continue
          if len(p) == 0:
            return False
          elif len(p) == 1:
            d[i][p[0]] = val[k][i]
      flip()
  #print(d)
  start = 0
  for i in range(n):
    num = start
    flag = False
    for j in range(n):
      if d[i][j] == -1:
        flag = True
        d[i][j] = num
        num ^= 1
    if flag:
      start ^= 1
  return True

for b in range(64):
  for i in range(2):
    for j in range(n):
      val[i][j] = (u[i][j]>>b)&1
  if solve():
    for i in range(n):
      for j in range(n):
        ans[i][j] |= d[i][j]<<b
  else:
    print(-1)
    exit()

for i in range(n):
  print(*ans[i])

Submission status: Time Limit Exceeded

Solution code:
import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
def resolve():
    N = ir()
    S = lr()
    T = lr()
    U = lr()
    V = lr()
    s = [[S[i], T[i]] for i in range(N)]
    d = [[-1]*N for i in range(N)]
    def flip():
        for i in range(N):
            for j in range(i):
                d[i][j], d[j][i] = d[j][i], d[i][j]
    a = [[0]*N for i in range(N)]
    for k in range(64):
        val = [[bool(U[i]&(1<<k)), bool(V[i]&(1<<k))] for i in range(N)]
        d = [[-1]*N for i in range(N)]
        for b in range(2):
            for i in range(N):
                x = val[i][b]
                if s[i][b] != x:
                    for j in range(N):
                        if d[i][j] != x and d[i][j] != -1:
                            print(-1)
                            return
                        d[i][j] = x
            flip()
        for _ in range(2):
            for b in range(2):
                for i in range(N):
                    x = val[i][b]
                    if s[i][b] == x:
                        p = []
                        ok = False
                        for j in range(N):
                            if d[i][j] == -1:
                                p.append(j)
                            if d[i][j] == x:
                                ok = True
                        if ok:
                            continue
                        if len(p) == 0:
                            print(-1)
                            return
                        if len(p) == 1:
                            d[i][p[0]] = x
                flip()
        ni = []
        nj = []
        for i in range(N):
            filled = True
            for j in range(N):
                if d[i][j] == -1:
                    filled = False
            if not filled:
                ni.append(i)
        for j in range(N):
            filled = True
            for i in range(N):
                if d[i][j] == -1:
                    filled = False
            if not filled:
                nj.append(j)
        for i in ni:
            for j in nj:
                d[i][j] = (i+j)%2
        for i in range(N):
            for j in range(N):
                a[i][j] |= d[i][j]<<k
    for i in range(N):
        print(*a[i], sep=' ')
resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
def resolve():
    N = ir()
    S = lr()
    T = lr()
    U = lr()
    V = lr()
    s = [[S[i], T[i]] for i in range(N)]
    def flip(td):
        for i in range(N):
            for j in range(i):
                td[i][j], td[j][i] = td[j][i], td[i][j]
        return td
    a = [[0]*N for i in range(N)]
    for k in range(64):
        val = [[bool(U[i]&(1<<k)), bool(V[i]&(1<<k))] for i in range(N)]
        d = [[-1]*N for i in range(N)]
        for b in range(2):
            for i in range(N):
                x = val[i][b]
                if s[i][b] != x:
                    for j in range(N):
                        if d[i][j] != x and d[i][j] != -1:
                            print(-1)
                            return
                        d[i][j] = x
            d = flip(d)
        for _ in range(2):
            for b in range(2):
                for i in range(N):
                    x = val[i][b]
                    if s[i][b] == x:
                        p = []
                        ok = False
                        for j in range(N):
                            if d[i][j] == -1:
                                p.append(j)
                            if d[i][j] == x:
                                ok = True
                        if ok:
                            continue
                        if len(p) == 0:
                            print(-1)
                            return
                        if len(p) == 1:
                            d[i][p[0]] = x
                d = flip(d)
        ni = []
        nj = []
        for i in range(N):
            filled = True
            for j in range(N):
                if d[i][j] == -1:
                    filled = False
            if not filled:
                ni.append(i)
        for j in range(N):
            filled = True
            for i in range(N):
                if d[i][j] == -1:
                    filled = False
            if not filled:
                nj.append(j)
        for i in ni:
            for j in nj:
                d[i][j] = (i+j)%2
        for i in range(N):
            for j in range(N):
                a[i][j] |= d[i][j]<<k
    for i in range(N):
        print(*a[i], sep=' ')
resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
def resolve():
    N = ir()
    S = lr()
    T = lr()
    U = lr()
    V = lr()
    s = [[S[i], T[i]] for i in range(N)]
    def flip(td):
        for i in range(N):
            for j in range(i):
                td[i][j], td[j][i] = td[j][i], td[i][j]
        return td
    a = [[0]*N for i in range(N)]
    for k in range(64):
        val = [[(U[i]>>k)&1, (V[i]>>k)&1] for i in range(N)]
        d = [[-1]*N for i in range(N)]
        for b in range(2):
            for i in range(N):
                x = val[i][b]
                if s[i][b] != x:
                    for j in range(N):
                        if d[i][j] != x and d[i][j] != -1:
                            print(-1)
                            return
                        d[i][j] = x
            d = flip(d)
        for _ in range(2):
            for b in range(2):
                for i in range(N):
                    x = val[i][b]
                    if s[i][b] == x:
                        p = []
                        ok = False
                        for j in range(N):
                            if d[i][j] == -1:
                                p.append(j)
                            if d[i][j] == x:
                                ok = True
                        if ok:
                            continue
                        if len(p) == 0:
                            print(-1)
                            return
                        if len(p) == 1:
                            d[i][p[0]] = x
                d = flip(d)
        ni = []
        nj = []
        for i in range(N):
            filled = True
            for j in range(N):
                if d[i][j] == -1:
                    filled = False
            if not filled:
                ni.append(i)
        for j in range(N):
            filled = True
            for i in range(N):
                if d[i][j] == -1:
                    filled = False
            if not filled:
                nj.append(j)
        for i in ni:
            for j in nj:
                d[i][j] = (i+j)%2
        for i in range(N):
            for j in range(N):
                a[i][j] |= d[i][j]<<k
    for i in range(N):
        print(*a[i], sep=' ')
resolve()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from functools import reduce
from operator import or_, and_


def solve(N: int, S: "List[int]", T: "List[int]", U: "List[int]", V: "List[int]"):
    AND, ORE = 0, 1
    ans = [[0 for j in range(N)] for i in range(N)]
    can = True
    for b in range(64):
        parityU = [(x >> b) & 1 for x in U]
        parityV = [(x >> b) & 1 for x in V]
        for i in range(N):
            for j in range(N):
                if parityU[i] == parityV[j]:
                    ans[i][j] |= parityU[i] << b
                if S[i] == AND and parityU[i] == 1 or T[j] == AND and parityV[j] == 1:
                    ans[i][j] |= 1 << b
                can &= not (S[i] == ORE and parityU[i] == 0 and T[j] == AND and parityV[j] == 1)
                can &= not (S[i] == AND and parityU[i] == 1 and T[j] == ORE and parityV[j] == 0)
        rows_free0 = [i for i in range(N) if parityU[i] == 0 or S[i] == ORE and any(x == 1 for x in parityV)]
        rows_free1 = [i for i in range(N) if parityU[i] == 1 or S[i] == AND and any(x == 0 for x in parityV)]
        cols_free0 = [j for j in range(N) if parityV[j] == 0 or T[j] == ORE and any(x == 1 for x in parityU)]
        cols_free1 = [j for j in range(N) if parityV[j] == 1 or T[j] == AND and any(x == 0 for x in parityU)]
        rows_need0 = [i for i in range(N) if S[i] == AND and parityU[i] == 0] if not cols_free0 else []
        rows_need1 = [i for i in range(N) if S[i] == ORE and parityU[i] == 1]
        cols_need0 = [j for j in range(N) if T[j] == AND and parityV[j] == 0] if not rows_free0 else []
        cols_need1 = [j for j in range(N) if T[j] == ORE and parityV[j] == 1]
        if rows_free1:
            for col in cols_need1:
                ans[rows_free1[0]][col] |= 1 << b
            cols_need1 = []
        if cols_free1:
            for row in rows_need1:
                ans[row][cols_free1[0]] |= 1 << b
            rows_need1 = []
        can &= not rows_need0 or any(T[j] == ORE for j in range(N))
        can &= not rows_need1 or any(T[j] == AND for j in range(N))
        can &= not cols_need0 or any(S[i] == ORE for i in range(N))
        can &= not cols_need1 or any(S[i] == AND for i in range(N))
        can &= not any(len(a) == 1 and len(b) > 0 or len(b) == 1 and len(a) > 0 for a, b in ((rows_need0, cols_need1), (rows_need1, cols_need0)))
        for rows, cols in ((rows_need0, cols_need1), (cols_need0, rows_need1)):
            for ii, i in enumerate(rows):
                for jj, j in enumerate(cols):
                    ans[i][j] |= ((ii & 1) ^ (jj & 1)) << b
    if can:
        for row in ans:
            print(*row)
        assert all(reduce(or_ if S[i] else and_, (ans[i][j] for j in range(N))) == U[i] for i in range(N))
        assert all(reduce(or_ if T[j] else and_, (ans[i][j] for i in range(N))) == V[j] for j in range(N))
    else:
        print(-1)


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    N = int(sys.stdin.readline())  # type: int
    S = [int(x) for x in sys.stdin.readline().split()]  # type: "List[int]"
    T = [int(x) for x in sys.stdin.readline().split()]  # type: "List[int]"
    U = [int(x) for x in sys.stdin.readline().split()]  # type: "List[int]"
    V = [int(x) for x in sys.stdin.readline().split()]  # type: "List[int]"
    solve(N, S, T, U, V)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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