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:
#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

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()))

mask_gyo = [((1<<N)-1)<<(N*i) for i in range(N)]
mask_retu = [(((1<<(N**2))-1)//((1<<N)-1))<<i for i in range(N)]

res = [[0]*N for j in range(N)]

for n in range(64):
  u = sum(((U[i]>>n)&1)<<i for i in range(N))
  v = sum(((V[i]>>n)&1)<<i for i in range(N))
  b = 0
  check = 0
  ###行のAND=1とOR=0を埋める###
  for i in range(N):
    if S[i] !=((u>>i) & 1):
      if((u>>i) & 1) == 1:
        b |= mask_gyo[i]
      check |= mask_gyo[i]
  ###列のAND=1とOR=0を埋める###
  for i in range(N):
    if T[i] !=((v>>i) & 1):
      if((v>>i) & 1) == 1:
        if b & mask_retu[i] != check & mask_retu[i]:
          print(-1)
          exit()
        b |= mask_retu[i]
      if((v>>i) & 1) == 0:
        if (b & mask_retu[i]) ^ (check & mask_retu[i]) != (check & mask_retu[i]):
          print(-1)
          exit()
      check |= mask_retu[i]


  ###行と列の値が一致するところを埋める###  
  
  same = (1<<N**2)-1-sum( (v^((1<<N)-1)*((u>>i)&1))<<N*i for i in range(N))
  same_b = same & (v * mask_retu[0])
  b |= same_b
  check |= same

  ###行のOR=1を満たしていく###  
  for i in range(N):
    if S[i] ==((u>>i) & 1) == 1:
      if b & mask_gyo[i] == 0: #まだ満たされてない行を発見した場合
        flag = 0 #未解決
        for j in range(N):
          digit = (1<<j)<<(N*i)
          if T[j] ==((v>>j) & 1) == 0 and check & digit == 0 and count_bit(b & mask_retu[j])<N-1:
            b |= digit
            check |= digit
            flag = 1 #解決
            break
        if not flag:
          print(-1)
          exit()
  ###列のOR=1を満たしていく###  
  for i in range(N):
    if T[i] ==((v>>i) & 1) == 1:
      if b & mask_retu[i] == 0: #まだ満たされてない列を発見した場合
        flag = 0 #未解決
        for j in range(N):
          digit = (1<<i)<<(N*j)
          if S[j] ==((u>>j) & 1)== 0 and check & digit == 0 and count_bit(b & mask_gyo[j])<N-1:
            b |= digit
            check |= digit
            flag = 1 #解決
            break         
        if not flag:
          print(-1)
          exit()

  for i in range(N):
    if S[i] == 0 and((u>>i) & 1) == 0:
      if b & mask_gyo[i] == mask_gyo[i]:
        print(-1)
        exit()
    if S[i] == 0 and((u>>i) & 1) == 1:
      if b & mask_gyo[i] != mask_gyo[i]:
        print(-1)
        exit()
    if S[i] == 1 and((u>>i) & 1) == 0:
      if b & mask_gyo[i] != 0:
        print(-1)
        exit()
    if S[i] == 1 and((u>>i) & 1) == 1:
      if b & mask_gyo[i] == 0:
        print(-1)
        exit()
  
  for i in range(N):
    if T[i] == 0 and((v>>i) & 1) == 0:
      if b & mask_retu[i] == mask_retu[i]:
        print(-1)
        exit()
    if T[i] == 0 and((v>>i) & 1) == 1:
      if b & mask_retu[i] != mask_retu[i]:
        print(-1)
        exit()
    if T[i] == 1 and((v>>i) & 1) == 0:
      if b & mask_retu[i] != 0:
        print(-1)
        exit()
    if T[i] == 1 and((v>>i) & 1) == 1:
      if b & mask_retu[i] == 0:
        print(-1)
        exit()
  tempb = list(bin(b)[2:])
  for j in range(N):
    for i in range(N):
      if tempb:
        res[j][i] |= int(tempb.pop())<<n



for item in res:
  print(*item)

Submission status: Time Limit Exceeded

Solution code:
#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

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()))

