結果

問題 No.2152 [Cherry Anniversary 2] 19 Petals of Cherry
ユーザー lam6er
提出日時 2025-04-16 15:25:10
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 775 ms / 1,000 ms
コード長 2,081 bytes
コンパイル時間 471 ms
コンパイル使用メモリ 81,340 KB
実行使用メモリ 176,384 KB
最終ジャッジ日時 2025-04-16 15:26:06
合計ジャッジ時間 18,334 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 49
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import defaultdict

def main():
    # Read input
    A = []
    for _ in range(19):
        parts = list(map(int, sys.stdin.readline().split()))
        L_i = parts[0]
        A_i = parts[1:] if L_i > 0 else []
        A.append(A_i)
    
    # Precompute mask_gt for x from 1 to 19
    mask_gt = [0] * 20  # x ranges from 1 to 19
    for x in range(1, 20):
        mask_gt[x] = ((1 << 19) - 1) ^ ((1 << x) - 1)
    
    # Initialize DP with a dictionary to track active masks and their even/odd counts
    prev = {0: (1, 0)}  # mask: (even_count, odd_count)
    
    for step in range(19):
        current_A = A[step]
        if not current_A:
            prev = {}
            break
        curr = defaultdict(lambda: [0, 0])  # key: mask, value: [even, odd]
        for mask in prev:
            even_prev, odd_prev = prev[mask]
            for x in current_A:
                if (mask & (1 << (x - 1))) != 0:
                    continue  # x is already used
                mg = mask_gt[x]
                k = (mask & mg).bit_count()
                new_mask = mask | (1 << (x - 1))
                # Process even_prev
                if even_prev > 0:
                    new_parity = (0 + k) % 2
                    if new_parity == 0:
                        curr[new_mask][0] += even_prev
                    else:
                        curr[new_mask][1] += even_prev
                # Process odd_prev
                if odd_prev > 0:
                    new_parity = (1 + k) % 2
                    if new_parity == 0:
                        curr[new_mask][0] += odd_prev
                    else:
                        curr[new_mask][1] += odd_prev
        # Update prev to curr, filtering out masks with zero counts
        new_prev = {}
        for m in curr:
            even, odd = curr[m]
            if even + odd > 0:
                new_prev[m] = (even, odd)
        prev = new_prev
    
    full_mask = (1 << 19) - 1
    X_even, X_odd = prev.get(full_mask, (0, 0))
    print(X_even, X_odd)

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