結果

問題 No.911 ラッキーソート
コンテスト
ユーザー lam6er
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

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()
0