結果
問題 |
No.911 ラッキーソート
|
ユーザー |
![]() |
提出日時 | 2025-04-16 16:26:09 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,701 bytes |
コンパイル時間 | 198 ms |
コンパイル使用メモリ | 81,216 KB |
実行使用メモリ | 111,896 KB |
最終ジャッジ日時 | 2025-04-16 16:28:15 |
合計ジャッジ時間 | 5,941 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 WA * 16 |
ソースコード
import sys def main(): N, L, R = map(int, sys.stdin.readline().split()) A = list(map(int, sys.stdin.readline().split())) if N == 1: print(R - L + 1) return mask = 0 value = 0 for i in range(N-1): a = A[i] b = A[i+1] c = a ^ b k = c.bit_length() - 1 while k >= 0 and (c >> k) & 1 == 0: k -= 1 if k < 0: print(0) return a_bit = (a >> k) & 1 b_bit = (b >> k) & 1 if a < b: req_bit = 0 else: req_bit = 1 if (mask & (1 << k)) != 0: if (value >> k) & 1 != req_bit: print(0) return else: mask |= (1 << k) value |= (req_bit << k) def count(n): if (value & mask) != value: return 0 if value > n: return 0 s = n - value free_bits = [] for bit in range(61): if (mask & (1 << bit)) == 0: free_bits.append(bit) free_bits.sort(reverse=True) n_bits = len(free_bits) suffix_sums = [0] * (n_bits + 1) for i in range(n_bits-1, -1, -1): suffix_sums[i] = suffix_sums[i+1] + (1 << free_bits[i]) res = 0 current = 0 for i in range(n_bits): bit = free_bits[i] bit_val = 1 << bit if current + bit_val > s: continue if current + bit_val + suffix_sums[i+1] <= s: res += (1 << (n_bits - i - 1)) current += bit_val else: remaining_bits = free_bits[i+1:] remaining_s = s - current - bit_val rem_res = 0 rem_current = 0 for j in range(len(remaining_bits)): rem_bit = remaining_bits[j] rem_val = 1 << rem_bit if rem_current + rem_val > remaining_s: continue if rem_current + rem_val + (suffix_sums[i+1 + j+1] if i+1 + j+1 < n_bits else 0) <= remaining_s: rem_res += (1 << (len(remaining_bits) - j - 1)) rem_current += rem_val else: pass if rem_current <= remaining_s: rem_res += 1 res += rem_res current += bit_val if current <= s: res += 1 return res total = count(R) - count(L-1) print(max(0, total)) if __name__ == '__main__': main()