mask_gyo = [((1<<N)-1)<<(N*i) for i in range(N)]
mask_retu = [(((1<<(N**2))-1)//((1<<N)-1))<<i for i in range(N)]

B = []

for n in range(64):
  u = sum(((U[i]>>n)&1)<<i for i in range(N))
  v = sum(((V[i]>>n)&1)<<i for i in range(N))
  b = 0
  check = 0
  ###行のAND=1とOR=0を埋める###
  for i in range(N):
    if S[i] !=((u>>i) & 1):
      if((u>>i) & 1) == 1:
        b |= mask_gyo[i]
      check |= mask_gyo[i]
  ###列のAND=1とOR=0を埋める###
  for i in range(N):
    if T[i] !=((v>>i) & 1):
      if((v>>i) & 1) == 1:
        if b & mask_retu[i] != check & mask_retu[i]:
          print(-1)
          exit()
        b |= mask_retu[i]
      if((v>>i) & 1) == 0:
        if (b & mask_retu[i]) ^ (check & mask_retu[i]) != (check & mask_retu[i]):
          print(-1)
          exit()
      check |= mask_retu[i]


  ###行と列の値が一致するところを埋める###  
  
  same = (1<<N**2)-1-sum( (v^((1<<N)-1)*((u>>i)&1))<<N*i for i in range(N))
  same_b = same & (v * mask_retu[0])
  b |= same_b
  check |= same

  ###行のOR=1を満たしていく###  
  for i in range(N):
    if S[i] ==((u>>i) & 1) == 1:
      if b & mask_gyo[i] == 0: #まだ満たされてない行を発見した場合
        flag = 0 #未解決
        for j in range(N):
          digit = (1<<j)<<(N*i)
          if T[j] ==((v>>j) & 1) == 0 and check & digit == 0 and count_bit(b & mask_retu[j])<N-1:
            b |= digit
            check |= digit
            flag = 1 #解決
            break
        if not flag:
          print(-1)
          exit()
  ###列のOR=1を満たしていく###  
  for i in range(N):
    if T[i] ==((v>>i) & 1) == 1:
      if b & mask_retu[i] == 0: #まだ満たされてない列を発見した場合
        flag = 0 #未解決
        for j in range(N):
          digit = (1<<i)<<(N*j)
          if S[j] ==((u>>j) & 1)== 0 and check & digit == 0 and count_bit(b & mask_gyo[j])<N-1:
            b |= digit
            check |= digit
            flag = 1 #解決
            break         
        if not flag:
          print(-1)
          exit()

  for i in range(N):
    if S[i] == 0 and((u>>i) & 1) == 0:
      if b & mask_gyo[i] == mask_gyo[i]:
        print(-1)
        exit()
    if S[i] == 0 and((u>>i) & 1) == 1:
      if b & mask_gyo[i] != mask_gyo[i]:
        print(-1)
        exit()
    if S[i] == 1 and((u>>i) & 1) == 0:
      if b & mask_gyo[i] != 0:
        print(-1)
        exit()
    if S[i] == 1 and((u>>i) & 1) == 1:
      if b & mask_gyo[i] == 0:
        print(-1)
        exit()
  
  for i in range(N):
    if T[i] == 0 and((v>>i) & 1) == 0:
      if b & mask_retu[i] == mask_retu[i]:
        print(-1)
        exit()
    if T[i] == 0 and((v>>i) & 1) == 1:
      if b & mask_retu[i] != mask_retu[i]:
        print(-1)
        exit()
    if T[i] == 1 and((v>>i) & 1) == 0:
      if b & mask_retu[i] != 0:
        print(-1)
        exit()
    if T[i] == 1 and((v>>i) & 1) == 1:
      if b & mask_retu[i] == 0:
        print(-1)
        exit()
  
  B.append(b)
"""
  for j in range(N):
    for i in range(N):
      digit = (1<<i)<<(N*j)
      a = not (b & digit == 0)
      res[j][i] += a<<n
"""

"""
for item in res:
  print(*item)
"""
for j in range(N):
  for i in range(N):
    ans = 0
    digit = (1<<i)<<(N*j)
    for n in range(64):
      b = B[n]
      a = not (b & digit == 0)
      ans += a<<n
    print(ans,end=" ")
  print()

Submission status: Time Limit Exceeded

Solution code:
#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

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()))

mask_gyo = [((1<<N)-1)<<(N*i) for i in range(N)]
mask_retu = [(sum(1<<(N*j) for j in range(N)))<<i for i in range(N)]

res = [[0 for i in range(N)] for j in range(N)]

