A Certain Forbidden Index

**这是一道函数式交互题。本题仅支持 C++ 提交。（出于某些原因，请不要使用 GCC 9 提交）** **本地编译、提交时请在程序里加入以下函数声明语句：** ```cpp int query(int, int); ``` **任何在赛时攻击交互库而得分的行为均视为作弊。**

有一个长为 $n=2^k$ 的序列，基于这个序列建立了一棵[线段树](https://oi-wiki.org/ds/seg/)。现在线段树上有恰好一个节点被标记了。 你可以进行若干次询问，每次询问给定一个区间 $[l,r]$，交互库会在被修改的线段树上进行一次区间查询，你可以得知在被修改的线段树上这个区间对应的所有节点中，是否有节点被标记。 你需要在尽可能少的询问内找到这个节点。具体而言，若最优策略在最坏情况下需要 $Q$ 次询问，则你最多可以使用 $Q$ 次询问。 ### 交互流程 你不需要，也不应该实现主函数，你只需要实现如下函数： ```cpp std::pair<int, int> solve(int k); ``` 该函数需要在得到答案后返回一个数对 $(x,y)$，表示被标记的线段树节点所对应的区间为 $[x,y]$。 你可以调用交互库提供的方法： ```cpp int query(int l, int r); ``` 传入的 `l` 和 `r` 代表询问的区间为 $[l,r]$。交互库会返回对应的结果。你需要保证 $1\le l\le r\le n$。具体而言： - 当没有节点被标记时，交互库返回 $0$； - 当有节点被标记时，交互库返回 $1$； - 当询问的区间不合法时，交互库会返回 $-1$，此时你需要立即结束这组数据的交互（不是整个测试点），否则可能导致不可预知的错误。 本题无询问次数限制，但过多的询问会导致时间超限，详细信息请看“数据规模与约定”。

下面给出样例交互库的输入输出格式： 第一行输入一个整数 $T$，表示数据组数。 对于每组数据，第一行输入三个整数 $k,l,r$ 代表 $n=2^k$，且将对应区间为 $[l,r]$ 的线段树节点修改。 注意样例交互库不会检查输入数据的正确性。

对于每组数据，如果你得到的答案正确，输出一个整数表示你使用的交互次数，否则： - 若你的询问不合法，输出 `Wrong Answer [1]`； - 若你返回的区间不正确，输出 `Wrong Answer [2]`。

2
2 1 1
2 3 4

1
2

#### 样例 1 解释 下面是一种可能的交互流程： | 交互库 | 选手程序 | 备注 | | :----------: | :----------: | :----------: | | 调用 `solve(2)` | | 开始测试 | | 返回 $1$ | 调用 `query(1,1)` | $[1,1]$ 就是答案节点 | | | 返回 $(1,1)$ | 答案正确 | | 调用 `solve(2)` | | 开始下一组数据的评测 | | 返回 $1$ | 调用 `query(2,4)` | $[2,4]$ 对应的节点是 $[2,2]$ 和 $[3,4]$，包括了答案节点 | | 返回 $0$ | 调用 `query(1,4)` | $[1,4]$ 对应的节点只有 $[1,4]$，不包括答案节点 | | | 返回 $(3,4)$ | 答案正确，评测结束 | ### 计分方式 本题首先会受到和传统题相同的限制。例如编译错误会导致整道题目得 $0$ 分，运行时错误、超过时间限制、超过空间限制等会导致相应测试点得 $0$ 分等。 如果你找到的节点是错误的，或者你给出的询问不合法，在该测试点将会得到 $0$ 分。 否则，设在一组数据中，答案最坏需要 $x$ 次询问，而你使用了 $y$ 次询问，满分为 $t$，则这组数据的分数是 $t\times \min\left(1,\mathrm{e}^{-\frac{y}{x}+1}\right)$。 每个测试点取所有数据组中得分的最小值，向下保留两位小数。你的得分是所有测试点得分之和。 ### 数据规模与约定 对于所有数据，保证 $1\le k\le 14$，$1\le T\le 300$。 本题共 $14$ 个测试点，对于第 $i$ 个测试点，保证 $k=i$。对于 $1\le k\le 4$ 的测试点，满分 $10$ 分。对于 $5\le k\le 14$ 的测试点，满分 $6$ 分。 保证在每组数据进行 $2n$ 次询问时，单个测试点内，交互库使用的时间不超过 0.6s，空间不超过 8MiB。 ### 下发文件说明 下发文件中有一个可以通过样例的程序示例 `sample.cpp`，以及一个样例交互库 `grader.cpp`。假设你的答案文件为 `answer.cpp`，则可以使用如下命令将其编译成可执行文件 `answer`： ```shell g++ grader.cpp answer.cpp -o answer -O2 ``` 实际评测时的交互库可能是自适应的，即被修改的节点可能不会在交互一开始时确定。