Submission #12396150


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 >= np.count_nonzero(all_zero_row) - 1:
            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 >= np.count_nonzero(all_one_row) - 1:
            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, V >> k) << k

if not test(S, T, U, V, A):
    print(-1)
else:
    print(A)

Submission Info

Submission Time
Task F - I hate Matrix Construction
User maspy
Language Python (3.8.2)
Score 0
Code Size 3315 Byte
Status
Exec Time 180 ms
Memory 33228 KB

Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample1.txt, sample2.txt
All 0 / 600 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 147 ms 33084 KB
anti-beet2.txt 160 ms 32916 KB
anti-beet3.txt 167 ms 33176 KB
anti-beet4.txt 146 ms 33152 KB
anti-beet5.txt 149 ms 33100 KB
anti-beet6.txt 142 ms 31100 KB
anti-beet7.txt 149 ms 30956 KB
anti-beet8.txt 179 ms 33064 KB
anti_beet_alpha.txt 147 ms 31012 KB
anti_beet_beta.txt 164 ms 32856 KB
anti_beet_delta.txt 154 ms 33008 KB
anti_beet_theta.txt 180 ms 33084 KB
brute1.txt 108 ms 26752 KB
brute2.txt 107 ms 26864 KB
brute3.txt 112 ms 26964 KB
brute4.txt 109 ms 27040 KB
brute5.txt 107 ms 26980 KB
brute6.txt 110 ms 26932 KB
brute7.txt 108 ms 26888 KB
brute8.txt 105 ms 26992 KB
brute9.txt 110 ms 26868 KB
ng3.txt 163 ms 33076 KB
random1.txt 165 ms 33076 KB
random2.txt 165 ms 33228 KB
sample1.txt 108 ms 26644 KB
sample2.txt 107 ms 26980 KB
test0.txt 107 ms 27032 KB
test1.txt 107 ms 27232 KB
test10.txt 144 ms 31064 KB
test11_.txt 143 ms 30936 KB
test12_.txt 146 ms 33104 KB
test13_.txt 147 ms 32796 KB
test14.txt 103 ms 26840 KB
test15.txt 147 ms 31264 KB
test16.txt 141 ms 30932 KB
test17_.txt 147 ms 31352 KB
test18_.txt 145 ms 32924 KB
test19_.txt 143 ms 31308 KB
test2.txt 107 ms 27304 KB
test20_.txt 148 ms 33004 KB
test21_.txt 144 ms 31156 KB
test22_.txt 151 ms 33132 KB
test3.txt 115 ms 28164 KB
test4.txt 150 ms 33068 KB
test5.txt 145 ms 30972 KB
test6.txt 145 ms 31228 KB
test7.txt 145 ms 31164 KB
test8.txt 145 ms 31048 KB
test9.txt 148 ms 33216 KB