結果

問題 No.2236 Lights Out On Simple Graph
ユーザー gew1fw
提出日時 2025-06-12 18:23:55
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,799 bytes
コンパイル時間 210 ms
コンパイル使用メモリ 82,276 KB
実行使用メモリ 76,464 KB
最終ジャッジ日時 2025-06-12 18:24:15
合計ジャッジ時間 9,185 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 32 WA * 1 TLE * 1 -- * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx])
    idx += 1
    M = int(input[idx])
    idx += 1
    edges = []
    for _ in range(M):
        a = int(input[idx]) - 1  # convert to 0-based
        idx += 1
        b = int(input[idx]) - 1
        idx += 1
        edges.append((a, b))
    c = list(map(int, input[idx:idx+N]))
    idx += N

    # Check sum of c is even
    if sum(c) % 2 != 0:
        print(-1)
        return

    # Build augmented matrix
    augmented = []
    for i in range(N):
        row = 0
        for j in range(M):
            a, b = edges[j]
            if i == a or i == b:
                row |= (1 << j)
        # Add target (c[i])
        row |= (c[i] << M)
        augmented.append(row)

    # Perform Gaussian elimination over GF(2)
    pivots = []  # list of (pivot_col, mask, target)
    rank = 0
    for col in range(M):
        # Find pivot row
        pivot_row = -1
        for r in range(rank, N):
            if (augmented[r] >> col) & 1:
                pivot_row = r
                break
        if pivot_row == -1:
            continue  # free variable
        # Swap with the current rank row
        augmented[rank], augmented[pivot_row] = augmented[pivot_row], augmented[rank]
        # Eliminate this column in other rows
        for r in range(N):
            if r != rank and ((augmented[r] >> col) & 1):
                augmented[r] ^= augmented[rank]
        # Record the pivot
        row_val = augmented[rank]
        # Compute mask: variables to the right of col
        mask = row_val & ((1 << M) - 1)
        mask &= ~((1 << (col + 1)) - 1)  # clear all bits up to and including col
        target = (row_val >> M) & 1
        pivots.append((col, mask, target))
        rank += 1

    # Check for inconsistency
    inconsistent = False
    for r in range(rank, N):
        if (augmented[r] >> M) & 1:
            # Check if variables part is all 0
            if (augmented[r] & ((1 << M) - 1)) == 0:
                inconsistent = True
                break
    if inconsistent:
        print(-1)
        return

    # Collect free variables (columns not in pivots)
    pivot_cols = {p[0] for p in pivots}
    free_vars = [col for col in range(M) if col not in pivot_cols]
    num_free = len(free_vars)
    if num_free > 20:
        print(-1)
        return

    # Generate all possible combinations of free variables
    from itertools import product
    min_ops = float('inf')
    for bits in product([0, 1], repeat=num_free):
        solution = 0
        # Set free variables
        for i in range(num_free):
            if bits[i]:
                solution |= (1 << free_vars[i])
        # Process pivots in reverse order
        for p in reversed(pivots):
            col, mask, target = p
            # Compute sum of variables in mask (to the right of col)
            sum_val = ( (solution & mask).bit_count() ) % 2
            # x_col = sum_val ^ target
            x_col = sum_val ^ target
            if x_col:
                solution |= (1 << col)
            else:
                solution &= ~ (1 << col)
        # Check if this solution satisfies all equations
        valid = True
        for r in range(N):
            lhs = 0
            for j in range(M):
                if (solution >> j) & 1:
                    a, b = edges[j]
                    if r == a or r == b:
                        lhs ^= 1
            expected = c[r]
            if lhs != expected:
                valid = False
                break
        if valid:
            count = bin(solution).count('1')
            if count < min_ops:
                min_ops = count

    if min_ops == float('inf'):
        print(-1)
    else:
        print(min_ops)

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