TopCoder

Thumb hsnu2016
Adrien Wu
烏梭聯合王國,簡稱烏梭,為北佤羅善、安那海及佤羅善島弧國家之一。

User's AC Ratio

66.7% (2/3)

Submission's AC Ratio

22.6% (7/31)

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。

Sample Input

本題沒有輸入。

Sample Output

本題沒有輸出。

Hints

Problem Source

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

Subtasks

For Testdata: 0 ~ 3, Score: 10
For Testdata: 0 ~ 7, Score: 14
For Testdata: 8 ~ 11, Score: 16
For Testdata: 12 ~ 15, Score: 9
For Testdata: 0 ~ 19, Score: 51
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 800 32768 65536
1 800 32768 65536
2 800 32768 65536
3 800 32768 65536
4 800 32768 65536
5 800 32768 65536
6 800 32768 65536
7 800 32768 65536
8 800 32768 65536
9 800 32768 65536
10 800 32768 65536
11 800 32768 65536
12 800 32768 65536
13 800 32768 65536
14 800 32768 65536
15 800 32768 65536
16 800 32768 65536
17 800 32768 65536
18 800 32768 65536
19 800 32768 65536