for n in range(64):
  u = [(i>>n)&1 for i in U]
  v = [(i>>n)&1 for i in V]
  b = 0
  check = 0
  ###行のAND=1とOR=0を埋める###
  for i in range(N):
    if S[i] != u[i]:
      if u[i] == 1:
        b |= mask_gyo[i]
      check |= mask_gyo[i]
  ###列のAND=1とOR=0を埋める###
  for i in range(N):
    if T[i] != v[i]:
      if v[i] == 1:
        if b & mask_retu[i] != check & mask_retu[i]:
          print(-1)
          exit()
        b |= mask_retu[i]
      if v[i] == 0:
        if (b & mask_retu[i]) ^ (check & mask_retu[i]) != (check & mask_retu[i]):
          print(-1)
          exit()
      check |= mask_retu[i]

  ###行と列の値が一致するところを埋める###  
  for j in range(N):
    for i in range(N):
      if u[j] == v[i]:
        digit = (1<<i)<<(N*j)
        b |= digit*u[j]
        check |= digit
  ###行のOR=1を満たしていく###  
  for i in range(N):
    if S[i] == u[i] == 1:
      if b & mask_gyo[i] == 0: #まだ満たされてない行を発見した場合
        flag = 0 #未解決
        for j in range(N):
          digit = (1<<j)<<(N*i)
          if T[j] == v[j] == 0 and check & digit == 0 and count_bit(b & mask_retu[j])<N-1:
            b |= digit
            check |= digit
            flag = 1 #解決
            break
        if not flag:
          print(-1)
          exit()
  ###列のOR=1を満たしていく###  
  for i in range(N):
    if T[i] == v[i] == 1:
      if b & mask_retu[i] == 0: #まだ満たされてない列を発見した場合
        flag = 0 #未解決
        for j in range(N):
          digit = (1<<i)<<(N*j)
          if S[j] == u[j]== 0 and check & digit == 0 and count_bit(b & mask_gyo[j])<N-1:
            b |= digit
            check |= digit
            flag = 1 #解決
            break         
        if not flag:
          print(-1)
          exit()

  for i in range(N):
    if S[i] == 0 and u[i] == 0:
      if b & mask_gyo[i] == mask_gyo[i]:
        print(-1)
        exit()
    if S[i] == 0 and u[i] == 1:
      if b & mask_gyo[i] != mask_gyo[i]:
        print(-1)
        exit()
    if S[i] == 1 and u[i] == 0:
      if b & mask_gyo[i] != 0:
        print(-1)
        exit()
    if S[i] == 1 and u[i] == 1:
      if b & mask_gyo[i] == 0:
        print(-1)
        exit()
  
  for i in range(N):
    if T[i] == 0 and v[i] == 0:
      if b & mask_retu[i] == mask_retu[i]:
        print(-1)
        exit()
    if T[i] == 0 and v[i] == 1:
      if b & mask_retu[i] != mask_retu[i]:
        print(-1)
        exit()
    if T[i] == 1 and v[i] == 0:
      if b & mask_retu[i] != 0:
        print(-1)
        exit()
    if T[i] == 1 and v[i] == 1:
      if b & mask_retu[i] == 0:
        print(-1)
        exit()
        
  
  for j in range(N):
    for i in range(N):
      digit = (1<<i)<<(N*j)
      a = not (b & digit == 0)
      res[j][i] += a<<n

  
for item in res:
  print(*item)

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce


def add_row(ans, n, i, k):
    for j in range(n):
        ans[i][j] |= k


def add_column(ans, n, j, k):
    for i in range(n):
        ans[i][j] |= k


