Background

This is a functional interactive problem. Only C++ submissions are supported. (For some reason, please do not use GCC 9 to submit.)

When compiling locally and when submitting, please add the following function declaration in your program:

int query(int, int);

Any behavior that attacks the interactive library to gain points during the contest will be considered cheating.

Problem Description

There is a sequence of length $n=2^k$, and a segment tree is built on this sequence. Now, exactly one node on the segment tree is marked.

You may make several queries. In each query, you are given an interval $[l,r]$. The interactive library will perform a range query on the modified segment tree, and you can learn whether, among all nodes corresponding to this interval on the modified segment tree, there is a marked node.

You need to find this node using as few queries as possible. Specifically, if the optimal strategy needs $Q$ queries in the worst case, then you may use at most $Q$ queries.

Interaction Procedure

You do not need to, and should not, implement main. You only need to implement the following function:

std::pair<int, int> solve(int k);

After obtaining the answer, this function should return a pair $(x,y)$, meaning that the interval corresponding to the marked segment tree node is $[x,y]$.

You may call the method provided by the interactive library:

int query(int l, int r);

The parameters l and r mean the query interval is $[l,r]$. The interactive library will return the corresponding result. You must ensure $1\le l\le r\le n$. Specifically:

• When there is no marked node, the interactive library returns $0$.
• When there is a marked node, the interactive library returns $1$.
• When the query interval is invalid, the interactive library returns $-1$. In this case, you must immediately end the interaction for this test case (not the whole test point), otherwise it may cause unpredictable errors.

There is no limit on the number of queries in this problem, but too many queries will cause a time limit exceeded. For details, see “Constraints and Conventions”.

Input Format

The following gives the input and output format of the sample interactive library.

The first line contains an integer $T$, meaning the number of test cases.

For each test case, the first line contains three integers $k,l,r$, meaning $n=2^k$, and the segment tree node corresponding to interval $[l,r]$ is modified.

Note that the sample interactive library will not check the correctness of the input data.

Output Format

For each test case, if your answer is correct, output an integer representing the number of interactions you used. Otherwise:

• If your query is invalid, output Wrong Answer [1].
• If the interval you returned is incorrect, output Wrong Answer [2].

2
2 1 1
2 3 4

1
2

Hint

Explanation for Sample 1

Below is one possible interaction procedure:

Scoring

This problem is first subject to the same restrictions as traditional problems. For example, a compilation error will cause the whole problem to score $0$ points. Runtime errors, exceeding the time limit, exceeding the memory limit, etc., will cause the corresponding test point to score $0$ points.

If the node you find is wrong, or your query is invalid, then you will get $0$ points on that test point.

Otherwise, suppose in one test case, the answer needs $x$ queries in the worst case, and you used $y$ queries. If the full score is $t$, then the score for this test case is $t\times \min\left(1,\mathrm{e}^{-\frac{y}{x}+1}\right)$.

For each test point, take the minimum score among all test cases, and keep two decimal places by rounding down. Your total score is the sum of the scores of all test points.

Constraints and Conventions

For all data, it is guaranteed that $1\le k\le 14$ and $1\le T\le 300$.

This problem has $14$ test points. For test point $i$, it is guaranteed that $k=i$. For test points with $1\le k\le 4$, the full score is $10$ points. For test points with $5\le k\le 14$, the full score is $6$ points.

It is guaranteed that when making $2n$ queries in each test case, within a single test point, the time used by the interactive library does not exceed 0.6s, and the memory does not exceed 8MiB.

Notes About the Provided Files

The provided files include an example program sample.cpp that can pass the sample, and a sample interactive library grader.cpp. Suppose your solution file is answer.cpp. You can compile them into an executable file answer using the following command:

g++ grader.cpp answer.cpp -o answer -O2

In the actual judging, the interactive library may be adaptive, meaning the modified node may not be determined at the beginning of the interaction.

Translated by ChatGPT 5