Background

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]$.

Problem Description

To guess this interval, you need to implement a function std::pair<int,int> 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<int,int>.

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.

Input Format

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

Output Format

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.

5 2 3 5

2 3 0

Hint

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.

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