P9683 A Certain Forbidden Index

**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:** ```cpp int query(int, int); ``` **Any behavior that attacks the interactive library to gain points during the contest will be considered cheating.**

There is a sequence of length $n=2^k$, and a [segment tree](https://oi-wiki.org/ds/seg/) 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: ```cpp std::pair 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: ```cpp 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”.

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.

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

#### Explanation for Sample 1 Below is one possible interaction procedure: | Interactive Library | Participant Program | Note | | :----------: | :----------: | :----------: | | Call `solve(2)` | | Start testing | | Return $1$ | Call `query(1,1)` | $[1,1]$ is the answer node | | | Return $(1,1)$ | Correct answer | | Call `solve(2)` | | Start judging the next test case | | Return $1$ | Call `query(2,4)` | The nodes corresponding to $[2,4]$ are $[2,2]$ and $[3,4]$, which include the answer node | | Return $0$ | Call `query(1,4)` | The only node corresponding to $[1,4]$ is $[1,4]$, which does not include the answer node | | | Return $(3,4)$ | Correct answer, judging ends | ### 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: ```shell 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