1172 . 握手症候群

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

icube
baluteshih 好強 <(_ _)>

User's AC Ratio

80.0% (24/30)

Submission's AC Ratio

22.2% (40/180)

Tags

CKsim 2016-CKsim-1st IOIstyle Interactive

Description

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

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

Input Format

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

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

子任務（測資） 額外限制 分數
1 (0~4) n≤104 13
2 (5~9) n≤105 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;
第二行：a0,a1,…,an−1代表手長變化;
第三行：l;
第四行：d0,d1,…,dl−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
Submit
Back to Top