結果
問題 |
No.1669 パズル作成
|
ユーザー |
![]() |
提出日時 | 2025-06-12 21:42:26 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,443 bytes |
コンパイル時間 | 180 ms |
コンパイル使用メモリ | 81,660 KB |
実行使用メモリ | 78,240 KB |
最終ジャッジ日時 | 2025-06-12 21:46:17 |
合計ジャッジ時間 | 4,586 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 2 WA * 2 TLE * 1 -- * 24 |
ソースコード
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()