結果

問題 No.1056 2D Lamps
ユーザー gew1fw
提出日時 2025-06-12 19:25:05
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,777 bytes
コンパイル時間 184 ms
コンパイル使用メモリ 82,840 KB
実行使用メモリ 53,616 KB
最終ジャッジ日時 2025-06-12 19:25:15
合計ジャッジ時間 6,052 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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
    configs = []
    for _ in range(M):
        mat = []
        for _ in range(N):
            row = input[idx]
            idx += 1
            mat.append(row)
        # Convert to bitmask
        bitmask = 0
        for i in range(N):
            for j in range(N):
                if mat[i][j] == '#':
                    pos = i * N + j
                    bitmask |= (1 << pos)
        configs.append(bitmask)

    # Precompute all line flip vectors
    line_flips = []

    # Rows
    for i in range(N):
        vec = 0
        for j in range(N):
            pos = i * N + j
            vec |= (1 << pos)
        line_flips.append(vec)

    # Columns
    for j in range(N):
        vec = 0
        for i in range(N):
            pos = i * N + j
            vec |= (1 << pos)
        line_flips.append(vec)

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

    # Anti-diagonals (i - j = t, t from -(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)
        line_flips.append(vec)

    # Gaussian elimination to find basis
    basis = []
    for vec in line_flips:
        v = vec
        for (pivot, b) in basis:
            if (v >> pivot) & 1:
                v ^= b
        if v != 0:
            # Find the first set bit
            pivot = 0
            while (v >> pivot) & 1 == 0:
                pivot += 1
            # Insert into basis in order
            insert_pos = 0
            while insert_pos < len(basis) and basis[insert_pos][0] < pivot:
                insert_pos += 1
            basis.insert(insert_pos, (pivot, v))

    # Function to check if a vector is in the row space
    def is_in_span(vec):
        v = vec
        for (pivot, b) in basis:
            if (v >> pivot) & 1:
                v ^= b
        return v == 0

    # Prepare the output
    output = []
    for i in range(M):
        for j in range(i + 1, M):
            D = configs[i] ^ configs[j]
            if is_in_span(D):
                output.append('1')
            else:
                output.append('0')

    # Print the output
    count = 0
    for i in range(M - 1):
        line = output[count : count + (M - 1 - i)]
        print(''.join(line))
        count += (M - 1 - i)

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