TopCoder

喵喵
貓咪好可愛 <3

User's AC Ratio

50.0% (2/4)

Submission's AC Ratio

20.5% (8/39)

Tags

Description

在維克波利斯夜市中,有一個著名的攤位會不定期舉辦一個禮品活動。

這個禮品活動流程如下:一開始,攤位主會把N個箱子一字排開,從左到右編號為0到N-1,兩個相鄰箱子之間的距離都相同。接著,其中的一些箱子中會被放入禮品,但是獎品在哪裡只有攤位主知道,圍觀群眾並不知道。

之後,任何人都可以付費參加這個活動。一個人可以依序講出兩個數字$x,y(0\leq x,y<N)$,接著攤位主就會回答x號箱子距離有禮品的箱子的距離是否小於y號箱子距離有禮品的箱子的距離。
換句話說,如果離x,y號箱子最近有禮品的箱子編號分別是a,b(注意有可能$x=a$或$y=b$或$a=b$),那麼攤位主會回答$|x-a|<|y-b|$是否成立。

最後,如果有人可以正確的找出所有有放禮品的箱子是哪些,就可以獨得這些獎品。

聰明的你一下就看出了這個遊戲的精髓。你決定要以一己之力拿到所有的獎品。

Input Format

本題是互動題,沒有輸入,請#include "lib1983.h"之後使用裡面的函數與攤位主互動。

你可以呼叫以下幾個函數:
long long Init();:此函數要在一開始的時候呼叫,並傳回全部的箱子數量N。
int Ask(long long x, long long y);:依序講出兩個數字x, y,並得到攤位主的回答。如果回答是「是」,那麼這個函數將回傳1;否則這個函數將回傳0。如果$0\leq x,y < N$不成立,你將會獲得一個WA。
void Answer(int k, long long* Ans);:傳入一個數字k與一個整數陣列Ans,代表你認為總共有k個箱子裡面有禮品,編號由小到大分別是Ans[0], Ans[1], ..., Ans[k-1]。這個函數會幫你結束程式。

以下以$N$代表箱子數量、$K$代表有放禮品的箱子數量。
對於所有測資,$N\leq 5\times 10^ {18},K\leq 10^ 5$。

子任務(測資) 額外限制 分數
1 (0~3) $N\leq 5000$ 10
2 (0~7) $N\leq 10^ 6$ 14
3 (8~11) $K=1$ 16
4 (12~15) $K=2$ 9
5 (0~19) 無限制 51

Output Format

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

Hints

Problem Source

改編自CF 809B(推廣)
Problem set / Description by Yidha Yol

Subtasks

No. Testdata Range Score
1 0~3 10
2 0~7 14
3 8~11 16
4 12~15 9
5 0~19 51

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 800 32768 262144 1 2 5
1 800 32768 262144 1 2 5
2 800 32768 262144 1 2 5
3 800 32768 262144 1 2 5
4 800 32768 262144 2 5
5 800 32768 262144 2 5
6 800 32768 262144 2 5
7 800 32768 262144 2 5
8 800 32768 262144 3 5
9 800 32768 262144 3 5
10 800 32768 262144 3 5
11 800 32768 262144 3 5
12 800 32768 262144 4 5
13 800 32768 262144 4 5
14 800 32768 262144 4 5
15 800 32768 262144 4 5
16 800 32768 262144 5
17 800 32768 262144 5
18 800 32768 262144 5
19 800 32768 262144 5