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: Accepted

Solution code:
from functools import reduce
import operator

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()))
mat = [[0] * N for _ in range(N)]
counts_r = [[0] * 64 for _ in range(N)]
counts_c = [[0] * 64 for _ in range(N)]


class NotOK(Exception):
    pass


try:
    for i in range(N):
        for j in range(N):
            x = 0
            if not Ss[i]:
                x |= Us[i]
            if not Ts[j]:
                x |= Vs[j]
            if Ss[i] and (~Us[i] & x):
                raise NotOK
            if Ts[j] and (~Vs[j] & x):
                raise NotOK
            if Ss[i] and Ts[j]:
                x |= Us[i] & Vs[j]
            mat[i][j] = x
            for k in range(64):
                if (x >> k) & 1:
                    counts_r[i][k] += 1
                    counts_c[j][k] += 1

    def corr(x, vals, ors, counts):
        for k in range(64):
            if (x >> k) & 1 == 0:
                continue
            for j in range(N):
                if ors[j]:
                    continue
                if counts[j][k] >= N - 1:
                    continue
                counts[j][k] += 1
                vals[j] += 1 << k
                x -= 1 << k
                if not x:
                    return x
                break
        return x

    for i in range(N):
        vals = mat[i]
        if Ss[i]:
            x = reduce(operator.or_, vals)
            if corr(Us[i] & ~x, vals, Ts, counts_c):
                raise NotOK
        vals = []
        for j in range(N):
            vals.append(mat[j][i])
        if Ts[i]:
            x = reduce(operator.or_, vals)
            if corr(Vs[i] & ~x, vals, Ss, counts_r):
                raise NotOK
            for j in range(N):
                mat[j][i] = vals[j]
    for i in range(N):
        vals = mat[i]
        if Ss[i]:
            x = reduce(operator.or_, vals)
        else:
            x = reduce(operator.and_, vals)
        if x != Us[i]:
            raise NotOK
        vals = []
        for j in range(N):
            vals.append(mat[j][i])
        if Ts[i]:
            x = reduce(operator.or_, vals)
        else:
            x = reduce(operator.and_, vals)
        if x != Vs[i]:
            raise NotOK
    for i in range(N):
        print(*mat[i])
except NotOK:
    print(-1)

Submission status: Accepted

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)];a=[n*[0]for _ in[0]*n];r=range(n)
for b in range(64):
  e=1<<b;u=[k&e for k in f];v=[k&e for k in g];l=[0]*n;m=l[:]
  for i in r:
    for j in r:
      if(u[i]&v[j])|((s[i]^1)*u[i])|((t[j]^1)*v[j]):a[i][j]|=e;l[i]+=1;m[j]+=1
  for i in r:
    if(l[i]==0)*s[i]*u[i]:
      for j in r:
        if(t[j]^1)*(n-m[j]>1):a[i][j]|=e;m[j]+=1;break
  for j in r:
    if(m[j]==0)*t[j]*v[j]:
      for i in r:
        if(s[i]^1)*(n-l[i]>1):a[i][j]|=e;l[i]+=1;break
h=a[0][:];w=[i[0]for i in a]
for i in r:
  for j in r:w[i]=(w[i]|a[i][j]if s[i]else w[i]&a[i][j]);h[j]=(h[j]|a[i][j]if t[j]else h[j]&a[i][j])
if(g!=h)|(f!=w):print(-1);exit() 
for i in a:print(*i)

Submission status: Accepted

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)];a=[n*[0]for _ in[0]*n];r=range(n)
for b in range(64):
  e=1<<b;u=[k&e for k in f];v=[k&e for k in g];l=[0]*n;m=l[:]
  for i in r:
    for j in r:
      if(u[i]&v[j])|((s[i]^1)*u[i])|((t[j]^1)*v[j]):a[i][j]|=e;l[i]+=1;m[j]+=1
  for i in r:
    if s[i]*u[i]*(l[i]==0):
      for j in r:
        if(t[j]^1)*(n-m[j]>1):a[i][j]|=e;m[j]+=1;break
  for j in r:
    if t[j]*v[j]*(m[j]==0):
      for i in r:
        if(s[i]^1)*(n-l[i]>1):a[i][j]|=e;l[i]+=1;break
