Overview

For each query price \(X\), if there are products with that exact price, output all their names in product number order; otherwise, suggest one product name with the “closest price.”

Analysis

The two key points are:

1. When the price exactly matches
   Output all products with the same price, in ascending order of product number. Since the input is given in order of product numbers \(1,2,\dots,N\), appending names to an array for each price naturally maintains product number order.

2. When there is no exact match, find the “closest price”
   Naively scanning all products for each query to find the minimum \(|V_i-X|\) would be \(O(NQ)\), which reaches up to \(10^{10}\) and results in TLE.
   Instead, by focusing only on prices and sorting the set of existing prices, we can use binary search to only check the prices immediately before and after \(X\).
   The closest candidates are:

   • The largest price smaller than \(X\) (predecessor)
   • The smallest price greater than or equal to \(X\) (successor)

Furthermore, if the differences are equal (e.g., \(X=100\), prices are 98 and 102), we need to choose the one with the smallest product number. By precomputing “the smallest product number among products with a given price,” we can handle tiebreaking by just comparing prices.

Algorithm

As preprocessing, we build the following:

• price_to_names[v]: A list of product names with price \(v\), ordered by product number
  (Simply appending in input order preserves product number order)
• price_to_min[v] = (min_index, name): Among products with price \(v\), the (index, name) of the product with the smallest product number
• prices: An array of all distinct prices (keys of price_to_min) sorted in ascending order

Each query \(X\) is processed as follows:

1. If price_to_names[X] exists, output its contents separated by spaces.
2. If it doesn’t exist, use binary search (bisect_left) on prices to find the insertion position pos.
   • pos==0: All prices are greater than \(X\) → the smallest price is the closest
   • pos==len(prices): All prices are less than \(X\) → the largest price is the closest
   • Otherwise: Compare the predecessor price lo_p=prices[pos-1] and the successor price hi_p=prices[pos]
     Compare the differences \(d_\mathrm{lo}=X-lo\_p\), \(d_\mathrm{hi}=hi\_p-X\):
     • Output the name from price_to_min[...] for the price with the smaller difference
     • If the differences are equal, compare price_to_min[lo_p] and price_to_min[hi_p] and output the name of the one with the smaller product number

Concrete Example

When the price list is [80, 120, 200] and \(X=150\), the predecessor is 120 and the successor is 200. The differences are 30 and 50, so we suggest the name of the product (with the smallest number) at price 120.
When \(X=160\), the differences are both 40, so we compare the smallest-numbered product on the 120 side with the smallest-numbered product on the 200 side, and output the one with the smaller product number.

Complexity

• Time complexity:
  Preprocessing \(O(N)\), price sorting \(O(M\log M)\) (\(M\) is the number of distinct prices, \(M\le N\)), binary search per query \(O(\log M)\), giving an overall complexity of \(O(N + M\log M + Q\log M)\)
  ※ Outputting matching prices additionally takes time proportional to the “number of characters output” (which is at most \(10^6\) according to the problem statement).
• Space complexity: \(O(N + M)\) (name lists per price, price array, etc.)

Implementation Notes

• Output order for products with the same price is “by product number,” so simply appending in input order is sufficient.

• To handle the case where “multiple prices are equally close,” store the product with the smallest product number for each price in price_to_min (without this, an additional search within products of the same price would be needed).

• For binary search, it suffices to check only the two prices: predecessor and successor.

• Since \(N,Q\) can be large, in Python it is safer to use sys.stdin.buffer.read() for fast input and accumulate output in an array to print all at once at the end.

  Source Code

import sys
from bisect import bisect_left

def main():
    data = sys.stdin.buffer.read().split()
    it = iter(data)
    N = int(next(it))
    Q = int(next(it))

    price_to_names = {}
    price_to_min = {}  # price -> (min_index, name)

    for i in range(1, N + 1):
        s = next(it).decode()
        v = int(next(it))

        lst = price_to_names.get(v)
        if lst is None:
            price_to_names[v] = [s]
        else:
            lst.append(s)

        cur = price_to_min.get(v)
        if cur is None or i < cur[0]:
            price_to_min[v] = (i, s)

    prices = sorted(price_to_min.keys())

    out_lines = []
    for _ in range(Q):
        x = int(next(it))
        names = price_to_names.get(x)
        if names is not None:
            out_lines.append(" ".join(names))
            continue

        pos = bisect_left(prices, x)
        if pos == 0:
            out_lines.append(price_to_min[prices[0]][1])
        elif pos == len(prices):
            out_lines.append(price_to_min[prices[-1]][1])
        else:
            lo_p = prices[pos - 1]
            hi_p = prices[pos]
            d_lo = x - lo_p
            d_hi = hi_p - x
            if d_lo < d_hi:
                out_lines.append(price_to_min[lo_p][1])
            elif d_hi < d_lo:
                out_lines.append(price_to_min[hi_p][1])
            else:
                lo_i, lo_s = price_to_min[lo_p]
                hi_i, hi_s = price_to_min[hi_p]
                out_lines.append(lo_s if lo_i < hi_i else hi_s)

    sys.stdout.write("\n".join(out_lines))

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.