結果

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

ソースコード

diff # 

import sys
from collections import defaultdict

def main():
    higher_bits = [0] * 20  # 1-based index for x in 1..19
    for x in range(1, 20):
        higher_bits[x] = sum(1 << (y - 1) for y in range(x + 1, 20))
    
    A = []
    for _ in range(19):
        parts = list(map(int, sys.stdin.readline().split()))
        L = parts[0]
        if L == 0:
            A.append(())
        else:
            A.append(tuple(parts[1:L+1]))
    
    prev_dp = defaultdict(lambda: [0, 0])
    prev_dp[0] = [1, 0]  # mask 0 has parity0=1, parity1=0

    for step in range(19):
        current_A = A[step]
        new_dp = defaultdict(lambda: [0, 0])
        for mask in prev_dp:
            count0, count1 = prev_dp[mask]
            if count0 == 0 and count1 == 0:
                continue
            for x in current_A:
                if (mask & (1 << (x - 1))) != 0:
                    continue
                new_mask = mask | (1 << (x - 1))
                cnt = bin(mask & higher_bits[x]).count('1')
                
                new_p0 = (cnt) % 2
                new_dp[new_mask][new_p0] += count0
                new_dp[new_mask][(new_p0 + 1) % 2] += count1
        
        prev_dp = new_dp

    final_mask = (1 << 19) - 1
    even = prev_dp.get(final_mask, [0, 0])[0]
    odd = prev_dp.get(final_mask, [0, 0])[1]
    print(even, odd)

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