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: Wrong Answer

Solution code:
N=int(input())
S=[int(i) for i in input().split()]
T=[int(i) for i in input().split()]
U=[int(i) for i in input().split()]
V=[int(i) for i in input().split()]
a=[[0 for j in range(N)] for i in range(N)]
b=[[[0,0] for k in range(64)] for i in range(N)]
c=[[[0,0] for k in range(64)] for j in range(N)]
for i in range(N):
    for j in range(N):
        #a[i][j]
        #i行目　j列目U
        for k in range(64):
            tmp=((1<<k)&U[i])>>k
            #tmp in range(2)
            if S[i]!=tmp:
                a[i][j]^=tmp<<k
                b[i][k][tmp]=1
                c[j][k][tmp]=1
                continue
            else:
                kouho1=tmp
            tmp=((1<<k)&V[j])>>k
            #tmp in range(2)
            if T[j]!=tmp:
                a[i][j]^=tmp<<k
                b[i][k][tmp]=1
                c[j][k][tmp]=1
                continue
            else:
                kouho2=tmp
            #ここに来るときは両方(0,0)か(1,1)になる
            #kouhox in range(2)
            if kouho1!=kouho2:
                if b[i][k][kouho1]==0 and c[j][k][kouho2]==0:
                    a[i][j]^=tmp<<k
                    b[i][k][tmp]=1
                    c[j][k][tmp]=1
                elif b[i][k][kouho1]==0:
                    a[i][j]^=kouho1<<k
                    b[i][k][kouho1]=1
                    c[j][k][kouho1]=1
                else:
                    a[i][j]^=kouho2<<k
                    b[i][k][kouho2]=1
                    c[j][k][kouho2]=1
            else:
                a[i][j]^=kouho1<<k
                b[i][k][kouho1]=1
                c[j][k][kouho1]=1
X=[0 for i in range(N)]
Y=[0 for j in range(N)]
for i in range(N):
    if S[i]==0:
        X[i]=(1<<64)-1
    if T[i]==0:
        Y[i]=(1<<64)-1
for i in range(N):
    for j in range(N):
        if S[i]==0:
            X[i]&=a[i][j]
        else:
            X[i]|=a[i][j]
        if T[j]==0:
            Y[j]&=a[i][j]
        else:
            Y[j]|=a[i][j]
flag=1
for i in range(N):
    if U[i]!=X[i]:
        flag=0
        break
    if V[i]!=Y[i]:
        flag=0
        break
#print(S,T)
#print(U,V)
#print(X,Y)
if flag==0:
    print(-1)
    exit()
for line in a:
    print(*line)

Submission status: Wrong Answer

Solution code:
#author: raghav_0901
from math import *

mod = 998244353


def CountOccurrences(string, substring):
    if(len(substring) > len(string)):
        return 0
    count = 0
    start = 0
    while start < len(string):

        pos = string.find(substring, start)

        if pos != -1:
            start = pos + 1

            # Increment the count
            count += 1
        else:
            # If no further substring is present
            break
    # return the value of count
    return count


def _in():
    return [int(x) for x in input().split(' ')]


def main():
    n = int(input())
    s, t, u, v = _in(), _in(), _in(), _in()
    ans = []
    for i in range(n):
        if((s[i] + t[i]) % 2 == 0):
            if(u[i] == v[i]):
                ans.append([u[i]] * n)
            else:
                print(-1)
                return 0
        elif(s[i] == 0 and t[i] == 1):
            if((u[i] & v[i]) == u[i]):
                if(n == 1):
                    if(u[i] == v[i]):
                        ans.append([u[i]])
                    else:
                        print(-1)
                        return 0
                else:
                    ans.append([u[i]] * (n - 1) + [v[i]])
            else:
                print(-1)
                return 0
        else:
            if((u[i] & v[i]) == v[i]):
                if(n == 1):
                    if(u[i] == v[i]):
                        ans.append([u[i]])
                    else:
                        print(-1)
                        return 0
                else:
                    ans.append([u[i]] * (n - 1) + [v[i]])
            else:
                print(-1)
                return 0
    for i in ans:
        for j in i:
            print(j, end=" ")
        print()


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n=int(input())
s_li=list(map(int,input().split()))
t_li=list(map(int,input().split()))
u_li=list(map(int,input().split()))
v_li=list(map(int,input().split()))