h=a[0][:];w=[i[0]for i in a]
for i in r:
  for j in r:w[i]=(w[i]|a[i][j]if s[i]else w[i]&a[i][j]);h[j]=(h[j]|a[i][j]if t[j]else h[j]&a[i][j])
if(g!=h)|(f!=w):print(-1);exit() 
for i in a:print(*i)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,*s=map(int,open(0).read().split())
s,t,f,g=[s[i-n:i]for i in range(n,4*n+1,n)]
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):
    if s[i]*u[i]*(l[i]==0):
      for j in range(n):
        if(t[j]^1)*(n-m[j]>1):ans[i][j]|=e;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):ans[i][j]|=e;l[i]+=1;break
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: Accepted

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):
    if s[i]*u[i]*(l[i]==0):
      for j in range(n):
        if(t[j]^1)*(n-m[j]>1):ans[i][j]|=e;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):ans[i][j]|=e;l[i]+=1;break
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: Accepted

Solution code:
import os

import sys
import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353


N = int(sys.stdin.buffer.readline())
row_or = list(map(int, sys.stdin.buffer.readline().split()))
col_or = list(map(int, sys.stdin.buffer.readline().split()))
right = list(map(int, sys.stdin.buffer.readline().split()))
down = list(map(int, sys.stdin.buffer.readline().split()))

row_or = np.array(row_or, dtype=bool)
row_and = ~row_or
col_or = np.array(col_or, dtype=bool)
col_and = ~col_or
right = np.array(right, dtype='uint64')
down = np.array(down, dtype='uint64')


def solve(right, down):
    ret = np.full((N, N), 7, dtype='uint64')
    yet_rows = []
    yet_cols = []
    used = [False] * 2
    for r in range(N):
        if row_or[r] and right[r] == 0:
            ret[r, :] = 0
            used[0] = True
        elif row_and[r] and right[r] == 1:
            ret[r, :] = 1
            used[1] = True
        else:
            yet_rows.append(r)
    for c in range(N):
        if col_or[c] and down[c] == 0:
            ret[:, c] = 0
            used[0] = True
        elif col_and[c] and down[c] == 1:
            ret[:, c] = 1
            used[1] = True
        else:
            yet_cols.append(c)

    if len(yet_cols) == 1:
        c = yet_cols[0]
        if not used[0]:
            # 0 を優先的に使いたい
            ret[yet_rows, c] = 0
            if down[c] == 1:
                for r in yet_rows:
                    # and で 0 のところは 0 じゃないといけないので、
                    # それ以外のところを 1 つ 1 にする
                    if row_or[r] and right[r] == 1:
                        ret[r, c] = 1
                        break
        elif not used[1]:
            # 1 を優先的に使いたい
            ret[yet_rows, c] = 1
            if down[c] == 0:
                for r in yet_rows:
                    # or で 1 のところは 1 じゃないといけないので、
                    # それ以外のところを 1 つ 0 にする
                    if row_and[r] and right[r] == 0:
                        ret[r, c] = 0
                        break
        else:
            # どっちでもいい
            ret[yet_rows, c] = np.arange(len(yet_rows), dtype=int) % 2
    elif len(yet_rows) == 1:
        r = yet_rows[0]
        if not used[0]:
            # 0 を優先的に使いたい
            ret[r, yet_cols] = 0
            if right[r] == 1:
                for c in yet_cols:
                    # and で 0 のところは 0 じゃないといけないので、
                    # それ以外のところを 1 つ 1 にする
                    if col_or[c] and down[c] == 1:
                        ret[r, c] = 1
                        break
        elif not used[1]:
            # 1 を優先的に使いたい
            ret[r, yet_cols] = 1
            if right[r] == 0:
                for c in yet_cols:
                    # or で 1 のところは 1 じゃないといけないので、
                    # それ以外のところを 1 つ 0 にする
                    if col_and[c] and down[c] == 0:
                        ret[r, c] = 0
                        break
        else:
            # どっちでもいい
            ret[r, yet_cols] = np.arange(len(yet_cols), dtype=int) % 2
    else:
        # 行列両方 2 つ以上ある
        for i, r in enumerate(yet_rows):
            ret[r, yet_cols] = (np.arange(len(yet_cols), dtype=int) + i) % 2

    # つくった
    ok = True
    for r in range(N):
        if row_and[r]:
            if right[r] == 1:
                ok &= np.all(ret[r, :] == 1)
            else:
                ok &= np.any(ret[r, :] == 0)
        else:
            if right[r] == 1:
                ok &= np.any(ret[r, :] == 1)
            else:
                ok &= np.all(ret[r, :] == 0)
    for c in range(N):
        if col_and[c]:
            if down[c] == 1:
                ok &= np.all(ret[:, c] == 1)
            else:
                ok &= np.any(ret[:, c] == 0)
        else:
            if down[c] == 1:
                ok &= np.any(ret[:, c] == 1)
            else:
                ok &= np.all(ret[:, c] == 0)
    assert np.all(ret <= 1)
    return ret & 1, ok


