Overview

Given the positions of houses and shelters on a number line, find the distance from each house to the nearest shelter.

Analysis

In this problem, for each house’s coordinate \(X_i\), we need to find the nearest shelter’s coordinate \(P_j\) and compute the distance \(|X_i - P_j|\).

If we naively compute the distance to all shelters, the time complexity becomes \(O(N \times M)\), requiring up to \(4 \times 10^{10}\) computations, which will not fit within the time limit (TLE).

However, by leveraging the fact that the shelter coordinates are sorted in ascending order, we can efficiently find the “nearest shelter” using binary search. Specifically, for a house \(X_i\), we only need to consider the following two candidates: - The smallest shelter coordinate that is greater than or equal to \(X_i\) (right neighbor) - The largest shelter coordinate that is less than \(X_i\) (left neighbor)

These can be found in \(O(\log M)\) using the bisect module.

For example, if a house’s coordinate is 5 and the shelters are [2, 6, 8], then: - The left neighbor is 2, and the right neighbor is 6 - The distances are 3 and 1, respectively → the minimum is 1

In this way, it is sufficient to only check the two neighboring shelters.

Algorithm

1. For each house \(X_i\), perform a binary search on the shelter list \(P\).
2. Use bisect.bisect_left(P, x) to obtain the index of the smallest shelter that is greater than or equal to \(x\).
3. Compare the distances to the shelter at that index and the shelter at the index one before it, and choose the smaller one.
4. Repeat this for all houses.

Complexity

• Time complexity: \(O(N \log M)\)
  Because we perform an \(O(\log M)\) binary search for each house.
• Space complexity: \(O(N + M)\)
  Because we need to store the input data as lists.

Implementation Notes

• The shelter list \(P\) is assumed to be sorted, so binary search can be used.

• Be careful with edge cases where the result of bisect_left is 0 or M (cases where only the leftmost or rightmost shelter exists as a candidate).

• sys.stdin.read is used to read input efficiently.

  Source Code

import bisect
import sys

def main():
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    M = int(data[1])
    X = list(map(int, data[2:2+N]))
    P = list(map(int, data[2+N:2+N+M]))
    
    result = []
    for x in X:
        # 二分探索でx以上の最小の避難所を探す
        idx = bisect.bisect_left(P, x)
        min_dist = float('inf')
        
        # x以上の最小の避難所
        if idx < M:
            min_dist = min(min_dist, abs(x - P[idx]))
        # x未満の最大の避難所
        if idx > 0:
            min_dist = min(min_dist, abs(x - P[idx - 1]))
            
        result.append(min_dist)
    
    print('\n'.join(map(str, result)))

if __name__ == "__main__":
    main()

This editorial was generated by qwen3-coder-480b.