Submission #12399911


Source Code Expand

Copy
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 Info

Submission Time
Task F - I hate Matrix Construction
User maspy
Language Python (3.8.2)
Score 600
Code Size 3375 Byte
Status AC
Exec Time 421 ms
Memory 54116 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status
AC × 2
AC × 49
Set Name Test Cases
Sample sample1.txt, sample2.txt
All anti-beet1.txt, anti-beet2.txt, anti-beet3.txt, anti-beet4.txt, anti-beet5.txt, anti-beet6.txt, anti-beet7.txt, anti-beet8.txt, anti_beet_alpha.txt, anti_beet_beta.txt, anti_beet_delta.txt, anti_beet_theta.txt, brute1.txt, brute2.txt, brute3.txt, brute4.txt, brute5.txt, brute6.txt, brute7.txt, brute8.txt, brute9.txt, ng3.txt, random1.txt, random2.txt, sample1.txt, sample2.txt, test0.txt, test1.txt, test10.txt, test11_.txt, test12_.txt, test13_.txt, test14.txt, test15.txt, test16.txt, test17_.txt, test18_.txt, test19_.txt, test2.txt, test20_.txt, test21_.txt, test22_.txt, test3.txt, test4.txt, test5.txt, test6.txt, test7.txt, test8.txt, test9.txt
Case Name Status Exec Time Memory
anti-beet1.txt AC 400 ms 53664 KB
anti-beet2.txt AC 377 ms 53708 KB
anti-beet3.txt AC 382 ms 53576 KB
anti-beet4.txt AC 384 ms 53500 KB
anti-beet5.txt AC 391 ms 53700 KB
anti-beet6.txt AC 421 ms 53808 KB
anti-beet7.txt AC 376 ms 53508 KB
anti-beet8.txt AC 412 ms 53700 KB
anti_beet_alpha.txt AC 411 ms 53808 KB
anti_beet_beta.txt AC 413 ms 53832 KB
anti_beet_delta.txt AC 416 ms 53752 KB
anti_beet_theta.txt AC 415 ms 53920 KB
brute1.txt AC 102 ms 26788 KB
brute2.txt AC 104 ms 27004 KB
brute3.txt AC 100 ms 27060 KB
brute4.txt AC 106 ms 27396 KB
brute5.txt AC 103 ms 27060 KB
brute6.txt AC 103 ms 26808 KB
brute7.txt AC 101 ms 26964 KB
brute8.txt AC 107 ms 27016 KB
brute9.txt AC 103 ms 26808 KB
ng3.txt AC 184 ms 33472 KB
random1.txt AC 389 ms 54004 KB
random2.txt AC 395 ms 53828 KB
sample1.txt AC 104 ms 27052 KB
sample2.txt AC 105 ms 27320 KB
test0.txt AC 101 ms 27068 KB
test1.txt AC 113 ms 27784 KB
test10.txt AC 351 ms 53860 KB
test11_.txt AC 337 ms 53656 KB
test12_.txt AC 356 ms 53704 KB
test13_.txt AC 348 ms 53512 KB
test14.txt AC 101 ms 26800 KB
test15.txt AC 142 ms 30932 KB
test16.txt AC 147 ms 30932 KB
test17_.txt AC 347 ms 53832 KB
test18_.txt AC 343 ms 53436 KB
test19_.txt AC 355 ms 53972 KB
test2.txt AC 114 ms 27788 KB
test20_.txt AC 340 ms 54116 KB
test21_.txt AC 344 ms 53760 KB
test22_.txt AC 355 ms 53676 KB
test3.txt AC 144 ms 31788 KB
test4.txt AC 346 ms 53948 KB
test5.txt AC 350 ms 53868 KB
test6.txt AC 350 ms 53608 KB
test7.txt AC 354 ms 54064 KB
test8.txt AC 340 ms 53868 KB
test9.txt AC 346 ms 53700 KB