結果
問題 |
No.2152 [Cherry Anniversary 2] 19 Petals of Cherry
|
ユーザー |
![]() |
提出日時 | 2025-04-16 15:26:35 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 717 ms / 1,000 ms |
コード長 | 1,881 bytes |
コンパイル時間 | 466 ms |
コンパイル使用メモリ | 81,820 KB |
実行使用メモリ | 146,136 KB |
最終ジャッジ日時 | 2025-04-16 15:28:44 |
合計ジャッジ時間 | 16,015 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 49 |
ソースコード
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()