結果

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

ソースコード

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
    
    # Process each adjacent pair
    from collections import defaultdict
    mask_dict = defaultdict(lambda: None)
    conflict = False
    
    for i in range(N-1):
        a = A[i]
        b = A[i+1]
        if a < b:
            original_order = 'asc'
        else:
            original_order = 'desc'
        y = a ^ b
        if y == 0:
            continue  # impossible given problem constraints
        
        k = y.bit_length() - 1  # MSB position (0-based)
        
        # Determine required bit value for x at k-th position
        a_bit = (a >> k) & 1
        b_bit = (b >> k) & 1
        
        if original_order == 'asc':
            required_bit = 0
        else:
            required_bit = 1
        
        # Check for conflicts
        if mask_dict[k] is not None and mask_dict[k] != required_bit:
            conflict = True
            break
        mask_dict[k] = required_bit
    
    if conflict:
        print(0)
        return
    
    # Construct fixed_mask and fixed_value
    fixed_mask = 0
    fixed_value = 0
    for bit in mask_dict:
        req = mask_dict[bit]
        fixed_mask |= (1 << bit)
        fixed_value |= (req << bit)
    
    # Now, compute the count of x in [L, R] where x & fixed_mask == fixed_value
    def count_masked(L, R, mask, value):
        if mask == 0:
            if value != 0:
                return 0
            return max(0, R - L + 1)
        free_mask = (~mask) & ((1 << 61) - 1)
        # x must be value | s where s is a subset of free_mask's bits
        # Use digit DP to count s where (value ^ s) is between L and R
        # And s is a subset of free_mask
        
        # DP state: [pos][loose_low][loose_high]
        dp_prev = [[0]*2 for _ in range(2)]
        dp_prev[0][0] = 1  # start with tight lower and upper
        
        for pos in reversed(range(61)):  # process from 60 downto 0
            current_bit = pos
            dp_curr = [[0]*2 for _ in range(2)]
            
            for loose_low in [0, 1]:
                for loose_high in [0, 1]:
                    count = dp_prev[loose_low][loose_high]
                    if count == 0:
                        continue
                    # Determine allowed y_bit for current position
                    if (free_mask >> current_bit) & 1:
                        possible_y_bits = [0, 1]
                    else:
                        possible_y_bits = [0]
                    
                    for y_bit in possible_y_bits:
                        x_bit = ((value >> current_bit) ^ y_bit) & 1
                        new_loose_low = loose_low
                        new_loose_high = loose_high
                        
                        # Check against lower bound L
                        if not loose_low:
                            lb = (L >> current_bit) & 1
                            if x_bit < lb:
                                continue  # x is less than L, invalid
                            elif x_bit > lb:
                                new_loose_low = 1  # now x is definitely >= L
                        
                        # Check against upper bound R
                        if not loose_high:
                            ub = (R >> current_bit) & 1
                            if x_bit > ub:
                                continue  # x is larger than R, invalid
                            elif x_bit < ub:
                                new_loose_high = 1  # now x is definitely <= R
                        
                        dp_curr[new_loose_low][new_loose_high] += count
            dp_prev = dp_curr
        
        total = 0
        for loose_low in [0, 1]:
            for loose_high in [0, 1]:
                # If after all bits processed, check if x is within [L, R]
                # All transitions have ensured that x >= L and x <= R
                total += dp_prev[loose_low][loose_high]
        return total
    
    result = count_masked(L, R, fixed_mask, fixed_value)
    print(result)

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