C - Product Search System
Editorial
/ 
/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 366 点
問題文
高橋君はオンラインショップを運営しており、N 個の商品を取り扱っています。商品には 1 から N までの番号が付けられており、商品 i (1 \leq i \leq N) の名前は文字列 S_i で、価格は V_i 円です。異なる商品が同じ名前を持つことや、同じ価格を持つこともあります。
青木君はこのショップの顧客で、Q 件の検索リクエストを送りました。j 番目 (1 \leq j \leq Q) のリクエストでは、整数 X_j を指定し、「価格がちょうど X_j 円の商品をすべて教えてほしい」と頼みます。
しかし、青木君は正確な価格を覚えていないことがあります。そこで高橋君は、青木君の利便性のために、次のルールで検索結果を返すことにしました。
- 価格がちょうど X_j 円である商品が 1 つ以上存在する場合は、それらの商品の名前を すべて、商品番号の小さい順にスペース区切りで 1 行に出力します。該当する商品の中に同じ名前のものが複数あっても、それぞれ別の商品として 1 回ずつ出力します（つまり名前が重複して出力されることがあります）。
- 価格がちょうど X_j 円である商品が 1 つも存在しない場合は、「もしかしてこの商品ですか？」という提案として、価格が X_j に最も近い商品を 1 つ選んで出力します。具体的には、価格の差の絶対値 |V_i - X_j| が最小となる商品を候補とします。候補が複数存在する場合（例えば X_j より同じだけ安い商品と高い商品がある場合など）は、その中で商品番号が最も小さいものを選びます。選ばれた商品の名前を 1 つだけ 1 行に出力します。
各リクエストに対する検索結果を求めてください。
制約
- 1 \leq N \leq 10^5
- 1 \leq Q \leq 10^5
- S_i は英小文字のみからなる長さ 1 以上 20 以下の文字列である。
- 1 \leq V_i \leq 10^9
- 1 \leq X_j \leq 10^9
- N, Q, V_i, X_j はすべて整数である。
- 全リクエストにわたって出力される商品名の文字数の総和（区切りのスペースや改行は含まない）は 10^6 を超えないことが保証される。
入力
N Q S_1 V_1 S_2 V_2 \vdots S_N V_N X_1 X_2 \vdots X_Q
- 1 行目には、商品の数 N と検索リクエストの数 Q が、スペース区切りで与えられる。
- 続く N 行のうち i 番目の行 (1 \leq i \leq N) には、商品 i の名前を表す文字列 S_i と、価格を表す整数 V_i が、スペース区切りで与えられる。
- 続く Q 行のうち j 番目の行 (1 \leq j \leq Q) には、j 番目の検索リクエストで指定される価格 X_j が与えられる。
出力
Q 件の検索リクエストそれぞれについて、1 行ずつ出力せよ。
- 価格がちょうど X_j 円である商品が 1 つ以上存在する場合、それらの名前を商品番号の小さい順にスペース区切りで出力せよ。同じ名前の商品が複数該当する場合も、それぞれ別の商品として 1 回ずつ出力せよ。
- 価格がちょうど X_j 円である商品が存在しない場合、|V_i - X_j| が最小となる商品のうち商品番号が最も小さいものの名前を 1 つだけ出力せよ。
入力例 1
5 4 apple 100 banana 200 cherry 100 date 300 elderberry 500 100 250 300 150
出力例 1
apple cherry banana date apple
入力例 2
4 5 milk 150 bread 150 cheese 300 butter 300 150 300 200 225 450
出力例 2
milk bread cheese butter milk milk cheese
入力例 3
10 8 notebook 1200 pen 300 eraser 100 ruler 500 pencil 300 marker 800 tape 250 glue 250 scissors 1500 stapler 1200 300 1200 100 700 2000 1 250 999
出力例 3
pen pencil notebook stapler eraser marker scissors eraser tape glue marker
入力例 4
15 10 alpha 1000 beta 2000 gamma 3000 delta 4000 epsilon 5000 zeta 6000 eta 7000 theta 8000 iota 9000 kappa 10000 lambda 1000 mu 5000 nu 5000 xi 15000 omicron 20000 5000 1000 7500 1 1000000000 10000 15000 12000 20000 3500
出力例 4
epsilon mu nu alpha lambda eta alpha omicron kappa xi kappa omicron gamma
入力例 5
1 1 a 1000000000 1000000000
出力例 5
a
Score : 366 pts
Problem Statement
Takahashi runs an online shop and handles N products. The products are numbered from 1 to N, and product i (1 \leq i \leq N) has the name S_i and a price of V_i yen. Different products may have the same name or the same price.
Aoki is a customer of this shop and has sent Q search requests. In the j-th request (1 \leq j \leq Q), he specifies an integer X_j and asks: "Please tell me all products whose price is exactly X_j yen."
However, Aoki may not remember the exact price. Therefore, for Aoki's convenience, Takahashi decided to return search results according to the following rules:
- If there exist one or more products whose price is exactly X_j yen, output all of their names on a single line, separated by spaces, in ascending order of product number. Even if multiple matching products have the same name, each is output once as a separate product (meaning names may appear duplicated in the output).
- If no product has a price of exactly X_j yen, as a suggestion of "Did you mean this product?", select and output one product whose price is closest to X_j. Specifically, the candidates are the products that minimize the absolute difference |V_i - X_j|. If there are multiple candidates (for example, a product that is equally cheaper and one that is equally more expensive than X_j), choose the one with the smallest product number among them. Output only one name of the selected product on a single line.
Determine the search results for each request.
Constraints
- 1 \leq N \leq 10^5
- 1 \leq Q \leq 10^5
- S_i is a string of length between 1 and 20 inclusive, consisting only of lowercase English letters.
- 1 \leq V_i \leq 10^9
- 1 \leq X_j \leq 10^9
- N, Q, V_i, X_j are all integers.
- It is guaranteed that the total number of characters of product names output across all requests (excluding separating spaces and newlines) does not exceed 10^6.
Input
N Q S_1 V_1 S_2 V_2 \vdots S_N V_N X_1 X_2 \vdots X_Q
- The first line contains the number of products N and the number of search requests Q, separated by a space.
- The i-th of the following N lines (1 \leq i \leq N) contains the string S_i representing the name of product i and the integer V_i representing its price, separated by a space.
- The j-th of the following Q lines contains the price X_j specified in the j-th search request.
Output
For each of the Q search requests, output one line.
- If there exist one or more products whose price is exactly X_j yen, output their names separated by spaces in ascending order of product number. Even if multiple matching products have the same name, output each as a separate product.
- If no product has a price of exactly X_j yen, output only the name of the product with the smallest product number among those that minimize |V_i - X_j|.
Sample Input 1
5 4 apple 100 banana 200 cherry 100 date 300 elderberry 500 100 250 300 150
Sample Output 1
apple cherry banana date apple
Sample Input 2
4 5 milk 150 bread 150 cheese 300 butter 300 150 300 200 225 450
Sample Output 2
milk bread cheese butter milk milk cheese
Sample Input 3
10 8 notebook 1200 pen 300 eraser 100 ruler 500 pencil 300 marker 800 tape 250 glue 250 scissors 1500 stapler 1200 300 1200 100 700 2000 1 250 999
Sample Output 3
pen pencil notebook stapler eraser marker scissors eraser tape glue marker
Sample Input 4
15 10 alpha 1000 beta 2000 gamma 3000 delta 4000 epsilon 5000 zeta 6000 eta 7000 theta 8000 iota 9000 kappa 10000 lambda 1000 mu 5000 nu 5000 xi 15000 omicron 20000 5000 1000 7500 1 1000000000 10000 15000 12000 20000 3500
Sample Output 4
epsilon mu nu alpha lambda eta alpha omicron kappa xi kappa omicron gamma
Sample Input 5
1 1 a 1000000000 1000000000
Sample Output 5
a