結果
問題 |
No.2152 [Cherry Anniversary 2] 19 Petals of Cherry
|
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
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()