結果

問題 No.1954 CHECKER×CHECKER(2)
コンテスト
ユーザー lam6er
提出日時 2025-03-20 20:34:02
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 88 ms / 1,000 ms
コード長 3,743 bytes
コンパイル時間 168 ms
コンパイル使用メモリ 82,228 KB
実行使用メモリ 78,052 KB
最終ジャッジ日時 2025-03-20 20:35:20
合計ジャッジ時間 2,736 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 29
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    H = int(input[idx]); idx +=1
    W = int(input[idx]); idx +=1
    
    grid = []
    for _ in range(H):
        s = input[idx].strip()
        idx +=1
        row = [1 if c == '#' else 0 for c in s]
        grid.append(row)
    
    M = int(input[idx]); idx +=1
    row_ops = []
    col_ops = []
    for _ in range(M):
        t = int(input[idx]); idx +=1
        n = int(input[idx]); idx +=1
        if t == 1:
            row_ops.append((t, n))
        else:
            col_ops.append((t, n))
    
    def is_solvable(augmented, n_vars):
        m = len(augmented)
        if m == 0:
            return True
        
        for col in range(n_vars):
            pivot = -1
            for row in range(col, m):
                if augmented[row][col] == 1:
                    pivot = row
                    break
            if pivot == -1:
                continue
            augmented[col], augmented[pivot] = augmented[pivot], augmented[col]
            
            for row in range(m):
                if row != col and augmented[row][col] == 1:
                    for c in range(col, len(augmented[row])):
                        augmented[row][c] ^= augmented[col][c]
        
        for row in range(len(augmented)):
            all_zero = True
            for c in range(n_vars):
                if augmented[row][c] != 0:
                    all_zero = False
                    break
            if all_zero and augmented[row][-1] == 1:
                return False
        return True
    
    for case in [0, 1]:
        desired = [[ ( (i + j) % 2 ) == case for j in range(W)] for i in range(H)]
        X = [[ (grid[i][j] ^ desired[i][j]) for j in range(W)] for i in range(H)]
        
        for row0 in [0, 1]:
            rf = [0] * H
            cf = [0] * W
            rf[0] = row0
            
            for j in range(W):
                cf[j] = X[0][j] ^ rf[0]
            
            valid = True
            for i in range(1, H):
                rf[i] = X[i][0] ^ cf[0]
            
            if valid:
                for i in range(H):
                    if not valid:
                        break
                    for j in range(W):
                        if (rf[i] ^ cf[j]) != X[i][j]:
                            valid = False
                            break
            
            if not valid:
                continue
            
            augmented_row = []
            for i in range(H):
                row_equation = []
                for (t, n_val) in row_ops:
                    if n_val >= (i + 1):
                        row_equation.append(1)
                    else:
                        row_equation.append(0)
                row_equation.append(rf[i])
                augmented_row.append(row_equation)
            
            variables_row = len(row_ops)
            row_possible = is_solvable(augmented_row, variables_row)
            if not row_possible:
                continue
            
            augmented_col = []
            for j in range(W):
                col_equation = []
                for (t, n_val) in col_ops:
                    if n_val >= (j + 1):
                        col_equation.append(1)
                    else:
                        col_equation.append(0)
                col_equation.append(cf[j])
                augmented_col.append(col_equation)
            
            variables_col = len(col_ops)
            col_possible = is_solvable(augmented_col, variables_col)
            
            if row_possible and col_possible:
                print("Yes")
                return
    
    print("No")

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