kano=True

ans=[[0]*n for i in range(n)]

hidari=[0]*n

migi=[0]*n

for i in range(n):
    if(n==1):
        kano=False
        break
    s=s_li[i]
    t=t_li[i]
    u=u_li[i]
    v=v_li[i]
    if(s==t):
        if(u==v):
            hidari[i]=u
            migi[i]=u
        else:
            kano=False
            break
    else:
        wa=0
        seki=0
        if(s==1):
            wa=u
            seki=v
        else:
            wa=v
            seki=u
        if((wa&seki)==seki):
            hidari[i]=wa
            migi[i]=seki
        else:
            kano=False
            break

#print(hidari)
#print(migi)

for i in range(n):
    ans[i][0]=hidari[i]
    for j in range(1,n):
        ans[i][j]=migi[i]

if(kano):
    for i in range(n):
        #print(ans[i])
        moji=""
        for j in range(n):
            moji+=str(ans[i][j])+" "
        print(moji)
else:
    if(n!=1):
        print(-1)
    else:
        if(u_li[0]==v_li[0]):
            print(u_li[0])
        else:
            print(-1)

Submission status: Wrong Answer

Solution code:
def bitwise_not(x):
    return x ^ 0xffffffffffffffff

def main():
    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()))

    logand = []
    logor = []
    ans = []
    for i in range(n):
        logand.append([])
        logor.append([])
        ans.append([])
        for j in range(n):
            logand[i].append(None)
            logor[i].append(None)
            ans[i].append(None)

    for i in range(n):
        for j in range(n):
            if s[i] == 0:
                logand[i][j] = u[i]
            else:
                logor[i][j] = u[i]

    for j in range(n):
        for i in range(n):
            if t[j] == 0:
                if logand[i][j] is None:
                    logand[i][j] = v[j]
                else:
                    logand[i][j] = logand[i][j] | v[j]
            else:
                if logor[i][j] is None:
                    logor[i][j] = v[j]
                else:
                    logor[i][j] = logor[i][j] & v[j]

    for i in range(n):
        for j in range(n):
            if logand[i][j] is None:
                ans[i][j] = logor[i][j]
            elif logor[i][j] is None:
                ans[i][j] = logand[i][j]
            elif logand[i][j] == logor[i][j]:
                ans[i][j] = logor[i][j]
            elif logand[i][j] & bitwise_not(logor[i][j]) > 0:
                print(-1)
                return
            else:
                ans[i][j] = logand[i][j] & logor[i][j]

    for i in range(n):
        if s[i] == 0:
            a = (1 << 64) - 1
            for j in range(n):
                a = a & ans[i][j]
            if a != u[i]:
                print(-1)
                return
        else:
            o = 0
            for j in range(n):
                o = o | ans[i][j]
            if o != u[i]:
                print(-1)
                return

    for j in range(n):
        if t[j] == 0:
            a = (1 << 64) - 1
            for i in range(n):
                a = a & ans[i][j]
            if a != v[j]:
                print(-1)
                return
        else:
            o = 0
            for i in range(n):
                o = o | ans[i][j]
            if o != v[j]:
                print(-1)
                return

    for i in range(n):
        print(' '.join(str(x) for x in ans[i]))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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 i in range(N):
    if S[i]==0:
        for j in range(N):
            ANS[i][j]=U[i]

for i in range(N):
    if T[i]==0:
        for j in range(N):
            if ANS[j][i]==-1:
                ANS[j][i]=V[i]
            else:
                ANS[j][i]=T[i]|ANS[j][i]