def solve(n, sss, ttt, uuu, vvv):
    max_d = max(max(uuu).bit_length(), max(vvv).bit_length())
    ans = [[0] * n for _ in range(n)]

    for d in range(max_d):
        k = 1 << d
        ambiguous_i = []
        ambiguous_j = []
        filled_i = [False, False]
        filled_j = [False, False]
        for i, (s, u) in enumerate(zip(sss, uuu)):
            if s == 0:
                if u & k:
                    add_row(ans, n, i, k)
                    filled_i[1] = True
                else:
                    ambiguous_i.append((i, 0))
            else:
                if u & k:
                    ambiguous_i.append((i, 1))
                else:
                    filled_i[0] = True
        for j, (t, v) in enumerate(zip(ttt, vvv)):
            if t == 0:
                if v & k:
                    if filled_i[0]:
                        return -1
                    add_column(ans, n, j, k)
                    filled_j[1] = True
                else:
                    ambiguous_j.append((j, 0))
            else:
                if v & k:
                    ambiguous_j.append((j, 1))
                else:
                    if filled_i[1]:
                        return -1
                    filled_j[0] = True

        # print(d)
        # print(ans)
        # print(ambiguous_i)
        # print(ambiguous_j)

        # print(*map('{:064b}'.format, [k] * (n + 1)))
        # for i in range(n):
        #     print(*map('{:064b}'.format, ans[i]), end=' ')
        #     print('{:064b}'.format(uuu[i]))
        # print(*map('{:064b}'.format, vvv))
        # print(ambiguous_i, ambiguous_j)
        # print(filled_i, filled_j)
        # print()

        if len(ambiguous_i) == 0:
            amb = set(bj for j, bj in ambiguous_j)
            for bj in amb:
                if not filled_i[bj]:
                    return -1
        elif len(ambiguous_j) == 0:
            amb = set(bi for i, bi in ambiguous_i)
            for bi in amb:
                if not filled_j[bi]:
                    return -1
        elif len(ambiguous_i) == 1:
            i, bi = ambiguous_i[0]
            if filled_j[bi]:
                for j, bj in ambiguous_j:
                    if bj:
                        ans[i][j] |= k
            elif filled_i[bi ^ 1]:
                if bi:
                    for j, bj in ambiguous_j:
                        ans[i][j] |= k
            else:
                ok = False
                for j, bj in ambiguous_j:
                    if bj:
                        ans[i][j] |= k
                    if bi == bj:
                        ok = True
                if not ok:
                    return -1
        elif len(ambiguous_j) == 1:
            j, bj = ambiguous_j[0]
            if filled_i[bj]:
                for i, bi in ambiguous_i:
                    if bi:
                        ans[i][j] |= k
            elif filled_j[bj ^ 1]:
                if bj == 1:
                    for i, bi in ambiguous_i:
                        ans[i][j] |= k
            else:
                ok = False
                for i, bi in ambiguous_i:
                    if bi:
                        ans[i][j] |= k
                    if bi == bj:
                        ok = True
                if not ok:
                    return -1
        else:
            for ii, (i, bi) in enumerate(ambiguous_i):
                for jj, (j, bj) in enumerate(ambiguous_j):
                    if (ii ^ jj) & 1:
                        ans[i][j] |= k

    return ans


def debug(n, sss, ttt, uuu, vvv, ans):
    from operator import or_, and_
    dbg = [row.copy() for row in ans]
    for i in range(n):
        func = and_ if sss[i] == 0 else or_
        dbg[i].append(reduce(func, dbg[i]))
        dbg[i].append(uuu[i])
    vertical = []
    correct = []
    for j in range(n):
        func = and_ if ttt[j] == 0 else or_
        vertical.append(reduce(func, (dbg[i][j] for i in range(n))))
        correct.append(vvv[j])
    dbg.append(vertical)
    dbg.append(correct)

    for row in dbg:
        print(*map('{:064b}'.format, row))


n = int(input())
sss = list(map(int, input().split()))
ttt = list(map(int, input().split()))
uuu = list(map(int, input().split()))
vvv = list(map(int, input().split()))

ans = solve(n, sss, ttt, uuu, vvv)
if ans == -1:
    print(ans)
else:
    for row in ans:
        print(*row)

Submission status: Time Limit Exceeded

Solution code:
# F - I hate Matrix Construction

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()))
assert len(s) == len(t) == n
assert len(u) == len(v) == n

nbits = 64
AND = 0
OR  = 1

# conflict check
for i in range(n):
    for j in range(n):
        if (s[i] == AND and t[j] == OR  and  u[i] & ~v[j]) or \
           (s[i] == OR  and t[j] == AND and ~u[i] &  v[j]):
            print(-1)
            exit()

# 初期配列
A = [[u[i]] * n for i in range(n)]
for i in range(n):
    for j in range(n):
        if t[j] == AND:
            A[i][j] |= v[j]  # v[j]で1のビットは1
        else:
            A[i][j] &= v[j]  # v[j]で0のビットは0

