本題為互動題,僅限使用 C/C++ 作答
有一個電腦叢集,裡面有 $N$ 台電腦,可以想像成 $N$ 個電腦排成一排,
而其中有一些電腦壞掉了,你想要找到是哪些電腦壞掉才方便維修,
這些電腦是叢集電腦,因此會互相知道其他電腦的狀況,
你想透過對某些電腦詢問來得知壞掉的電腦是哪些。
你每次可以對一台電腦詢問 $[l,r]$ 之間是否有電腦壞掉,
不過如果對壞掉的電腦查詢,有可能會得到錯誤的結果,
且因為電腦叢集不穩定的關係,你最多只可以執行 $300019$ 次的詢問操作。
你希望可以找到任意一台壞掉電腦的位置在哪。
保證至少有一台電腦是壞掉的,且沒壞的電腦數量大於 $\frac{N}{2}$。
本題測資為動態生成,每筆 submission 的測資可能不同。
本題沒有輸入,若你輸入了任何東西,可能會導致各種不可預期的結果。
請記得 #include "lib0113.h"
,以下幾個是你可以使用的函式:
int Init()
:此函式會回傳一個數字 $N$,代表這個電腦叢集的電腦數量。
int Query(int pos, int l, int r)
:對編號為 $pos$ 的電腦詢問 $[l,r]$ 是否有電腦是壞掉的,如果查詢的區間存在壞掉的電腦,此函式會回傳 $1$,否則回傳 $0$;其中 $pos,l,r$ 均需介於 $[1,N]$ 且 $l<=r$。請注意,如果你對一台壞掉的電腦查詢,得到的結果不一定會是正確的。你最多只能呼叫此函式 $300019$ 次。
void Fix(int pos)
:回傳你認為是壞掉電腦的編號,如果有多個,只需回傳任意一個即可;其中 $pos$ 需介於 $[1,N]$。這個函式會自動幫你結束程式。
本題沒有輸出,若你輸出了任何東西,你將會得到一個 WA。
這裡提供一份範例標頭檔可以使用。
若在本機使用這份標頭檔執行時,輸入格式如下:
第一行會有一個數字 $N$,代表電腦數量。
接下來一行有 $N$ 個數字,第 $i$ 個數字 $c_i$ 代表第 $i$ 台電腦狀態,若 $c_i=0$ 則代表該電腦壞掉了,否則 $c_i=1$。
如果你的程式被評為 WA,範例評分程式會輸出 "Wrong Answer: MSG",其中 MSG 格式與意義如下:
No. | Testdata Range | Score |
---|---|---|
1 | 0~51 | 100 |
No. | Time Limit (ms) | Memory Limit (KiB) | Output Limit (KiB) | Subtasks |
---|---|---|---|---|
0 | 1000 | 65536 | 65536 | |
1 | 1000 | 65536 | 65536 | |
2 | 1000 | 65536 | 65536 | |
3 | 1000 | 65536 | 65536 | |
4 | 1000 | 65536 | 65536 | |
5 | 1000 | 65536 | 65536 | |
6 | 1000 | 65536 | 65536 | |
7 | 1000 | 65536 | 65536 | |
8 | 1000 | 65536 | 65536 | |
9 | 1000 | 65536 | 65536 | |
10 | 1000 | 65536 | 65536 | |
11 | 1000 | 65536 | 65536 | |
12 | 1000 | 65536 | 65536 | |
13 | 1000 | 65536 | 65536 | |
14 | 1000 | 65536 | 65536 | |
15 | 1000 | 65536 | 65536 | |
16 | 1000 | 65536 | 65536 | |
17 | 1000 | 65536 | 65536 | |
18 | 1000 | 65536 | 65536 | |
19 | 1000 | 65536 | 65536 | |
20 | 1000 | 65536 | 65536 | |
21 | 1000 | 65536 | 65536 | |
22 | 1000 | 65536 | 65536 | |
23 | 1000 | 65536 | 65536 | |
24 | 1000 | 65536 | 65536 | |
25 | 1000 | 65536 | 65536 | |
26 | 1000 | 65536 | 65536 | |
27 | 1000 | 65536 | 65536 | |
28 | 1000 | 65536 | 65536 | |
29 | 1000 | 65536 | 65536 | |
30 | 1000 | 65536 | 65536 | |
31 | 1000 | 65536 | 65536 | |
32 | 1000 | 65536 | 65536 | |
33 | 1000 | 65536 | 65536 | |
34 | 1000 | 65536 | 65536 | |
35 | 1000 | 65536 | 65536 | |
36 | 1000 | 65536 | 65536 | |
37 | 1000 | 65536 | 65536 | |
38 | 1000 | 65536 | 65536 | |
39 | 1000 | 65536 | 65536 | |
40 | 1000 | 65536 | 65536 | |
41 | 1000 | 65536 | 65536 | |
42 | 1000 | 65536 | 65536 | |
43 | 1000 | 65536 | 65536 | |
44 | 1000 | 65536 | 65536 | |
45 | 1000 | 65536 | 65536 | |
46 | 1000 | 65536 | 65536 | |
47 | 1000 | 65536 | 65536 | |
48 | 1000 | 65536 | 65536 | |
49 | 1000 | 65536 | 65536 | |
50 | 1000 | 65536 | 65536 | |
51 | 1000 | 65536 | 65536 |