結果

問題 No.2152 [Cherry Anniversary 2] 19 Petals of Cherry
コンテスト
ユーザー lam6er
提出日時 2025-03-31 17:18:22
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,971 bytes
コンパイル時間 143 ms
コンパイル使用メモリ 82,712 KB
実行使用メモリ 183,644 KB
最終ジャッジ日時 2025-03-31 17:19:11
合計ジャッジ時間 29,454 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 40 TLE * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import defaultdict

def main():
    candidates = []
    for _ in range(19):
        parts = list(map(int, sys.stdin.readline().split()))
        if not parts:
            candidates.append([])
            continue
        L = parts[0]
        if L == 0:
            candidates.append([])
        else:
            candidates.append(parts[1:1+L])
    
    for cs in candidates:
        if not cs:
            print(0, 0)
            return
    
    prev_even = defaultdict(int)
    prev_even[0] = 1
    prev_odd = defaultdict(int)
    
    for step in range(19):
        cs = candidates[step]
        curr_even = defaultdict(int)
        curr_odd = defaultdict(int)
        
        for mask, cnt_even in prev_even.items():
            for k in cs:
                if not (mask & (1 << (k - 1))):
                    new_mask = mask | (1 << (k - 1))
                    shifted = mask >> k
                    cnt = shifted.bit_count()
                    new_parity = (cnt % 2)
                    if new_parity == 0:
                        curr_even[new_mask] += cnt_even
                    else:
                        curr_odd[new_mask] += cnt_even
        
        for mask, cnt_odd in prev_odd.items():
            for k in cs:
                if not (mask & (1 << (k - 1))):
                    new_mask = mask | (1 << (k - 1))
                    shifted = mask >> k
                    cnt = shifted.bit_count()
                    new_parity = (cnt % 2) ^ 1
                    if new_parity == 0:
                        curr_even[new_mask] += cnt_odd
                    else:
                        curr_odd[new_mask] += cnt_odd
        
        prev_even, prev_odd = curr_even, curr_odd
        if not prev_even and not prev_odd:
            break
    
    full_mask = (1 << 19) - 1
    X_even = prev_even.get(full_mask, 0)
    X_odd = prev_odd.get(full_mask, 0)
    print(X_even, X_odd)

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