結果

問題 No.1056 2D Lamps
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 16:57:29
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,930 bytes
コンパイル時間 366 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 282,696 KB
最終ジャッジ日時 2025-06-12 16:57:36
合計ジャッジ時間 6,797 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 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
    
    boards = []
    for _ in range(m):
        board = []
        for _ in range(n):
            row = data[idx]
            idx +=1
            board.append(row)
        boards.append(board)
    
    size_x = n
    size_y = n
    size_a = 2*n -1
    size_b = 2*n -1
    total_vars = size_x + size_y + size_a + size_b
    
    def get_col(var_type, k, n):
        if var_type == 'x':
            return k-1
        elif var_type == 'y':
            return n + (k-1)
        elif var_type == 'a':
            return 2*n + (k-2)
        elif var_type == 'b':
            return 2*n + (2*n-1) + (k + (n-1))
        else:
            return -1
    
    def gaussian_elimination(equations, n_vars):
        rank =0
        for col in reversed(range(n_vars)):
            pivot = -1
            for i in range(rank, len(equations)):
                if (equations[i][0] >> col) &1:
                    pivot = i
                    break
            if pivot == -1:
                continue
            equations[rank], equations[pivot] = equations[pivot], equations[rank]
            for i in range(len(equations)):
                if i != rank and ( (equations[i][0] >> col) &1 ):
                    equations[i] = ( equations[i][0] ^ equations[rank][0], equations[i][1] ^ equations[rank][1] )
            rank +=1
        for a, b in equations:
            if a ==0 and b !=0:
                return False
        return True
    
    output = []
    for i in range(m):
        for j in range(i+1, m):
            d = []
            for x in range(n):
                row = []
                for y in range(n):
                    a = boards[i][x][y]
                    b = boards[j][x][y]
                    row.append(1 if a != b else 0)
                d.append(row)
            equations = []
            for x in range(1, n+1):
                for y in range(1, n+1):
                    x_index = get_col('x', x, n)
                    y_index = get_col('y', y, n)
                    a_index = get_col('a', x + y, n)
                    b_index = get_col('b', x - y, n)
                    row_mask = 0
                    for idx_var in [x_index, y_index, a_index, b_index]:
                        row_mask |= (1 << idx_var)
                    rhs = d[x-1][y-1]
                    equations.append( (row_mask, rhs) )
            if gaussian_elimination(equations, total_vars):
                output.append('1')
            else:
                output.append('0')
    
    res = []
    k = 0
    for i in range(m-1):
        line = []
        for j in range(i+1, m):
            line.append(output[k])
            k +=1
        res.append(''.join(line))
    
    for line in res:
        print(line)
    print()

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