結果

問題 No.1669 パズル作成
コンテスト
ユーザー qwewe
提出日時 2025-04-24 12:23:18
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,897 bytes
コンパイル時間 239 ms
コンパイル使用メモリ 82,340 KB
実行使用メモリ 84,888 KB
最終ジャッジ日時 2025-04-24 12:25:06
合計ジャッジ時間 3,967 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other TLE * 1 -- * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def main():
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx]); idx += 1
    M = int(input[idx]); idx += 1
    black = set()
    for _ in range(M):
        r = int(input[idx]) - 1
        c = int(input[idx + 1]) - 1
        black.add((r, c))
        idx += 2

    min_x = N * N  # Initialize with maximum possible X

    # Precompute T matrix: T[i][j] = 1 if (i,j) is white, else 0
    # Instead of a full matrix, use a function to check on the fly
    def is_black(i, j):
        return (i, j) in black

    # Try each column j as the base column
    for j in range(N):
        for c_j in [0, 1]:
            # Determine R[i] based on column j and c_j
            R = [0] * N
            for i in range(N):
                T_ij = 0 if is_black(i, j) else 1
                R[i] = T_ij ^ c_j

            # Determine C[k] for other columns
            C = [0] * N
            C[j] = c_j  # Fixed base column

            for k in range(N):
                if k == j:
                    continue
                cnt0 = 0
                cnt1 = 0
                for i in range(N):
                    T_ik = 0 if is_black(i, k) else 1
                    expected_c = R[i] ^ T_ik
                    if expected_c == 0:
                        cnt0 += 1
                    else:
                        cnt1 += 1
                if cnt0 >= cnt1:
                    C[k] = 0
                else:
                    C[k] = 1

            # Calculate the number of valid cells
            valid = 0
            for i in range(N):
                for k in range(N):
                    T_ik = 0 if is_black(i, k) else 1
                    if (R[i] ^ C[k]) == T_ik:
                        valid += 1
            current_x = N * N - valid
            if current_x < min_x:
                min_x = current_x

    print(min_x)

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