for i in range(N):
    if S[i]==1:
        for j in range(N):
            if ANS[i][j]==-1:
                ANS[i][j]=U[i]

for i in range(N):
    if T[i]==1:
        for j in range(N):
            if ANS[j][i]==-1:
                ANS[j][i]=V[i]

for i in range(N):
    print(*ANS[i])

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
print(-1)

Submission status: Wrong Answer

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

def check(k):
    res = [[None]*N for _ in range(N)]
    H = []
    W = []
    for i in range(N):
        if S[i] == 0 and U[i] & (1<<k):
            res[i] = [1]*N
        elif S[i] == 1 and not U[i] & (1<<k):
            res[i] = [0]*N
        else:
            H.append(i)
    for j in range(N):
        if T[j] == 0 and V[j] & (1<<k):
            for i in range(N):
                if res[i][j] == 0:
                    return -1
                res[i][j] = 1
        elif T[j] == 1 and not V[j] & (1<<k):
            for i in range(N):
                if res[i][j] == 1:
                    return -1
                res[i][j] = 0
        else:
            W.append(j)

    for st in range(2):
        for i in range(len(H)):
            for j in range(len(W)):
                h, w = H[i], W[j]
                res[h][w] = (i+j+st)%2
        flag = True
        for i in range(N):
            if S[i] == 0:
                cnt = 1
                for j in range(N):
                    cnt &= res[i][j]
                if  (cnt ^ (U[i]>>k)) & 1:
                    flag = False
                    break
            else:
                cnt = 0
                for j in range(N):
                    cnt |= res[i][j]
                if  (cnt ^ (U[i]>>k)) & 1:
                    flag = False
                    break
        else:
            for j in range(N):
                if T[j] == 0:
                    cnt = 1
                    for i in range(N):
                        cnt &= res[i][j]
                    if  (cnt ^ (V[j]>>k)) & 1:
                        flag = False
                        break
                else:
                    cnt = 0
                    for i in range(N):
                        cnt |= res[i][j]
                    if  (cnt ^ (V[j]>>k)) & 1:
                        flag = False
                        break
        if flag:
            return res
    return -1
    

N = int(readline())
S = list(map(int, readline().split()))
T = list(map(int, readline().split()))
U = list(map(int, readline().split()))
V = list(map(int, readline().split()))

ans = [[0]*N for _ in range(N)]

for k in range(64):
    res = check(k)
    if res == -1:
        ans = -1
        break
    for i in range(N):
        for j in range(N):
            ans[i][j] |= res[i][j]<<k
if ans == -1:
    print(-1)
else:
    print('\n'.join([' '.join(map(str, a)) for a in ans]))

Submission status: Time Limit Exceeded

Solution code:
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 = [False, False]
    for i, (ps, v) in enumerate(zip(rps, rv)):
        if ps ^ v == 1:
            res[i, :] = v
            r_all[v] = True
    c_all = [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, 1, res)
    if r_all[1] and c_all[1]:
        return np.where(res==2, 0, res)
    if 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 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, 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, 1, res)
    if r_all[1]:
        if (cv==1).any():
            x = (cv==1).nonzero()[0][0]
            res[:, x] = 1
            return np.where(res==2, 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, 0, res)
    if c_all[0]:
        if (rv==0).any():
            y = (rv==0).nonzero()[0][0]
            res[y, :] = 0
            return np.where(res==2, 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, 1, res)
    if c_all[1]:
        if (rv==1).any():
            y = (rv==1).nonzero()[0][0]
            res[y, :] = 1
            return np.where(res==2, 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, 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



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)

Submission status: Time Limit Exceeded

