結果

問題 No.1056 2D Lamps
ユーザー gew1fw
提出日時 2025-06-12 14:26:43
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,543 bytes
コンパイル時間 428 ms
コンパイル使用メモリ 82,568 KB
実行使用メモリ 125,220 KB
最終ジャッジ日時 2025-06-12 14:27:03
合計ジャッジ時間 5,909 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other TLE * 1 -- * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0

    N = int(input[idx])
    idx += 1
    M = int(input[idx])
    idx += 1

    # Read M configurations
    configurations = []
    for _ in range(M):
        vec = 0
        for i in range(N):
            line = input[idx]
            idx += 1
            for j in range(N):
                if line[j] == '#':
                    pos = i * N + j
                    vec |= (1 << pos)
        configurations.append(vec)

    # Generate all operation vectors
    op_vectors = []

    # Rows
    for k in range(1, N + 1):
        vec = 0
        for j in range(N):
            pos = (k - 1) * N + j
            vec |= (1 << pos)
        op_vectors.append(vec)

    # Columns
    for k in range(1, N + 1):
        vec = 0
        for i in range(N):
            pos = i * N + (k - 1)
            vec |= (1 << pos)
        op_vectors.append(vec)

    # Diagonals i + j = s, for s in 0..2N-2
    for s in range(0, 2 * N - 1):
        vec = 0
        for i in range(N):
            j = s - i
            if 0 <= j < N:
                pos = i * N + j
                vec |= (1 << pos)
        op_vectors.append(vec)

    # Anti-diagonals j - i = t, for t in -(N-1) to N-1
    for t in range(-(N - 1), N):
        vec = 0
        for i in range(N):
            j = i + t
            if 0 <= j < N:
                pos = i * N + j
                vec |= (1 << pos)
        op_vectors.append(vec)

    # Perform Gaussian elimination to find the basis
    basis = {}
    for vec in op_vectors:
        current = vec
        while True:
            if current == 0:
                break
            highest_bit = current.bit_length() - 1
            if highest_bit not in basis:
                basis[highest_bit] = current
                break
            else:
                current ^= basis[highest_bit]

    # Sort basis keys in descending order
    basis_keys = sorted(basis.keys(), reverse=True)

    # Prepare the result
    result = []
    for i in range(M - 1):
        line = []
        for j in range(i + 1, M):
            D = configurations[i] ^ configurations[j]
            current = D
            for bit in basis_keys:
                if (current >> bit) & 1:
                    current ^= basis[bit]
            if current == 0:
                line.append('1')
            else:
                line.append('0')
        result.append(''.join(line))

    # Print the result
    for line in result:
        print(line)

if __name__ == "__main__":
    main()
0