# 1であるビット数を数える
ucount = [[0] * nbits for i in range(n)]
vcount = [[0] * nbits for j in range(n)]
for i in range(n):
    for j in range(n):
        for k in range(nbits):
            if A[i][j] & (1 << k):
                ucount[i][k] += 1
                vcount[j][k] += 1

def must_set(s, u, ucount, i, k):
    return s[i] == OR  and u[i] & (1 << k) and ucount[i][k] == 0
def must_clear(s, u, ucount, i, k):
    return s[i] == AND and u[i] & (1 << k) == 0 and ucount[i][k] == n

def find_and_set(t, v, vcount, k):
    "いずれかの列の第kビットを1にする"
    for j in range(n):
        if (t[j] == OR  and v[j] & (1 << k)) or \
           (t[j] == AND and v[j] & (1 << k) == 0 and vcount[j][k] < n - 1):
            return j
    raise Exception

def find_and_clear(t, v, vcount, k):
    "いずれかの列の第kビットを0にする"
    for j in range(n):
        if (t[j] == AND and v[j] & (1 << k) == 0) or \
           (t[j] == OR  and v[j] & (1 << k) and vcount[j][k] > 1):
            return j
    raise Exception

# 仕様通りでない箇所を修正
try:
    for i in range(n):
        for k in range(nbits):
            if must_set(s, u, ucount, i, k):
                # いずれかの列の第kビットを1にする
                j = find_and_set(t, v, vcount, k)
                A[i][j] |= 1 << k
                ucount[i][k] += 1
                vcount[j][k] += 1
            elif must_clear(s, u, ucount, i, k):
                # いずれかの列の第kビットを0にする
                j = find_and_clear(t, v, vcount, k)
                A[i][j] &= ~(1 << k)
                ucount[i][k] -= 1
                vcount[j][k] -= 1
    for j in range(n):
        for k in range(nbits):
            if must_set(t, v, vcount, j, k):
                i = find_and_set(s, u, ucount, k)
                A[i][j] |= 1 << k
                ucount[i][k] += 1
                vcount[j][k] += 1
            elif must_clear(t, v, vcount, j, k):
                i = find_and_clear(s, u, ucount, k)
                A[i][j] &= ~(1 << k)
                ucount[i][k] -= 1
                vcount[j][k] -= 1
except:
    print(-1)
    exit()

for i in range(n):
    print(' '.join(map(str, A[i])))

Submission status: Time Limit Exceeded

Solution code:
# F - I hate Matrix Construction

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()))
assert len(s) == len(t) == n
assert len(u) == len(v) == n

nbits = 64
AND = 0
OR  = 1

# conflict check
for i in range(n):
    for j in range(n):
        if (s[i] == AND and t[j] == OR  and  u[i] & ~v[j]) or \
           (s[i] == OR  and t[j] == AND and ~u[i] &  v[j]):
            print(-1)
            exit()

A = [[u[i]] * n for i in range(n)]
for j in range(n):
    for i in range(n):
        if t[j] == AND:
            A[i][j] |= v[j]  # v[j]で1のビットは1
        else:
            A[i][j] &= v[j]  # v[j]で0のビットは0

# 1であるビット数を数える
ucount = [[0] * nbits for i in range(n)]
vcount = [[0] * nbits for j in range(n)]
for k in range(nbits):
    mask = 1 << k
    for i in range(n):
        ucount[i][k] = sum(1 for j in range(n) if A[i][j] & mask)
    for j in range(n):
        vcount[j][k] = sum(1 for i in range(n) if A[i][j] & mask)

