Overview

This is a problem about implementing a system that responds to search queries based on product prices. If there is an exact match, output all product names with that price; otherwise, suggest one product with the closest price.

Analysis

In this problem, up to \(10^5\) products and \(10^5\) queries are given, so efficient processing is required.

Naive Approach and Its Issues

A straightforward approach would be to scan all products for each query to find ones with a matching price. This takes \(O(N)\) per query, resulting in \(O(Q \cdot N)\) overall, which requires up to \(10^{10}\) computations in the worst case and will not meet the time limit.

Similarly, finding the “product with the closest price” when there is no exact match would also be slow if done with a linear search each time.

Improvements

• By pre-building a product list for each price, we can quickly determine and retrieve exact matches.
• To find the “closest price,” we can sort the list of prices and use binary search (bisect) to efficiently find it.

Furthermore, when there is an exact match, the output must be in “product number order,” so we need to pre-sort the product list for each price by product number.

Algorithm

1. Reading Input and Preprocessing

   • Store each product as a tuple of (price, product number, name).
   • Use defaultdict(list) to maintain a list of (product number, name) for each price.
   • Sort the list for each price in ascending order of product number.

2. Sorting Prices

   • Extract only the price keys and create a sorted list sorted_prices (for binary search).

3. Query Processing

   • For each query \(X_j\), do the following:
     • Exact Match: If \(X_j\) exists as a key, concatenate and output the product name list for that price in order.
     • Nearest Price:

          - Use `bisect_left(sorted_prices, X_j)` to get the position of the smallest price greater than or equal to $X_j$.
          - Consider prices to the left and right of that position (if they exist) as candidates, compare their differences and product numbers, and select one product that satisfies the conditions.
       

Complexity

• Time complexity: \(O(N \log N + Q \log N)\)
  • Preprocessing products takes \(O(N \log N)\) (sorting the price list)
  • Each query uses \(O(\log N)\) for binary search, and candidate comparison is constant time, so the total is \(O(Q \log N)\)
• Space complexity: \(O(N + Q)\)
  • For storing product information, price-to-product mappings, sorted price list, etc.

Implementation Notes

• Manage product data as tuples like (price, number, name) to facilitate sorting and searching.

• For exact match output, the order must be “by product number,” so it is important to pre-sort the list for each price.

• When comparing left and right candidates after binary search, note that if the differences are equal, the product with the smaller product number should be chosen.

• To read input quickly, use sys.stdin.read and perform string splitting only once for speed optimization.

  Source Code

import bisect
from collections import defaultdict
import sys

input = sys.stdin.read

def main():
    data = input().split()
    idx = 0
    N = int(data[idx])
    idx += 1
    Q = int(data[idx])
    idx += 1
    
    products = []
    price_to_names = defaultdict(list)
    
    for i in range(N):
        S = data[idx]
        idx += 1
        V = int(data[idx])
        idx += 1
        products.append((V, i, S))
        price_to_names[V].append((i, S))
    
    # 各価格ごとに商品を番号順にソート
    for price in price_to_names:
        price_to_names[price].sort()
    
    # 価格リストをソートしたものを保持（二分探索用）
    sorted_prices = sorted(price_to_names.keys())
    
    results = []
    for _ in range(Q):
        X = int(data[idx])
        idx += 1
        
        if X in price_to_names:
            # 一致する価格の商品名を番号順に出力
            names = [name for _, name in price_to_names[X]]
            results.append(' '.join(names))
        else:
            # 最も近い価格を探す
            pos = bisect.bisect_left(sorted_prices, X)
            candidates = []
            
            # 左隣
            if pos > 0:
                left_price = sorted_prices[pos - 1]
                diff = abs(left_price - X)
                candidates.append((diff, price_to_names[left_price][0][0], price_to_names[left_price][0][1]))
            
            # 右隣
            if pos < len(sorted_prices):
                right_price = sorted_prices[pos]
                diff = abs(right_price - X)
                candidates.append((diff, price_to_names[right_price][0][0], price_to_names[right_price][0][1]))
            
            # 最小差分を選ぶ（同じなら番号が小さい方）
            candidates.sort()
            results.append(candidates[0][2])
    
    print('\n'.join(results))

if __name__ == "__main__":
    main()

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