Buckets of sizes sizes[0], sizes[1], ... are laid end to end on a number line starting at 0. Bucket 0 covers positions 0 .. sizes[0] - 1, bucket 1 covers the next sizes[1] positions, and so on. A bucket of size 0 covers nothing.
Write find_buckets(sizes: list[int], positions: list[int]) -> list[int] that returns, for each position, the index of the bucket containing it.
# sizes [3, 1, 2] cover: 0 1 2 | 3 | 4 5
find_buckets([3, 1, 2], [0, 2, 3, 4, 5]) # [0, 0, 1, 2, 2]
# the empty bucket 1 never owns anything
find_buckets([2, 0, 2], [1, 2]) # [0, 2]
Constraints: sizes[i] >= 0, the total is at least 1, every position is in [0, sum(sizes)). Up to 10^5 buckets and 10^5 positions, so scanning the buckets for each position is too slow.
Show hint
with ends = list(itertools.accumulate(sizes)), bucket i owns [ends[i] - sizes[i], ends[i]), so the answer is the first i with ends[i] > x, which is exactly bisect.bisect_right(ends, x).