結果

問題 No.911 ラッキーソート
コンテスト
ユーザー lam6er
提出日時 2025-04-15 23:39:38
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,921 bytes
コンパイル時間 151 ms
コンパイル使用メモリ 82,208 KB
実行使用メモリ 128,908 KB
最終ジャッジ日時 2025-04-15 23:41:10
合計ジャッジ時間 5,859 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 24 WA * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx])
    idx += 1
    L = int(input[idx])
    idx += 1
    R = int(input[idx])
    idx += 1
    A = list(map(int, input[idx:idx+N]))
    idx += N
    
    if N == 1:
        print(max(0, R - L + 1))
        return
    
    bit_dict = {}
    
    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
        if a < b:
            required_bit = 0
        else:
            required_bit = 1
        if k in bit_dict:
            if bit_dict[k] != required_bit:
                print(0)
                return
        else:
            bit_dict[k] = required_bit
    
    mask = 0
    fixed_mask = 0
    for bit in bit_dict:
        mask |= (1 << bit)
        fixed_mask |= (bit_dict[bit] << bit)
    
    if mask == 0:
        print(max(0, R - L + 1))
        return
    
    m = mask + 1
    r = fixed_mask
    
    if r >= m:
        print(0)
        return
    
    low = L
    high = R
    
    if low > high:
        print(0)
        return
    
    remainder_low = low % m
    if remainder_low <= r:
        first_x = low + (r - remainder_low)
    else:
        first_x = low + (m - (remainder_low - r))
    
    if first_x < low:
        steps = (low - first_x + m - 1) // m
        first_x += steps * m
    
    if first_x > high:
        print(0)
        return
    
    remainder_high = high % m
    if remainder_high >= r:
        last_x = high - (remainder_high - r)
    else:
        last_x = high - (remainder_high + m - r)
    
    if last_x > high:
        steps = (last_x - high + m - 1) // m
        last_x -= steps * m
    
    if last_x < low or first_x > last_x:
        print(0)
        return
    
    count = (last_x - first_x) // m + 1
    print(count)

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