for k in range(nbits):
    mask = 1 << k
    for i in range(n):
        if s[i] == OR and u[i] & (1 << k) and ucount[i][k] == 0:
            # いずれかの列の第kビットを1にする
            for j in range(n):
                if (t[j] == OR  and v[j] & mask) or \
                   (t[j] == AND and v[j] & mask == 0 and vcount[j][k] < n - 1):
                    A[i][j] |= mask
                    ucount[i][k] += 1
                    vcount[j][k] += 1
                    break
            else:
                print(-1)
                exit()
        if s[i] == AND and u[i] & mask == 0 and ucount[i][k] == n:
            # いずれかの列の第kビットを0にする
            for j in range(n):
                if (t[j] == AND and v[j] & mask == 0) or \
                   (t[j] == OR  and v[j] & mask and vcount[j][k] > 1):
                    A[i][j] &= ~mask
                    ucount[i][k] -= 1
                    vcount[j][k] -= 1
                    break
            else:
                print(-1)
                exit()
    for j in range(n):
        if t[j] == OR and v[j] & mask and vcount[j][k] == 0:
            for i in range(n):
                if (s[i] == OR  and u[i] & mask) or \
                   (s[i] == AND and u[i] & mask == 0 and ucount[i][k] < n - 1):
                    A[i][j] |= mask
                    ucount[i][k] += 1
                    vcount[j][k] += 1
                    break
            else:
                print(-1)
                exit()
        if t[j] == AND and v[j] & mask == 0 and vcount[j][k] == n:
            for i in range(n):
                if (s[i] == AND and u[i] & mask == 0) or \
                   (s[i] == OR  and u[i] & mask and ucount[i][k] > 1):
                    A[i][j] &= ~mask
                    ucount[i][k] -= 1
                    vcount[j][k] -= 1
                    break
            else:
                print(-1)
                exit()

for i in range(n):
    print(' '.join(map(str, A[i])))

Submission status: Time Limit Exceeded

Solution code:
# F - I hate Matrix Construction

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()))
assert len(s) == len(t) == n
assert len(u) == len(v) == n

nbits = 64
AND = 0
OR  = 1

# conflict check
for i in range(n):
    for j in range(n):
        if (s[i] == AND and t[j] == OR  and  u[i] & ~v[j]) or \
           (s[i] == OR  and t[j] == AND and ~u[i] &  v[j]):
            print(-1)
            exit()

A = [[u[i]] * n for i in range(n)]
for j in range(n):
    for i in range(n):
        if t[j] == AND:
            A[i][j] |= v[j]  # v[j]で1のビットは1
        else:
            A[i][j] &= v[j]  # v[j]で0のビットは0

# 1であるビット数を数える
ucount = [[0] * nbits for i in range(n)]
vcount = [[0] * nbits for j in range(n)]
for k in range(nbits):
    for i in range(n):
        ucount[i][k] = sum(1 for j in range(n) if A[i][j] & (1 << k))
    for j in range(n):
        vcount[j][k] = sum(1 for i in range(n) if A[i][j] & (1 << k))

for k in range(nbits):
    for i in range(n):
        if s[i] == OR and u[i] & (1 << k) and ucount[i][k] == 0:
            # いずれかの列の第kビットを1にする
            for j in range(n):
                if (t[j] == OR  and v[j] & (1 << k)) or \
                   (t[j] == AND and v[j] & (1 << k) == 0 and \
                    vcount[j][k] < n - 1):
                    A[i][j] |= 1 << k
                    ucount[i][k] += 1
                    vcount[j][k] += 1
                    break
            else:
                print(-1)
                exit()
        if s[i] == AND and u[i] & (1 << k) == 0 and ucount[i][k] == n:
            # いずれかの列の第kビットを0にする
            for j in range(n):
                if (t[j] == AND and v[j] & (1 << k) == 0) or \
                   (t[j] == OR  and v[j] & (1 << k) and vcount[j][k] > 1):
                    A[i][j] &= ~(1 << k)
                    ucount[i][k] -= 1
                    vcount[j][k] -= 1
                    break
            else:
                print(-1)
                exit()
    for j in range(n):
        if t[j] == OR and v[j] & (1 << k) and vcount[j][k] == 0:
            for i in range(n):
                if (s[i] == OR  and u[i] & (1 << k)) or \
                   (s[i] == AND and u[i] & (1 << k) == 0 and \
                    ucount[i][k] < n - 1):
                    A[i][j] |= 1 << k
                    ucount[i][k] += 1
                    vcount[j][k] += 1
                    break
            else:
                print(-1)
                exit()
        if t[j] == AND and v[j] & (1 << k) == 0 and vcount[j][k] == n:
            for i in range(n):
                if (s[i] == AND and u[i] & (1 << k) == 0) or \
                   (s[i] == OR  and u[i] & (1 << k) and ucount[i][k] > 1):
                    A[i][j] &= ~(1 << k)
                    ucount[i][k] -= 1
                    vcount[j][k] -= 1
                    break
            else:
                print(-1)
                exit()
for i in range(n):
    print(' '.join(map(str, A[i])))

Submission status: Time Limit Exceeded

Solution code:
def transpose(mat):
    return [list(x) for x in zip(*mat)]

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()))

