結果

問題 No.460 裏表ちわーわ
コンテスト
ユーザー lam6er
提出日時 2025-03-20 21:19:02
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 579 ms / 2,000 ms
コード長 3,012 bytes
コンパイル時間 355 ms
コンパイル使用メモリ 82,724 KB
実行使用メモリ 76,872 KB
最終ジャッジ日時 2025-03-20 21:20:11
合計ジャッジ時間 7,953 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def main():
    M, N = map(int, sys.stdin.readline().split())
    a = []
    for _ in range(M):
        a.append(list(map(int, sys.stdin.readline().split())))
    
    # マス(i,j)を一列のインデックスに対応させる: idx = i*N + j
    total = M * N
    matrix = []
    target = []
    for i in range(M):
        for j in range(N):
            row = 0
            rhs = a[i][j]
            for di in (-1, 0, 1):
                for dj in (-1, 0, 1):
                    ni, nj = i + di, j + dj
                    if 0 <= ni < M and 0 <= nj < N:
                        k = ni * N + nj
                        row |= 1 << k
            matrix.append(row)
            target.append(rhs)
    
    # GF(2)でのガウスの消去法
    pivot_row = [-1] * total
    rank = 0
    for col in reversed(range(total)):  # 右から左に処理するように変更
        # Find the pivot row
        pivot = -1
        for r in range(rank, total):
            if (matrix[r] >> col) & 1:
                pivot = r
                break
        if pivot == -1:
            continue
        # Swap with the rank row
        matrix[rank], matrix[pivot] = matrix[pivot], matrix[rank]
        target[rank], target[pivot] = target[pivot], target[rank]
        # Record the pivot row for this column
        pivot_row[col] = rank
        # Eliminate this column in other rows
        for r in range(total):
            if r != rank and ((matrix[r] >> col) & 1):
                matrix[r] ^= matrix[rank]
                target[r] ^= target[rank]
        rank += 1
    
    # Check for inconsistency
    for r in range(rank, total):
        if target[r]:
            print("Impossible")
            return
    
    # Collect free variables
    free = []
    for col in range(total):
        if pivot_row[col] == -1:
            free.append(col)
    
    # Generate all possible values for free variables and compute the minimal flips
    min_flips = float('inf')
    for mask in range(0, 1 << len(free)):
        x = [0] * total
        # Set free variables
        for i in range(len(free)):
            if (mask >> i) & 1:
                x[free[i]] = 1
        
        # Process pivot columns from right to left
        pivot_cols = [col for col in range(total) if pivot_row[col] != -1]
        pivot_cols.sort(reverse=True)
        
        for col in pivot_cols:
            row = pivot_row[col]
            bits = matrix[row]
            rhs = target[row]
            # Calculate the sum from other columns
            sum_val = rhs
            for c in range(total):
                if c == col:
                    continue
                if (bits >> c) & 1:
                    sum_val ^= x[c]
            x[col] = sum_val
        
        # Count the number of flips
        flips = sum(x)
        if flips < min_flips:
            min_flips = flips
    
    if min_flips == float('inf'):
        print("Impossible")
    else:
        print(min_flips)

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