結果

問題 No.911 ラッキーソート
コンテスト
ユーザー lam6er
提出日時 2025-04-16 16:26:07
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,436 bytes
コンパイル時間 470 ms
コンパイル使用メモリ 81,608 KB
実行使用メモリ 96,232 KB
最終ジャッジ日時 2025-04-16 16:28:05
合計ジャッジ時間 4,884 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other TLE * 1 -- * 45
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from functools import lru_cache

def main():
    N, L, R = map(int, sys.stdin.readline().split())
    A = list(map(int, sys.stdin.readline().split()))
    if N == 1:
        print(max(0, R - L + 1))
        return
    
    constraints = {}
    for i in range(N-1):
        a = A[i]
        b = A[i+1]
        c = a ^ b
        if c == 0:
            print(0)
            return
        k = c.bit_length() - 1
        while (c >> k) == 0:
            k -= 1
        if a < b:
            required_bit = 0
        else:
            required_bit = 1
        if k in constraints:
            if constraints[k] != required_bit:
                print(0)
                return
        else:
            constraints[k] = required_bit
    
    fixed_val = 0
    fixed_mask = 0
    for bit in constraints:
        val = constraints[bit]
        fixed_mask |= (1 << bit)
        fixed_val |= (val << bit)
    
    allowed_mask = (~fixed_mask) & ((1 << 61) - 1)
    
    if fixed_val > R:
        print(0)
        return
    
    lower = max(0, L - fixed_val)
    upper = R - fixed_val
    
    if lower > upper:
        print(0)
        return
    
    @lru_cache(maxsize=None)
    def count_subset_le(max_var, allowed_bits):
        def dp(bit, is_less):
            if bit < 0:
                return 1
            current_bit_mask = 1 << bit
            max_bit = (max_var >> bit) & 1
            allowed = (allowed_bits & current_bit_mask) != 0
            res = 0
            
            if allowed:
                if is_less:
                    res += dp(bit-1, True)
                else:
                    if 1 <= max_bit:
                        new_is_less = (1 < max_bit)
                        res += dp(bit-1, new_is_less)
                if is_less:
                    res += dp(bit-1, True)
                else:
                    new_is_less = (0 < max_bit)
                    res += dp(bit-1, new_is_less)
            else:
                if is_less:
                    res += dp(bit-1, True)
                else:
                    new_is_less = (0 < max_bit)
                    res += dp(bit-1, new_is_less)
            return res
        
        return dp(60, False)
    
    count_upper = count_subset_le(upper, allowed_mask)
    count_lower = count_subset_le(lower - 1, allowed_mask) if lower > 0 else 0
    total = count_upper - count_lower
    print(total)

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