ans = np.zeros((N, N), dtype='uint64')
for i in range(64):
    bits, ok = solve(right >> i & 1, down >> i & 1)
    if not ok:
        print(-1)
        exit()
    ans |= bits << i

for row in ans:
    print(*row)

Submission status: Accepted

Solution code:
import numpy as np


def solve(n, s_list, t_list, u_list, v_list):

    x = np.zeros((n, n, 64), dtype=np.uint64)

    for k in range(64):

        # mod
        uk_list = [(u // (2 ** k)) % 2 for u in u_list]
        vk_list = [(v // (2 ** k)) % 2 for v in v_list]

        # count
        all_1_row = 0
        not_all_1_row = 0
        all_0_row = 0
        not_all_0_row = 0
        all_1_col = 0
        not_all_1_col = 0
        all_0_col = 0
        not_all_0_col = 0

        # row
        for i in range(n):
            if s_list[i] == 0 and uk_list[i] == 1:
                # all 1
                all_1_row += 1
            elif s_list[i] == 0 and uk_list[i] == 0:
                # not all 1
                not_all_1_row += 1
            elif s_list[i] == 1 and uk_list[i] == 0:
                # all 0
                all_0_row += 1
            else:
                # not all 0
                not_all_0_row += 1
        # col
        for j in range(n):
            if t_list[j] == 0 and vk_list[j] == 1:
                # all 1
                all_1_col += 1
            elif t_list[j] == 0 and vk_list[j] == 0:
                # not all 1
                not_all_1_col += 1
            elif t_list[j] == 1 and vk_list[j] == 0:
                # all 0
                all_0_col += 1
            else:
                # not all 0
                not_all_0_col += 1

        # impossible
        if all_1_row > 0 and all_0_col > 0:
            return [-1]
        elif all_0_row > 0 and all_1_col > 0:
            return [-1]
        elif all_1_col == n and not_all_1_row > 0:
            return [-1]
        elif all_0_col == n and not_all_0_row > 0:
            return [-1]
        elif all_1_row == n and not_all_1_col > 0:
            return [-1]
        elif all_0_row == n and not_all_0_col > 0:
            return [-1]

        # all 1 in both
        if all_1_row > 0 and all_1_col > 0:
            for i in range(n):
                # all 1
                if s_list[i] == 0 and uk_list[i] == 1:
                    x[i, :, k] = 1
            for j in range(n):
                # all 1
                if t_list[j] == 0 and vk_list[j] == 1:
                    x[:, j, k] = 1

        # all 0 in both
        elif all_0_row > 0 and all_0_col > 0:
            x[:, :, k] = 1
            for i in range(n):
                # all 0
                if s_list[i] == 1 and uk_list[i] == 0:
                    x[i, :, k] = 0
            for j in range(n):
                # all 0
                if t_list[j] == 1 and vk_list[j] == 0:
                    x[:, j, k] = 0

        # only row
        elif all_0_col == 0 and all_1_col == 0:
            if sum(uk_list) == n:
                x[:, :, k] = 1
                if all_1_row == n - 1:
                    if not_all_1_col == n:
                        return [-1]
                    else:
                        for i in range(n):
                            if s_list[i] == 1:
                                for j in range(n):
                                    if vk_list[j] == 0:
                                        x[i, j, k] = 0
                else:
                    cnt = 0
                    for i in range(n):
                        if s_list[i] == 1:
                            if cnt == 0:
                                x[i, 0::2, k] = 0
                            elif cnt == 1:
                                x[i, 1::2, k] = 0
                            cnt += 1

            elif sum(uk_list) == 0:
                x[:, :, k] = 0
                if all_0_row == n - 1:
                    if not_all_0_col == n:
                        return [-1]
                    else:
                        for i in range(n):
                            if s_list[i] == 0:
                                for j in range(n):
                                    if t_list[j] == 1 and vk_list[j] == 1:
                                        x[i, j, k] = 1
                else:
                    cnt = 0
                    for i in range(n):
                        if s_list[i] == 0:
                            if cnt == 0:
                                x[i, 0::2, k] = 1
                            elif cnt == 1:
                                x[i, 1::2, k] = 1
                            cnt += 1
            else:
                for i in range(n):
                    x[i, :, k] = uk_list[i]
        # only col
        else:
            if sum(vk_list) == n:
                x[:, :, k] = 1
                if all_1_col == n - 1:
                    if not_all_1_row == n:
                        return [-1]
                    else:
                        for j in range(n):
                            if t_list[j] == 1:
                                for i in range(n):
                                    if s_list[i] == 0 and uk_list[i] == 0:
                                        x[i, j, k] = 0
                else:
                    cnt = 0
                    for j in range(n):
                        if t_list[j] == 1:
                            if cnt == 0:
                                x[0::2, j, k] = 0
                            elif cnt == 1:
                                x[1::2, j, k] = 0
                            cnt += 1

            elif sum(vk_list) == 0:
                x[:, :, k] = 0
                if all_0_col == n - 1:
                    if not_all_0_row == n:
                        return [-1]
                    else:
                        for j in range(n):
                            if t_list[j] == 0:
                                for i in range(n):
                                    if s_list[i] == 1 and uk_list[i] == 1:
                                        x[i, j, k] = 1
                else:
                    cnt = 0
                    for j in range(n):
                        if t_list[j] == 0:
                            if cnt == 0:
                                x[0::2, j, k] = 1
                            elif cnt == 1:
                                x[1::2, j, k] = 1
                            cnt += 1
            else:
                for j in range(n):
                    x[:, j, k] = vk_list[j]

    for k in range(64):
        x[:, :, k] = x[:, :, k] * (2 ** k)

    y = x.sum(axis=2)
    res = []
    for i in range(n):
        res.append(" ".join([str(z) for z in y[i, :]]))

    # print(res)

    return res


def main():
    n = int(input())
    s_list = list(map(int, input().split()))
    t_list = list(map(int, input().split()))
    u_list = list(map(int, input().split()))
    v_list = list(map(int, input().split()))
    res = solve(n, s_list, t_list, u_list, v_list)
    for r in res:
        print(r)


def test():
    assert solve(2, [0, 1], [1, 0], [1, 1], [1, 0]) == 0
    assert solve(2, [1, 1], [1, 0], [15, 15], [15, 11]) == 0


if __name__ == "__main__":
    # test()
    main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import numpy as np

N = int(readline())
S = np.array(readline().split(), np.uint64)
T = np.array(readline().split(), np.uint64)
U = np.array(readline().split(), np.uint64)
V = np.array(readline().split(), np.uint64)


def solve(S, T, U, V):
    A = np.zeros((N, N), np.uint64)
    if N == 1:
        return np.array([[U[0]]], np.uint64)
    all_one_row = (S == 0) & (U == 1)
    all_zero_row = (S == 1) & (U == 0)
    r = np.any(all_zero_row), np.any(all_one_row)
    all_one_col = (T == 0) & (V == 1)
    all_zero_col = (T == 1) & (V == 0)
    c = np.any(all_zero_col), np.any(all_one_col)
    if (c[0] or c[1]) and not (r[0] or r[1]):
        return solve(T, S, V, U).T
    # 確定条件があるなら行にある
    if not (r[0] or r[1]):
        # 確定条件なし。十分均一ならok
        A[1::2, ::2] = 1
        A[::2, 1::2] = 1
        return A
    # 少なくとも行に確定条件がある場合
    if r[0] and r[1]:
        # 列の運命は確定なので、行本位で入れればよい
        A += U[:, None]
        return A
    if r[0]:
        if c[1]:
            return A
        if c[0]:
            # 行列とも強制的に 0 が入る。他は 1 を埋める。
            A += 1
            A[all_zero_row, :] = 0
            A[:, all_zero_col] = 0
            return A
        # 列に強制条件なし
        if np.any(U == 1):
            A += U[:, None]
            return A
        # 行は、all or exists で 0
        # 列は、exists 0 or 1
        if np.any(V == 0):
            A += V[None, :]
            A[all_zero_row] = 0
            return A
        if N - 1 <= np.count_nonzero(all_zero_row):
            return A
        ind = np.where(~all_zero_row)[0]
        A[ind[0], 0] = 1
        A[ind[-1], 1:] = 1
        return A
    if r[1]:
        if c[0]:
            return A
        if c[1]:
            # 行列とも強制的に 1 が入る。他は 0 を埋める。
            A[all_one_row, :] = 1
            A[:, all_one_col] = 1
            return A
        # 列に強制条件なし
        if np.any(U == 0):
            A += U[:, None]
            return A
        # 行は、all or exists で 1
        # 列は、exists 0 or 1
        if np.any(V == 1):
            A += V[None, :]
            A[all_one_row] = 1
            return A
        if N - 1 <= np.count_nonzero(all_one_row):
            return A
        A += 1
        ind = np.where(~all_one_row)[0]
        A[ind[0], 0] = 0
        A[ind[-1], 1:] = 0
        return A


def test(S, T, U, V, A):
    row_or = np.bitwise_or.reduce(A, axis=1)
    row_and = np.bitwise_and.reduce(A, axis=1)
    cond_row = np.all(U[S == 0] == row_and[S == 0]) and np.all(U[S == 1] == row_or[S == 1])
    col_or = np.bitwise_or.reduce(A, axis=0)
    col_and = np.bitwise_and.reduce(A, axis=0)
    cond_col = np.all(V[T == 0] == col_and[T == 0]) and np.all(V[T == 1] == col_or[T == 1])
    return cond_row and cond_col


A = np.zeros((N, N), np.uint64)
for k in range(64):
    A ^= solve(S, T, (U >> k) & 1, (V >> k) & 1) << k

if not test(S, T, U, V, A):
    print(-1)
else:
    print('\n'.join(' '.join(row) for row in A.astype(str)))

Submission status: Accepted

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)]
ss=[u[i]if s[i]==0 else 0 for i in range(n)]
tt=[v[i]if t[i]==0 else 0 for i in range(n)]
son=[[]for _ in range(n)]
ton=[[]for _ in range(n)]
sno=[[n-1]*64 for _ in range(n)]
tno=[[n-1]*64 for _ in range(n)]
for i in range(n):
  for j in range(n):
    ans[i][j]=u[i]&v[j]
    if s[i]==0:
      ans[i][j]|=u[i]
      ss[i]&=ans[i][j]
    else:
      ss[i]|=ans[i][j]
    if t[j]==0:
      ans[i][j]|=v[j]
      tt[j]&=ans[i][j]
    else:
      tt[j]|=ans[i][j]
    if s[i]==0 or t[i]==0:
      for k in range(64):
        if ans[i][j]&1<<k:
          if s[i]==0:sno[i][k]-=1
          if t[j]==0:tno[j][k]-=1
    if j==n-1:
      if s[i]==1:
        if ss[i]|u[i]>u[i]:print(-1);exit()
        if ss[i]!=u[i]:
          for k in range(64):
            if u[i]&1<<k:
              if (ss[i]&1<<k)==0:
                son[i].append(k)
          ss[i]=1
        else:ss[i]=0
      else:
        if ss[i]!=u[i]:print(-1);exit()
        else:ss[i]=2
    if i==n-1:
      if t[j]==1:
        if tt[j]|v[j]>v[j]:print(-1);exit()
        if tt[j]!=v[j]:
          for k in range(64):
            if v[j]&1<<k:
              if (tt[j]&1<<k)==0:
                ton[j].append(k)
          tt[j]=1
        else:tt[j]=0
      else:
        if tt[j]!=v[j]:print(-1);exit()
        else:tt[j]=2
for i in range(n):
  for k in son[i]:
    for j in range(n):
      if t[j]==0:
        if tno[j][k]>0:
          ans[i][j]|=1<<k
          tno[j][k]-=1
          break
      if j==n-1:print(-1);exit()
for j in range(n):
  for k in ton[j]:
    for i in range(n):
      if s[i]==0:
        if sno[i][k]>0:
          ans[i][j]|=1<<k
          sno[i][k]-=1
          break
      if i==n-1:print(-1);exit()
for i in range(n):
  if s[i]==0:uu=ans[i][0]
  else:uu=0
  for j in range(n):
    if s[i]==0:uu&=ans[i][j]
    else:uu|=ans[i][j]
  if uu!=u[i]:print(-1);exit()
for j in range(n):
  if t[j]==0:vv=ans[0][j]
  else:vv=0
  for i in range(n):
    if t[j]==0:vv&=ans[i][j]
    else:vv|=ans[i][j]
  if vv!=v[j]:print(-1);exit()
for i in ans:print(*i)

Submission status: Accepted

Solution code:
import sys
range = xrange
input = raw_input
 
big = int(2**63 - 1)
big2 = 2**64 - 1
def flipper(x):
    if x > big:
        return int(x - 2**64)
    else:
        return x
 
n = int(input())
S = [int(x) for x in input().split()]
T = [int(x) for x in input().split()]
 
Scount = [[0] for _ in range(2)]
for s in S:
    Scount[0].append((Scount[0][-1] + (s == 0)) & 1)
    Scount[1].append((Scount[1][-1] + (s == 1)) & 1)
 
Tcount = [[0] for _ in range(2)]
for t in T:
    Tcount[0].append((Tcount[0][-1] + (t == 0)) & 1)
    Tcount[1].append((Tcount[1][-1] + (t == 1)) & 1)
 
U = [flipper(int(x)) for x in input().split()]
V = [flipper(int(x)) for x in input().split()]
 
A = [[0] * n for _ in range(n)]

def solve(layer, par):
    ubit = [1 & (u >> layer) for u in U]
    vbit = [1 & (v >> layer) for v in V]
    mat = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if ubit[i] != S[i]:
                mat[i][j] = ubit[i]
            elif vbit[j] != T[j]:
                mat[i][j] = vbit[j]
            elif S[i] == T[j]:
                mat[i][j] = ubit[i]
            else:
                #assert(S[i] != T[j])
                mat[i][j] = par ^ Scount[S[i]][i] ^ Tcount[T[j]][j]
    
    for i in range(n):
        x = mat[i][0]
        if S[i] == 0:
            for j in range(n):
                x &= mat[i][j]
        else:
            for j in range(n):
                x |= mat[i][j]
        if x != ubit[i]:
            return False
    
    for j in range(n):
        x = mat[0][j]
        if T[j] == 0:
            for i in range(n):
                x &= mat[i][j]
        else:
            for i in range(n):
                x |= mat[i][j]
        if x != vbit[j]:
            return False
    for i in range(n):
        for j in range(n):
            A[i][j] += mat[i][j] << layer
    return True

for layer in range(64):
    if not solve(layer, 0):
        if not solve(layer, 1):
            print -1
            sys.exit()
 
print '\n'.join(' '.join(str(x) for x in row) for row in A)

Submission status: Accepted

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(4):
        if st > 1:
            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
        else:
            for i in range(len(H)):
                for j in range(len(W)):
                    h, w = H[i], W[j]
                    res[h][w] = st
        flag = True
        for i in H:
            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 W:
                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]))