题目描述

Tom 心里想好了若干个整数。33DAI 想把这些数全部问出来，但 Tom 只 allow 他问一种问题：

• 给出一个整数 $y$，问「你想的那个数是否严格大于 $y$」。

本题是函数式交互题。你不需要写 main 函数，只要实现下面两个函数（声明在随题下发的 guess.h 里）：

void init(int t, long long n);
long long guess();

• init(t, n)：每个测试点开始时调用一次。$t$ 是这个测试点里数对的组数，$n$ 说明每组隐藏的数 $x$ 都满足 $1 \le x \le n$。
• guess()：求出当前这一组隐藏的数并返回。评测程序会把它和你实现的函数配合起来，一组一组地问；每组开始时询问次数清零。

你可以调用下面这个函数向评测程序提问：

int query(long long y);

• 返回 $1$ 表示 $x > y$，返回 $0$ 表示 $x \le y$。
• 要求 $0 \le y \le 10^9$，否则本测试点判为 Wrong Answer。

评分方式：记 $M$ 为"这个测试点里，某一组问得最多的次数"。

• 只要有任何一组答错，本测试点得 $0$ 分；
• $M \le 100$ 才有分（$M > 100$ 直接判 Wrong Answer）；
• 令 $k = \lceil \log_2 n \rceil$（二分查找所需的最少次数）。$M \le k$ 得满分； $k < M \le 2k$ 时分数从满分线性降到一半；$2k < M < 4k$ 时从一半线性降到 $0$；$M \ge 4k$ 得 $0$ 分。

输入格式

本题没有传统意义上的输入文件：数据由评测程序（grader）读入，你只要实现上面两个函数。

随题下发的文件（见「附加文件」）：

• guess.h：接口声明；
• grader.cpp：示例评测程序，只用来在本地把你的程序跑起来；
• compile.sh：编译脚本。

本地编译命令（把你自己的代码保存为 foo.cc，与上面三个文件放在同一个目录）：

g++ -o foo foo.cc grader.cpp -O2 -std=c++14

示例 grader 的本地输入格式是：第一行两个整数 $t, n$；之后 $t$ 行每行一个隐藏数。 它会打印每一组用了多少次询问。

注意：示例 grader 只用于本地自测，它的数据格式、数据范围与判分方式都和正式评测不同； 正式评测使用另一份 grader，请以题面写明的接口与规则为准。

输出格式

不需要输出任何东西：guess() 的返回值就是答案，由评测程序收集。

样例

下面是某个测试点（$t = 3$、$n = 10$，隐藏的数依次是 $7, 1, 10$）的一次合法交互过程。

第一组 $x = 7$：

你的程序                评测程序
query(5)      ->        1        （x > 5 成立）
query(8)      ->        0        （x > 8 不成立）
query(6)      ->        1        （x > 6 成立）
query(7)      ->        0        （x > 7 不成立，所以 x = 7）
guess() 返回 7

第二组 $x = 1$：query(5) 返回 0、query(2) 返回 0、query(1) 返回 0，于是返回 $1$。 第三组 $x = 10$：query(5) 返回 1、query(8) 返回 1、query(9) 返回 1、query(10) 返回 0，于是返回 $10$。

本测试点里最多的一组问了 $4$ 次，$k = \lceil \log_2 10 \rceil = 4$，所以 $M = 4 \le k$，得满分。

提示

• 本题是函数式交互题：题面里给出的 guess.h、grader.cpp、compile.sh 会随题目一起下发， 你只需要提交实现 init / guess 的源文件。
• $n$ 最大到 $10^9$，逐一试 $y = 1, 2, 3, \dots$ 需要最多 $10^9$ 次询问，一定会超时/超次数。
• 询问次数很少时才有满分，请想想怎样用最少的询问确定一个 $[1, n]$ 内的整数。

数据范围

对于所有测试数据，保证：

• $1 \le t \le 10$；
• $1 \le n \le 10^9$；
• $1 \le x \le n$。

共 $20$ 个测试点，每个测试点 $5$ 分，按测试点计分（子任务 type: sum）。