TopCoder

icube
baluteshih 好強 <(_ _)>

User's AC Ratio

78.6% (22/28)

Submission's AC Ratio

20.8% (36/173)

Tags

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 1

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

Sample Output 1

注意:本題沒有輸出,本輸出為提供測試標頭檔(參見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

No. Testdata Range Score
1 0~4 13
2 5~9 12
3 10~14 75

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 1
2 1000 65536 262144 1
3 1000 65536 262144 1
4 1000 65536 262144 1
5 1000 65536 262144 2
6 1000 65536 262144 2
7 1000 65536 262144 2
8 1000 65536 262144 2
9 1000 65536 262144 2
10 1000 65536 262144 3
11 1000 65536 262144 3
12 1000 65536 262144 3
13 1000 65536 262144 3
14 1000 65536 262144 3