User's AC Ratio

73.9% (17/23)

Submission's AC Ratio

24.5% (26/106)

Description

那個(邊緣)人記錄完所有握手後,他突然發現了每個人的手的長度都發生了變化(可能是因為過度拉扯導致手的長度改變吧)。因為他有握手的紀錄,所以他可以根據握手的紀錄推算出每個人的手的長度變化。然而他的計算能力有限,沒辦法算出每個人手長變化的確切值,只能得出給定的兩個人手長變化誰大誰小。

為了醫治這些手變太長的人們,你,握手宴會在旁待命的醫生,決定挺身而出將這「握手症候群」根絕。然而,其中有$l$個人病情特別嚴重,而他們自己都不知情。根據邊緣人的計算,這$l$個人分別是手長變化長度第$d[0],d[1],...,d[l-1]$小的人。為了在他們手脫落之前醫治好他們,你決定使用程式幫助你。而在他們手脫落之前,你有$2\times 10^ 7$次詢問邊緣人的機會。

Input Format

本題沒有輸入。
#include "lib1172.h"
在標頭檔中其中一個函式
int comp(int a, int b);
會回傳第$a$號的人的手長變化是否比第$b$號小,是的話回傳1,不是的話回傳0。注意人的編號是由$0$開始編號的。如果$a,b$超出範圍或者你呼叫超過$2\times 10^ 7$次這個函式,你會得到一個WA。
而你需要實作一個函式
void query(int n, int d[], int l, int ans[]);
其中$n\leq 10^ 6$代表參加宴會的人數,d[]和$l\leq 100$如題敘,而你需要將病情嚴重的$l$個人的編號依序輸出至ans[]。

保證$n$個人的手長變化都不相同,並且d[]中的數是嚴格遞增且介於$0$到$n-1$之間的數。評測時每筆測資只會有一組測試資料。

子任務(測資) 額外限制 分數
1 (0~4) $n\leq 10^ 4$ 13
2 (5~9) $n\leq 10^ 5$ 12
3 (10~14) 無限制 75

Output Format

本題沒有輸出。

Sample Input

注意:本題沒有輸入,本輸入為提供測試標頭檔(參見Hints)使用。
5
2 8 3 1 5
3
0 2 4

Sample Output

注意:本題沒有輸出,本輸出為提供測試標頭檔(參見Hints)使用。
3 2 1

Hints

這裡有一個測試用的標頭檔,可以用來測試。
(註:由於不知名原因無法更新,請加入一行#include <stdlib.h>
該標頭檔接受以下輸入,數字間皆以空白分隔:
第一行:$n$;
第二行:$a_0,a_1,\dots,a_{n-1}$代表手長變化;
第三行:$l$;
第四行:$d_0,d_1,\dots, d_{l-1}$
最後程式會輸出$l$個數,代表你回傳的$ans$。

如果你呼叫超過次數的話,程式會輸出"Limit exceeded!!"。
如果你呼叫函數時的$x$或$y$超出範圍,程式會輸出"Out of range!!"

Problem Source

Problem set / Description by Paupière
建國中學105學年度校內第一次模擬賽pB

Subtasks

For Testdata: 0 ~ 4, Score: 13
For Testdata: 5 ~ 9, Score: 12
For Testdata: 10 ~ 14, Score: 75
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 262144
1 1000 65536 262144
2 1000 65536 262144
3 1000 65536 262144
4 1000 65536 262144
5 1000 65536 262144
6 1000 65536 262144
7 1000 65536 262144
8 1000 65536 262144
9 1000 65536 262144
10 1000 65536 262144
11 1000 65536 262144
12 1000 65536 262144
13 1000 65536 262144
14 1000 65536 262144