結果

問題 No.1056 2D Lamps
ユーザー maspymaspy
提出日時 2020-05-16 10:32:51
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
AC  
実行時間 698 ms / 3,000 ms
コード長 887 bytes
コンパイル時間 234 ms
コンパイル使用メモリ 12,672 KB
実行使用メモリ 128,216 KB
最終ジャッジ日時 2024-09-22 02:09:16
合計ジャッジ時間 14,156 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 483 ms
44,128 KB
testcase_01 AC 478 ms
44,256 KB
testcase_02 AC 477 ms
44,016 KB
testcase_03 AC 698 ms
128,064 KB
testcase_04 AC 665 ms
127,960 KB
testcase_05 AC 660 ms
128,216 KB
testcase_06 AC 644 ms
127,956 KB
testcase_07 AC 632 ms
128,132 KB
testcase_08 AC 633 ms
127,720 KB
testcase_09 AC 595 ms
127,956 KB
testcase_10 AC 587 ms
127,708 KB
testcase_11 AC 615 ms
127,636 KB
testcase_12 AC 634 ms
127,948 KB
testcase_13 AC 470 ms
44,256 KB
testcase_14 AC 490 ms
47,700 KB
testcase_15 AC 494 ms
47,396 KB
testcase_16 AC 489 ms
47,580 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, M = map(int, readline().split())

if N > 3:
    filter = np.random.randint(0, 10**18, (N - 3, N - 3), dtype=np.uint64)

def compute_hash(A):
    if A.shape[0] <= 3:
        return np.zeros(A.shape[2], np.uint64)
    A = A == b'#'
    # 2x2ごとの集計を並べる
    A = A[:-1] ^ A[1:]
    A = A[:, :-1] ^ A[:, 1:]
    # ななめに2x2
    A = A[1:, :-1] ^ A[:-1, 1:]
    A = A[:-1, :-1] ^ A[1:, 1:]
    return np.sum(A * filter[:, :, None], axis=(0, 1))

A = np.empty((N * N + N + 1) * M, 'S1')
A[:-1] = np.frombuffer(read(), 'S1')

A = A.reshape(M, -1)[:, :-1].reshape(M, N, -1)[:, :, :-1]

H = compute_hash(A.T)
ok = (np.equal.outer(H, H) * 1).astype(str)

answers = (''.join(ok[i, i + 1:]) for i in range(M - 1))
print('\n'.join(answers))
0