Solution code:
def main(N,S,T,U,V):
    ans = [[0]*N for _ in range(N)]
    possible = True
    for n in range(64):
        n = 2**n
        n1 = 0
        n2 = 0
        S_ = [False]*N
        s_ = 0
        T_ = [False]*N
        t_ = 0
        i1 = -1
        j1 = -1
        i2 = -1
        j2 = -1
        for i in range(N):
            ansi = ans[i]
            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):
                        ansi[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):
                    ansi[j] += v*n
                elif (s,u)==(t,v):
                    ansi[j] += u*n
                elif (s,u)==(0,0):
                    if n1==0:
                        i1 = i
                        j1 = j
                    else:
                        if i==i1 or j==j1:
                            ansi[j] += n
                    n1 += 1
                elif (s,u)==(1,1):
                    if n2==0:
                        i2 = i
                        j2 = j
                    else:
                         if i==i2 or j==j2:
                             ansi[j] += n
                    n2 += 1
                if u*n==ansi[j]&n:
                    if not S_[i]:
                        s_ += 1
                    S_[i] = True
                if v*n==ansi[j]&n:
                    if not T_[j]:
                        t_ += 1
                    T_[j] = True
        if s_!=N:
            ans[i2][j2] += n
            m = n
            for i in range(N):
                m &= ans[i][j2]
            if m&n:
                possible = False
        if 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)

if __name__ == '__main__':
    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()))
    main(N,S,T,U,V)

Submission status: Time Limit Exceeded

Solution code:
def main(N,S,T,U,V):
    ans = [[0]*N for _ in range(N)]
    possible = True
    for n in range(64):
        n = 2**n
        n1 = 0
        n2 = 0
        S_ = [False]*N
        s_ = 0
        T_ = [False]*N
        t_ = 0
        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:
                    if not S_[i]:
                        s_ += 1
                    S_[i] = True
                if v*n==ans[i][j]&n:
                    if not T_[j]:
                        t_ += 1
                    T_[j] = True
        if s_!=N:
            ans[i2][j2] += n
            m = n
            for i in range(N):
                m &= ans[i][j2]
            if m&n:
                possible = False
        if 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)

if __name__ == '__main__':
    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()))
    main(N,S,T,U,V)

Submission status: Time Limit Exceeded

Solution code:
def main(N,S,T,U,V):
    ans = [[0]*N for _ in range(N)]
    possible = True
    l = [i for i in range(N)]
    for n in range(64):
        n = 2**n
        n1 = 0
        n2 = 0
        S_ = [False]*N
        s_ = 0
        T_ = [False]*N
        t_ = 0
        i1 = -1
        j1 = -1
        i2 = -1
        j2 = -1
        for i in l:
            s = S[i]
            u = U[i]&n
            if u>0:
                u = 1
            for j in l:
                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:
                    if not S_[i]:
                        s_ += 1
                    S_[i] = True
                if v*n==ans[i][j]&n:
                    if not T_[j]:
                        t_ += 1
                    T_[j] = True
        if s_!=N:
            ans[i2][j2] += n
            m = n
            for i in range(N):
                m &= ans[i][j2]
            if m&n:
                possible = False
        if 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)

if __name__ == '__main__':
    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()))
    main(N,S,T,U,V)

Submission status: Time Limit Exceeded

Solution code:
def main(N,S,T,U,V):
    ans = [[0]*N for _ in range(N)]
    possible = True
    l = [i for i in range(N)]
    for n in range(64):
        n = 2**n
        n1 = 0
        n2 = 0
        S_ = [0]*N
        T_ = [0]*N
        i1 = -1
        j1 = -1
        i2 = -1
        j2 = -1
        for i in l:
            s = S[i]
            u = U[i]&n
            if u>0:
                u = 1
            for j in l:
                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] = 1
                if v*n==ans[i][j]&n:
                    T_[j] = 1
        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)

if __name__ == '__main__':
    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()))
    main(N,S,T,U,V)

Submission status: Time Limit Exceeded

Solution code:
def main(N,S,T,U,V):
    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)

if __name__ == '__main__':
    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()))
    main(N,S,T,U,V)