Overview

This is a problem where, for product price search queries, you must quickly answer: if there exists a product with a price exactly matching the specified price, output all matching products; otherwise, output the product with the closest price (and if there are multiple candidates with the same price difference, output the one with the smallest product number).

Analysis

Since both \(N\) and \(Q\) can be up to \(10^5\), checking all products for each query would result in \(O(NQ)\) time complexity, causing a Time Limit Exceeded (TLE) verdict. Therefore, we need a method to process queries efficiently.

• Searching for an exact price match By using a hash map (associative array or dictionary) that stores product numbers keyed by price, we can search in \(O(1)\) or \(O(\log N)\) time.
• Searching for the closest price By sorting the list of existing prices in ascending order beforehand and performing binary search, we can find the neighboring prices in \(O(\log N)\) time.

Additionally, the problem states: “output matching products in ascending order of product number” and “if the price difference is the same, output the one with the smaller product number.” Since the input data is given in ascending order of product numbers (from \(1\) to \(N\)), simply adding them to the dictionary in order automatically creates lists sorted by product number in ascending order. Leveraging this property makes the implementation much easier.

Algorithm

1. Preprocessing (Data Preparation)

   • Read product information in order. Create a dictionary exact_match with price \(v\) as the key and a list of product numbers with that price as the value.
   • Extract all existing prices (keys of exact_match) and create a sorted array sorted_V in ascending order.

2. Query Processing For each request price \(X\), do the following:

   • If an exact price match exists Check if \(X\) exists in the dictionary exact_match. If it does, output all product names in that list, separated by spaces.
   • If no exact price match exists Use binary search to find the position pos where \(X\) would be inserted in sorted_V.
     • If pos == 0: All product prices are higher than \(X\), so select the cheapest price sorted_V[0].
     • If pos equals the length of the array: All product prices are lower than \(X\), so select the most expensive price sorted_V[-1].
     • Otherwise: The two prices surrounding \(X\), \(v_1 = sorted\_V[pos-1]\) and \(v_2 = sorted\_V[pos]\), are candidates. Compare the differences \(|v_1 - X|\) and \(|v_2 - X|\), and select the price with the smaller difference. If the differences are equal, compare the smallest product numbers of each price (the first element of each dictionary list) and select the price with the smaller product number.
     • Finally, output the product name at the head of the selected price’s list.

Complexity

• Time complexity: \(O(N \log N + Q \log N + L)\)
  • Let \(K\) (\(K \le N\)) be the number of distinct prices. Sorting the prices takes \(O(K \log K)\).
  • Binary search for \(Q\) queries takes \(O(Q \log K)\).
  • Dictionary lookup is \(O(1)\).
  • \(L\) is the total number of characters output across all queries (at most \(10^6\) according to the constraints).
  • Overall, this runs very efficiently and comfortably fits within the time limit.
• Space complexity: \(O(N)\)
  • Memory for storing product names, the dictionary, the sorted price array, etc.

Implementation Notes

• Utilizing binary search: In Python, using bisect_left from the bisect module allows you to easily perform binary search without implementing it yourself.

• Using the first element of lists: Since products are processed in order and added to the dictionary, the list exact_match[v] is always in ascending order of product number. Therefore, simply accessing exact_match[v][0] gives us “the product with the smallest product number at price \(v\)” in \(O(1)\).

• Fast I/O: Since the problem involves a large amount of input and output, calling input() or print() each time can be slow. By reading all input at once with sys.stdin.read().split() and accumulating output in an array, then joining with \n and printing all at once at the end, we can significantly speed up processing.

  Source Code

import sys
from bisect import bisect_left

def main():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    Q = int(input_data[1])
    
    S = []
    exact_match = {}
    
    idx = 2
    for i in range(N):
        s = input_data[idx]
        v = int(input_data[idx+1])
        S.append(s)
        if v not in exact_match:
            exact_match[v] = []
        exact_match[v].append(i)
        idx += 2
        
    sorted_V = sorted(exact_match.keys())
    
    out = []
    for _ in range(Q):
        X = int(input_data[idx])
        idx += 1
        
        if X in exact_match:
            out.append(" ".join([S[i] for i in exact_match[X]]))
        else:
            pos = bisect_left(sorted_V, X)
            if pos == 0:
                best_V = sorted_V[0]
            elif pos == len(sorted_V):
                best_V = sorted_V[-1]
            else:
                v1 = sorted_V[pos - 1]
                v2 = sorted_V[pos]
                diff1 = X - v1
                diff2 = v2 - X
                if diff1 < diff2:
                    best_V = v1
                elif diff2 < diff1:
                    best_V = v2
                else:
                    idx1 = exact_match[v1][0]
                    idx2 = exact_match[v2][0]
                    if idx1 < idx2:
                        best_V = v1
                    else:
                        best_V = v2
            out.append(S[exact_match[best_V][0]])
            
    sys.stdout.write("\n".join(out) + "\n")

if __name__ == '__main__':
    main()

This editorial was generated by gemini-3.1-pro-thinking.