1983 . 禮品問題
TopCoder
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 |