mat = [[[-1]*64 for _ in range(n)] for _ in range(n)]
flag=True
s2 = [[0]*2 for _ in range(n)]
u2 = [[[0]*2 for _ in range(64)] for _ in range(n)]
for i in range(n):
    s2[i][0] = s[i]
    s2[i][1] = t[i]
for i in range(n):
    for k in range(64):
        u2[i][k][0] = u[i]>> k & 1
        u2[i][k][1] = v[i]>> k & 1
ans = [[0]*n for _ in range(n)]
for k in range(64):
    mat = [[-1 for _ in range(n)] for _ in range(n)]
    for l in range(2):
        for i in range(n):
            x = u2[i][k][l]
            if s2[i][l] != x:
                for j in range(n):
                    if mat[i][j] != -1 and mat[i][j] != x:
                        flag=False
                        break
                    else:
                        mat[i][j] = x
        mat = transpose(mat)

    for _ in range(2):
        for l in range(2):
            for i in range(n):
                x = u2[i][k][l]
                if s2[i][l] == x:
                    pending = list()
                    ok = False
                    for j in range(n):
                        if mat[i][j] == -1:
                            pending.append(j)
                        elif mat[i][j] == x:
                            ok = True
                    if ok:
                        continue
                    if len(pending) == 0:
                        flag = False
                        break
                    elif len(pending) == 1:
                        j = pending[0]
                        mat[i][j] = x
            mat = transpose(mat)

    inot = list()
    jnot = list()
    for i in range(n):
        filled = True
        for j in range(n):
            if mat[i][j] == -1:
                filled = False
        if not filled:
            inot.append(i)

    for j in range(n):
        filled = True
        for i in range(n):
            if mat[i][j] == -1:
                filled = False
        if not filled:
            jnot.append(j)

    for i in range(len(inot)):
        for j in range(len(jnot)):
            mat[inot[i]][jnot[j]] = (i+j) %2




    # add to ans
    if flag:
        for i in range(n):
            for j in range(n):
                    ans[i][j]+=mat[i][j]<<k
    else:
        print(-1)
        break
else:
    for i in range(n):
        print(*ans[i])

Submission status: Time Limit Exceeded

Solution code:
def transpose(mat):
    return [list(x) for x in zip(*mat)]

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()))

mat = [[[-1]*64 for _ in range(n)] for _ in range(n)]
flag=True
s2 = [[0]*2 for _ in range(n)]
u2 = [[0]*2 for _ in range(n)]
for i in range(n):
    s2[i][0] = s[i]
    s2[i][1] = t[i]
    u2[i][0] = u[i]
    u2[i][1] = v[i]
ans = [[0]*n for _ in range(n)]
for k in range(64):
    mat = [[-1 for _ in range(n)] for _ in range(n)]
    for l in range(2):
        for i in range(n):
            x = u2[i][l] >> k & 1
            if s2[i][l] != x:
                for j in range(n):
                    if mat[i][j] != -1 and mat[i][j] != x:
                        flag=False
                        break
                    else:
                        mat[i][j] = x
        mat = transpose(mat)

    for _ in range(2):
        for l in range(2):
            for i in range(n):
                x = u2[i][l] >> k & 1
                if s2[i][l] == x:
                    pending = list()
                    ok = False
                    for j in range(n):
                        if mat[i][j] == -1:
                            pending.append(j)
                        elif mat[i][j] == x:
                            ok = True
                    if ok:
                        continue
                    if len(pending) == 0:
                        flag = False
                        break
                    elif len(pending) == 1:
                        j = pending[0]
                        mat[i][j] = x
            mat = transpose(mat)

    inot = list()
    jnot = list()
    for i in range(n):
        filled = True
        for j in range(n):
            if mat[i][j] == -1:
                filled = False
        if not filled:
            inot.append(i)

    for j in range(n):
        filled = True
        for i in range(n):
            if mat[i][j] == -1:
                filled = False
        if not filled:
            jnot.append(j)

    for i in range(len(inot)):
        for j in range(len(jnot)):
            mat[inot[i]][jnot[j]] = (i+j) %2




    # add to ans
    if flag:
        for i in range(n):
            for j in range(n):
                    ans[i][j]+=mat[i][j]<<k
    else:
        print(-1)
        break
else:
    for i in range(n):
        print(*ans[i])