結果

問題 No.2152 [Cherry Anniversary 2] 19 Petals of Cherry
コンテスト
ユーザー lam6er
提出日時 2025-04-15 21:20:56
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 693 ms / 1,000 ms
コード長 1,881 bytes
コンパイル時間 412 ms
コンパイル使用メモリ 82,156 KB
実行使用メモリ 146,392 KB
最終ジャッジ日時 2025-04-15 21:26:48
合計ジャッジ時間 15,584 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 49
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import defaultdict

def main():
    allowed = [set() for _ in range(20)]  # 1-based index for positions 1-19
    for i in range(1, 20):
        parts = list(map(int, sys.stdin.readline().split()))
        L_i = parts[0]
        if L_i > 0:
            allowed[i] = set(parts[1:1+L_i])
        else:
            allowed[i] = set()
    
    # Precompute greater_mask for each a
    greater_mask = [0] * 20  # a ranges from 1 to 19
    for a in range(1, 20):
        mask = 0
        for elem in range(a + 1, 20):
            mask |= 1 << (elem - 1)
        greater_mask[a] = mask
    
    # Initialize DP
    dp = defaultdict(lambda: [0, 0])
    dp[0] = [1, 0]  # mask 0, even count 1, odd 0
    
    for i in range(1, 20):
        next_dp = defaultdict(lambda: [0, 0])
        current_allowed = allowed[i]
        if not current_allowed:
            # No possible permutations, break early
            dp = defaultdict(lambda: [0, 0])
            break
        
        for mask, (even, odd) in dp.items():
            if even == 0 and odd == 0:
                continue
            for a in current_allowed:
                if (mask & (1 << (a - 1))) != 0:
                    continue  # a is already used
                # Compute c
                c = (mask & greater_mask[a]).bit_count()
                new_mask = mask | (1 << (a - 1))
                # Update even
                if even > 0:
                    new_p = (0 + c) % 2
                    next_dp[new_mask][new_p] += even
                # Update odd
                if odd > 0:
                    new_p = (1 + c) % 2
                    next_dp[new_mask][new_p] += odd
        
        dp = next_dp
    
    full_mask = (1 << 19) - 1
    X_even = dp.get(full_mask, [0, 0])[0]
    X_odd = dp.get(full_mask, [0, 0])[1]
    print(X_even, X_odd)

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