結果

問題 No.1669 パズル作成
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 17:07:10
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,443 bytes
コンパイル時間 362 ms
コンパイル使用メモリ 82,752 KB
実行使用メモリ 476,140 KB
最終ジャッジ日時 2025-06-12 17:07:14
合計ジャッジ時間 4,424 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 2 WA * 2 TLE * 1 -- * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def main():
    N, M = map(int, sys.stdin.readline().split())
    b = [[0 for _ in range(N)] for __ in range(N)]
    for _ in range(M):
        r, c = map(int, sys.stdin.readline().split())
        r -= 1
        c -= 1
        b[r][c] = 1

    # 情况一：先翻转行，再翻转列
    # 计算各行的净收益，翻转收益为正的行
    row_flips = [0] * N
    for r in range(N):
        k = sum(1 - b[r][c] for c in range(N))
        if 2 * k - N > 0:
            row_flips[r] = 1

    # 翻转行后的棋盘状态
    b_flip_row = [row.copy() for row in b]
    for r in range(N):
        if row_flips[r]:
            for c in range(N):
                b_flip_row[r][c] ^= 1

    # 计算各列的净收益，翻转收益为正的列
    col_flips = [0] * N
    for c in range(N):
        k = sum(1 - b_flip_row[r][c] for r in range(N))
        if 2 * k - N > 0:
            col_flips[c] = 1

    # 翻转列后的棋盘状态
    for c in range(N):
        if col_flips[c]:
            for r in range(N):
                b_flip_row[r][c] ^= 1

    # 计算情况一的X操作次数
    x_case1 = sum(1 - b_flip_row[r][c] for r in range(N) for c in range(N))

    # 情况二：先翻转列，再翻转行
    b_flip_col = [row.copy() for row in b]
    # 计算各列的净收益，翻转收益为正的列
    col_flips2 = [0] * N
    for c in range(N):
        k = sum(1 - b[r][c] for r in range(N))
        if 2 * k - N > 0:
            col_flips2[c] = 1

    for c in range(N):
        if col_flips2[c]:
            for r in range(N):
                b_flip_col[r][c] ^= 1

    # 计算各行的净收益，翻转收益为正的行
    row_flips2 = [0] * N
    for r in range(N):
        k = sum(1 - b_flip_col[r][c] for c in range(N))
        if 2 * k - N > 0:
            row_flips2[r] = 1

    for r in range(N):
        if row_flips2[r]:
            for c in range(N):
                b_flip_col[r][c] ^= 1

    x_case2 = sum(1 - b_flip_col[r][c] for r in range(N) for c in range(N))

    # 情况三：不翻转行和列
    x_case3 = sum(1 - b[r][c] for r in range(N) for c in range(N))

    # 情况四：只翻转行和列中收益为正的，但不考虑顺序
    # （这可能需要更复杂的计算，但为了节省时间，这里只比较情况一、二、三）

    # 选择最小的X操作次数
    min_x = min(x_case1, x_case2, x_case3)
    print(min_x)

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