P8111 [Cnoi2021] Interval.

Cirno has an interval $[a,b](1\le a \le b \le n)$, and your task is to help Rumia guess this interval within the required number of queries. Each time, you may ask Cirno about a number $k$, and Cirno will tell you the relationship between this number and the interval $[a,b]$.

To guess this interval, you need to implement a function `std::pair Guess(int n,int c)`. This function must correctly determine a closed sub-interval $[a,b]$ of $[1,n]$ using at most $c$ queries, and return the interval you finally determine in the form of `std::pair`. You may call a function in the interactive library called `Query`, with the prototype `int Query(int x)`. Its return value is: - If $x < a$, return $-1$. - If $x \in [a,b]$, return $0$. - If $x > b$, return $1$. You must call `Query` no more than $c$ times to get the score for that test point; otherwise, the score for that test point is $0$. For how to call this function, please refer to the “Notes / Hint” section. Within one test point, your `Guess` function may be called multiple times, up to at most $5000$ times. To ensure your program does not time out, you also need to implement a function `void init()`. This function will be called only once by the interactive library at the beginning. Of course, its implementation may be empty. Since Rumia’s compiler only supports C++, you may only use C++ (including C++, C++11, C++14, C++17) to solve this problem.

In the sample, four numbers $n$, $a$, $b$, $c$ are given as input. You cannot read these numbers.

In the sample, three numbers $l$, $r$, $q$ are given as output, representing the interval you guessed and the number of `Query` calls. You do not need to output these.

**Sample Explanation** The interval to be found is $[2,3]$. The possible range of the left and right endpoints is $[1,5]$, and you can guess at most $5$ times. **Constraints and Conventions** For all testdata, it is guaranteed that $1 \le a \le b \le n$; except for SubtaskExtra, it is guaranteed that $1\le n\le1500$. **Subtasks** Subtask1 ($10$ points): $c=n$. Subtask2 ($30$ points): $c=30$. Subtask3 ($30$ points): $c=22$. Subtask4 ($30$ points): $c=20$. **Extra Task** SubtaskExtra ($1$ point): $1\le n\le 10^6$, $c=\lfloor\log_2 n\rfloor+\lfloor\log_2 \frac{4n}{3}\rfloor$. This problem uses Special Judge. Both $100$ and $101$ points are considered Accepted. **Notes** If you do not know how to solve interactive problems, you may refer to [this problem](https://www.luogu.com.cn/problem/P1947). The template program and the template interactive library for this problem can be found in the attachments `SampleProgram.cpp` and `SampleInteractor.cpp`. # Input Format # Output Format Translated by ChatGPT 5