P8111 [Cnoi2021] 区间

Cirno 有一个区间 $[a,b](1\le a \le b \le n)$，而你的任务是在规定的次数内帮 Rumia 猜出这个区间。 每次，你可向 Cirno 询问一个数字 $k$，而 Cirno 会告诉你这个数字与区间 $[a,b]$ 的关系。

为了猜到这个区间，你需要实现一个函数 `std::pair Guess(int n,int c)`，这个函数的作用是在不超过 $c$ 次询问中猜对 $[1,n]$ 中的一个子闭区间 $[a,b]$，返回值为你最终确定的区间，以 `std::pair` 的形式返回。 你可以调用交互库中一个叫做 `Query` 的函数，其原型为 `int Query(int x)`，返回值为： - 若 $x < a$，返回 $-1$。 - 若 $x \in [a,b]$，返回 $0$。 - 若 $x > b$，返回 $1$。 你调用 `Query` 函数的次数不超过 $c$ 才能得到这个点的分数，否则这个点为 $0$ 分。有关该函数的调用请参考「说明/提示」部分。 在一个测试点中，你的 `Guess` 函数可能被调用多次，最多不超过 $5000$ 次。为了保证你的程序不会超时，你需要额外实现一个函数 `void init()`，这个函数只会在开始时被交互库调用一次。当然，它的实现可以为空。 由于 Rumia 的编译器只支持 C++，所以你只能使用 C++ 语言（包括 C++，C++11，C++14，C++17）来解决本题。

样例中输入四个数字 $n$，$a$，$b$，$c$。这些数字你无法读取。

样例中给输出三个数字 $l$，$r$，$q$。分别表示你猜的区间与 `Query` 调用测次数。这些你不用输出。

**样例解释** 需要求的区间是 $[2,3]$，区间左右端点可能的范围是 $[1,5]$，你最多猜 $5$ 次。 **数据范围与约定** 对于所有数据保证 $1 \le a \le b \le n$；除 SubtaskExtra 外，保证 $1\le n\le1500$。 **子任务** Subtask1（$10$ points）：$c=n$。 Subtask2（$30$ points）：$c=30$。 Subtask3（$30$ points）：$c=22$。 Subtask4（$30$ points）：$c=20$。 **附加任务** SubtaskExtra（$1$ point）：$1\le n\le 10^6$，$c=\lfloor\log_2 n\rfloor+\lfloor\log_2 \frac{4n}{3}\rfloor$。 本题使用 Special Judge，$100$ 与 $101$ 分均视作 Accepted. **提示** 如果你不知道怎么解决交互题，可以参考[这题](https://www.luogu.com.cn/problem/P1947)。 本题模板程序与模板交互库见附件中的 `SampleProgram.cpp` 与 `SampleInteractor.cpp`。