結果

問題 No.911 ラッキーソート
ユーザー lam6er
提出日時 2025-03-20 20:46:43
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,871 bytes
コンパイル時間 271 ms
コンパイル使用メモリ 82,228 KB
実行使用メモリ 113,108 KB
最終ジャッジ日時 2025-03-20 20:46:52
合計ジャッジ時間 7,978 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 15 WA * 31
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    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
    
    required = {}
    valid = True
    
    for i in range(n-1):
        a = A[i]
        b = A[i+1]
        xor = a ^ b
        highest_bit = 0
        if xor == 0:
            valid = False
            break
        highest_bit = xor.bit_length() - 1
        # Verify the actual highest bit
        temp = (1 << highest_bit)
        while (a & temp) == (b & temp) and temp > 0:
            temp >>= 1
            highest_bit -= 1
        if highest_bit < 0:
            valid = False
            break
        mask = 1 << highest_bit
        a_bit = (a & mask) != 0
        b_bit = (b & mask) != 0
        
        if a < b:
            # Original a < b requires x's highest_bit to be 0
            req = 0
        else:
            req = 1  # Must invert the highest_bit to make a^x < b^x
        
        if highest_bit in required:
            if required[highest_bit] != req:
                valid = False
                break
        else:
            required[highest_bit] = req
    
    if not valid:
        print(0)
        return
    
    mask_x = 0
    F = 0
    for bit in required:
        mask_x |= (1 << bit)
        F |= (required[bit] << bit)
    
    free_mask = (~mask_x) & ((1 << 61) - 1)
    
    # Compute a and b
    a = max(L - F, 0)
    b = min(R - F, free_mask)
    
    if a > b or F > R or (F + free_mask) < L:
        print(0)
        return
    
    def count_subset_less_eq(X, mask):
        if X < 0:
            return 0
        if mask == 0:
            return 1 if X >= 0 else 0
        
        bits = []
        for i in reversed(range(61)):
            if (mask >> i) & 1:
                bits.append(i)
        if not bits:
            return 1 if X >=0 else 0
        
        from functools import lru_cache
        @lru_cache(maxsize=None)
        def dp(pos, tight):
            if pos == len(bits):
                return 1
            current_bit = bits[pos]
            x_bit = (X >> current_bit) & 1
            res = 0
            
            # Option 0: set current_bit to 0
            new_tight = tight and (0 == x_bit)
            res += dp(pos + 1, new_tight)
            
            # Option 1: set current_bit to 1, if allowed
            if (mask & (1 << current_bit)):
                if tight:
                    if x_bit >= 1:
                        res += dp(pos +1, tight and (1 == x_bit))
                else:
                    res += dp(pos +1, False)
            return res
        
        return dp(0, True)
    
    cnt_high = count_subset_less_eq(b, free_mask)
    cnt_low = count_subset_less_eq(a - 1, free_mask)
    
    print(cnt_high - cnt_low)

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