結果

問題 No.1056 2D Lamps
ユーザー maspymaspy
提出日時 2020-05-16 10:32:51
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
AC  
実行時間 592 ms / 3,000 ms
コード長 887 bytes
コンパイル時間 557 ms
コンパイル使用メモリ 12,044 KB
実行使用メモリ 127,348 KB
最終ジャッジ日時 2023-10-22 00:46:25
合計ジャッジ時間 15,839 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 391 ms
42,664 KB
testcase_01 AC 400 ms
42,664 KB
testcase_02 AC 407 ms
42,616 KB
testcase_03 AC 592 ms
127,176 KB
testcase_04 AC 592 ms
127,144 KB
testcase_05 AC 568 ms
127,348 KB
testcase_06 AC 548 ms
127,144 KB
testcase_07 AC 549 ms
127,152 KB
testcase_08 AC 550 ms
127,212 KB
testcase_09 AC 506 ms
127,136 KB
testcase_10 AC 512 ms
127,136 KB
testcase_11 AC 542 ms
127,332 KB
testcase_12 AC 549 ms
127,136 KB
testcase_13 AC 407 ms
43,312 KB
testcase_14 AC 422 ms
46,260 KB
testcase_15 AC 412 ms
46,656 KB
testcase_16 AC 423 ms
46,396 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