結果

問題 No.1056 2D Lamps
コンテスト
ユーザー maspy
提出日時 2020-05-16 10:32:51
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 14
権限があれば一括ダウンロードができます

ソースコード

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