Overview

This problem requires processing \(Q\) price search queries for \(N\) products. If there are products matching the specified price, output all of them; otherwise, suggest one product with the closest price.

Analysis

Key Observation

For each query, we need to determine “Is there a product with price exactly \(X_j\)?” and if not, efficiently find “the product with the closest price.”

Issues with the Naive Approach

If we linearly scan all products for each query, a single query takes \(O(N)\), resulting in \(O(NQ)\) overall. Since \(N, Q \leq 10^5\), this leads to a maximum of \(10^{10}\) operations, which will result in TLE (Time Limit Exceeded).

Solution Strategy

• Exact match determination: Using a dictionary (hash map), we can check in \(O(1)\).
• Searching for the closest price: By sorting the unique prices and using binary search, we can find the answer in \(O(\log N)\).

Algorithm

1. Preprocessing:

   • For each price, store the list of product numbers with that price in a dictionary price_to_items. Since products are processed in order \(1, 2, \ldots, N\), the lists are naturally in ascending order of product number.
   • Extract the unique prices and create a sorted array sorted_prices.

2. Processing each query (for specified price \(X_j\)):

   • If there is an exact match: Output the names in order of product numbers registered in price_to_items[X_j], separated by spaces.
   • If there is no exact match: Perform binary search (bisect_left) on sorted_prices to obtain the insertion position pos. The candidates for the closest price are at most two: sorted_prices[pos-1] (the side smaller than \(X_j\)) and sorted_prices[pos] (the side larger than \(X_j\)). Compare the absolute differences for each, and if the differences are equal, choose the one with the smallest product number.

Concrete Example

Products: apple 100, banana 200, cherry 100, with query \(X = 150\): - No exact match → Binary search on sorted_prices = [100, 200] gives pos = 1 - Candidates: sorted_prices[0] = 100 (difference 50), sorted_prices[1] = 200 (difference 50) - Since the differences are the same, choose the one with the smaller product number → Product 1 with price 100, output “apple”

Complexity

• Time complexity: \(O(N \log N + Q \log N)\)
  • Sorting unique prices in preprocessing takes \(O(N \log N)\)
  • Each query requires dictionary lookup \(O(1)\) or binary search \(O(\log N)\)
• Space complexity: \(O(N)\)
  • Required for storing the dictionary, sorted array, and product names

Implementation Details

• Exact match determination using a dictionary: Checking x in price_to_items in \(O(1)\) allows fast branching between exact match and non-match cases.

• Boundary checks for binary search: The result pos from bisect_left may be 0 or len(sorted_prices), so care must be taken to avoid out-of-bounds access when examining candidates.

• Handling equal differences: When two candidates have the same difference, compare the first element (smallest product number) of each price group and choose the one with the smaller number. price_to_items[v][0] gives the smallest product number for each price group.

• Fast I/O: By reading all input at once with sys.stdin.buffer.read() and writing output collectively with '\n'.join(), we reduce I/O overhead.

  Source Code

import sys
from bisect import bisect_left

def main():
    input_data = sys.stdin.buffer.read().decode()
    tokens = input_data.split()
    idx = 0
    N = int(tokens[idx]); idx += 1
    Q = int(tokens[idx]); idx += 1
    
    names = []
    prices = []
    for i in range(N):
        s = tokens[idx]; idx += 1
        v = int(tokens[idx]); idx += 1
        names.append(s)
        prices.append(v)
    
    # Group by price: price -> list of (original_index, name)
    from collections import defaultdict
    price_to_items = defaultdict(list)
    for i in range(N):
        price_to_items[prices[i]].append(i)
    
    # Sorted unique prices for binary search
    sorted_prices = sorted(price_to_items.keys())
    
    out = []
    for _ in range(Q):
        x = int(tokens[idx]); idx += 1
        
        if x in price_to_items:
            # Exact match - items are already stored in order of original index
            items = price_to_items[x]
            out.append(' '.join(names[i] for i in items))
        else:
            # Find closest price
            pos = bisect_left(sorted_prices, x)
            best_diff = float('inf')
            best_idx = N  # large sentinel
            
            # Check pos-1 and pos
            for p in (pos - 1, pos):
                if 0 <= p < len(sorted_prices):
                    diff = abs(sorted_prices[p] - x)
                    if diff < best_diff or (diff == best_diff and price_to_items[sorted_prices[p]][0] < best_idx):
                        best_diff = diff
                        best_idx = price_to_items[sorted_prices[p]][0]
            
            out.append(names[best_idx])
    
    sys.stdout.write('\n'.join(out) + '\n')

main()

This editorial was generated by claude4.6opus-thinking.