User's AC Ratio

66.7% (2/3)

Submission's AC Ratio

15.0% (3/20)

Description

本題為互動題,僅限使用 C/C++ 作答

有一個電腦叢集,裡面有 $N$ 台電腦,可以想像成 $N$ 個電腦排成一排,
而其中有一些電腦壞掉了,你想要找到是哪些電腦壞掉才方便維修,
這些電腦是叢集電腦,因此會互相知道其他電腦的狀況,
你想透過對某些電腦詢問來得知壞掉的電腦是哪些。

你每次可以對一台電腦詢問 $[l,r]$ 之間是否有電腦壞掉,
不過如果對壞掉的電腦查詢,有可能會得到錯誤的結果,
且因為電腦叢集不穩定的關係,你最多只可以執行 $300019$ 次的詢問操作
你希望可以找到任意一台壞掉電腦的位置在哪。
保證至少有一台電腦是壞掉的,且沒壞的電腦數量大於 $\frac{N}{2}$。

本題測資為動態生成,每筆 submission 的測資可能不同。

Input Format

本題沒有輸入,若你輸入了任何東西,可能會導致各種不可預期的結果。

請記得 #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]$。這個函式會自動幫你結束程式。

  • $3\leq N\leq 3\times10^5$

Output Format

本題沒有輸出,若你輸出了任何東西,你將會得到一個 WA

Sample Input 1

注意:本題沒有輸入,本輸入僅供範例標頭檔使用 (參見 Hints)

10
1 1 1 0 1 0 1 1 0 1

Sample Output 1

注意:本題沒有輸出,本輸出僅供範例標頭檔使用 (參見 Hints)

Successfully fix a computer.
Totally make %d queries.

Sample Input 2

注意:本題沒有輸入,本輸入僅供範例標頭檔使用 (參見 Hints)

15
1 1 1 0 0 1 0 0 1 1 0 1 0 1 1

Sample Output 2

注意:本題沒有輸出,本輸出僅供範例標頭檔使用 (參見 Hints)

Successfully fix a computer.
Totally make %d queries.

Hints

這裡提供一份範例標頭檔可以使用。

若在本機使用這份標頭檔執行時,輸入格式如下:

第一行會有一個數字 $N$,代表電腦數量。
接下來一行有 $N$ 個數字,第 $i$ 個數字 $c_i$ 代表第 $i$ 台電腦狀態,若 $c_i=0$ 則代表該電腦壞掉了,否則 $c_i=1$。

如果你的程式被評為 WA,範例評分程式會輸出 "Wrong Answer: MSG",其中 MSG 格式與意義如下:

  • Out of range:代表你詢問的區間不合法
  • Too many queries:代表你的詢問次數過多
  • Not broken computer:代表你選到的電腦不是壞掉的電腦

Problem Source

Subtasks

No. Testdata Range Score
1 0~51 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 65536 65536 1
1 1000 65536 65536 1
2 1000 65536 65536 1
3 1000 65536 65536 1
4 1000 65536 65536 1
5 1000 65536 65536 1
6 1000 65536 65536 1
7 1000 65536 65536 1
8 1000 65536 65536 1
9 1000 65536 65536 1
10 1000 65536 65536 1
11 1000 65536 65536 1
12 1000 65536 65536 1
13 1000 65536 65536 1
14 1000 65536 65536 1
15 1000 65536 65536 1
16 1000 65536 65536 1
17 1000 65536 65536 1
18 1000 65536 65536 1
19 1000 65536 65536 1
20 1000 65536 65536 1
21 1000 65536 65536 1
22 1000 65536 65536 1
23 1000 65536 65536 1
24 1000 65536 65536 1
25 1000 65536 65536 1
26 1000 65536 65536 1
27 1000 65536 65536 1
28 1000 65536 65536 1
29 1000 65536 65536 1
30 1000 65536 65536 1
31 1000 65536 65536 1
32 1000 65536 65536 1
33 1000 65536 65536 1
34 1000 65536 65536 1
35 1000 65536 65536 1
36 1000 65536 65536 1
37 1000 65536 65536 1
38 1000 65536 65536 1
39 1000 65536 65536 1
40 1000 65536 65536 1
41 1000 65536 65536 1
42 1000 65536 65536 1
43 1000 65536 65536 1
44 1000 65536 65536 1
45 1000 65536 65536 1
46 1000 65536 65536 1
47 1000 65536 65536 1
48 1000 65536 65536 1
49 1000 65536 65536 1
50 1000 65536 65536 1
51 1000 65536 65536 1