在維克波利斯夜市中,有一個著名的攤位會不定期舉辦一個禮品活動。
這個禮品活動流程如下:一開始,攤位主會把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|$是否成立。
最後,如果有人可以正確的找出所有有放禮品的箱子是哪些,就可以獨得這些獎品。
聰明的你一下就看出了這個遊戲的精髓。你決定要以一己之力拿到所有的獎品。
本題是互動題,沒有輸入,請#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 |
本題沒有輸出。若你輸出了任何東西,你將會獲得一個WA。
改編自CF 809B(推廣)
Problem set / Description by Yidha Yol
No. | Testdata Range | Score |
---|---|---|
1 | 0~3 | 10 |
2 | 0~7 | 14 |
3 | 8~11 | 16 |
4 | 12~15 | 9 |
5 | 0~19 | 51 |