結果

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

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    idx = 0
    N = int(data[idx])
    idx += 1
    M = int(data[idx])
    idx += 1
    
    grids = []
    for _ in range(M):
        grid = []
        for _ in range(N):
            line = data[idx]
            idx += 1
            grid.append(line)
        vec = 0
        for i in range(N):
            for j in range(N):
                if grid[i][j] == '#':
                    idx_bit = i * N + j
                    vec |= (1 << idx_bit)
        grids.append(vec)
    
    operation_masks = []
    
    # Rows
    for k in range(N):
        mask = 0
        for j in range(N):
            idx_bit = k * N + j
            mask |= (1 << idx_bit)
        operation_masks.append(mask)
    
    # Columns
    for k in range(N):
        mask = 0
        for i in range(N):
            idx_bit = i * N + k
            mask |= (1 << idx_bit)
        operation_masks.append(mask)
    
    # Diagonals i + j = d (d ranges from 0 to 2N-2)
    for d in range(2 * N - 1):
        mask = 0
        for i in range(N):
            j = d - i
            if 0 <= j < N:
                idx_bit = i * N + j
                mask |= (1 << idx_bit)
        if mask != 0:
            operation_masks.append(mask)
    
    # Anti-diagonals i - j = d (d ranges from -(N-1) to N-1)
    for d in range(-(N-1), N):
        mask = 0
        for i in range(N):
            j = i - d
            if 0 <= j < N:
                idx_bit = i * N + j
                mask |= (1 << idx_bit)
        if mask != 0:
            operation_masks.append(mask)
    
    # Gaussian elimination to find the basis
    basis = {}
    for mask in operation_masks:
        current = mask
        if current == 0:
            continue
        while True:
            pivot = current.bit_length() - 1
            if pivot in basis:
                current ^= basis[pivot]
                if current == 0:
                    break
            else:
                basis[pivot] = current
                break
    
    # Prepare the basis pivots in sorted order for checking
    pivots = sorted(basis.keys(), reverse=True)
    
    # Prepare the output
    output = []
    for i in range(M):
        for j in range(i + 1, M):
            D = grids[j] ^ grids[i]
            temp = D
            for pivot in pivots:
                if (temp >> pivot) & 1:
                    temp ^= basis[pivot]
            if temp == 0:
                output.append('1')
            else:
                output.append('0')
    
    # Print the output in the required format
    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