結果
問題 |
No.911 ラッキーソート
|
ユーザー |
![]() |
提出日時 | 2025-03-31 17:46:16 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,123 bytes |
コンパイル時間 | 447 ms |
コンパイル使用メモリ | 82,580 KB |
実行使用メモリ | 112,708 KB |
最終ジャッジ日時 | 2025-03-31 17:46:53 |
合計ジャッジ時間 | 7,247 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 21 WA * 25 |
ソースコード
def main(): import sys N, L, R = map(int, sys.stdin.readline().split()) A = list(map(int, sys.stdin.readline().split())) constraints = {} possible = True for i in range(N-1): C = A[i] D = A[i+1] xor = C ^ D if xor == 0: possible = False break k = xor.bit_length() - 1 required_bit = 0 if C < D else 1 if k in constraints: if constraints[k] != required_bit: possible = False break else: constraints[k] = required_bit if not possible: print(0) return mask_mask = 0 value_mask = 0 for k in constraints: mask_mask |= (1 << k) value_mask |= (constraints[k] << k) if (value_mask & mask_mask) != value_mask: print(0) return def count(x): free_bits = ~mask_mask & ((1 << 61) - 1) max_v = x - value_mask if max_v < 0: return 0 bits = [] for i in range(61): if (free_bits >> i) & 1: bits.append(i) bits.sort(reverse=True) n = len(bits) from functools import lru_cache @lru_cache(maxsize=None) def dp(pos, tight): if pos == n: return 1 bit = bits[pos] bit_val = 1 << bit res = 0 current_max = (max_v >> bit) & 1 if tight else 1 for choice in [0, 1]: if choice > current_max: continue new_tight = tight and (choice == current_max) if choice == 1: if (value_mask + (1 << bit)) > x: continue res += dp(pos + 1, new_tight) else: res += dp(pos + 1, new_tight) return res return dp(0, True) answer = count(R) - count(L-1) print(max(answer, 0)) if __name__ == "__main__": main()