Overview

This problem requires implementing a system that searches a product database for products matching a specified price, and suggests the product with the closest price if no exact match exists.

Analysis

There are two key points to this problem:

1. Exact price matching: If there are products that exactly match the specified price \(X_j\), all of them must be output in order of product number
2. Closest price suggestion: If no matching product exists, select one product with the minimum absolute price difference \(|V_i - X_j|\), and if there are ties, choose the one with the smallest product number

A naive approach that scans all products for each query would take \(O(NQ)\) time, and since \(N, Q\) can be up to \(10^5\), this would require \(10^{10}\) operations, which would clearly result in TLE.

Algorithm

We use the following approach as an efficient solution:

1. Preprocessing: Group products by price, and sort by product number within each price group
2. Binary search: Create a sorted list of all prices, and use binary search to locate positions during query processing
3. Candidate selection: When there is no exact match, consider the prices before and after the position found by binary search (the closest prices) as candidates, and select the optimal product according to the conditions

Specific steps: - Create a dictionary with price \(v\) as the key and a list of \((product\ number, product\ name)\) as the value - Sort within each price group by product number - Create a sorted list prices of all prices - For each query \(X_j\): - Binary search in prices to locate the position of \(X_j\) - If there is an exactly matching price, output all corresponding product names - Otherwise, select two candidates from the adjacent prices, compare by price difference and product number, and choose the optimal one

Complexity

• Time complexity: \(O(N \log N + Q \log N)\)
  • Preprocessing sort: \(O(N \log N)\)
  • Processing each query: binary search is \(O(\log N)\), output for exact matches is within the guaranteed total character count
• Space complexity: \(O(N)\)
  • Storage for product data and price list

Implementation Notes

• Use bisect.bisect_left() to efficiently search for price positions

• For exact match output, retrieve product names from the list that is pre-sorted by product number

• For candidate selection, create tuples of (price difference, product number, product name) and sort by minimum price difference and minimum product number

• The constraint on the total sum of output characters guarantees that even large amounts of output will not cause issues

  Source Code

import bisect

def main():
    import sys
    data = sys.stdin.read().splitlines()
    n, q = map(int, data[0].split())
    products = []
    price_to_products = {}
    
    for i in range(1, n+1):
        parts = data[i].split()
        s = parts[0]
        v = int(parts[1])
        products.append((v, s, i))
        if v not in price_to_products:
            price_to_products[v] = []
        price_to_products[v].append((i, s))
    
    for key in price_to_products:
        price_to_products[key].sort(key=lambda x: x[0])
    
    prices = sorted(price_to_products.keys())
    queries = list(map(int, data[n+1:n+1+q]))
    
    output_lines = []
    for x in queries:
        if x in price_to_products:
            names = [item[1] for item in price_to_products[x]]
            output_lines.append(" ".join(names))
        else:
            idx = bisect.bisect_left(prices, x)
            candidates = []
            if idx > 0:
                candidate_price1 = prices[idx-1]
                diff1 = abs(candidate_price1 - x)
                candidate_product1 = price_to_products[candidate_price1][0]
                candidates.append((diff1, candidate_product1[0], candidate_product1[1]))
            if idx < len(prices):
                candidate_price2 = prices[idx]
                diff2 = abs(candidate_price2 - x)
                candidate_product2 = price_to_products[candidate_price2][0]
                candidates.append((diff2, candidate_product2[0], candidate_product2[1]))
            
            candidates.sort(key=lambda cand: (cand[0], cand[1]))
            output_lines.append(candidates[0][2])
    
    for line in output_lines:
        print(line)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.