背景

题目来源：【HT-129-Div.1】核桃省选模拟赛

提交到洛谷上时，无需引用头文件 #include "reversal.h"。直接将

std::pair<int, int> solve(int n);
int query(const std::string &S);

复制到程序开头，同时选用 C++17 或者更高版本编译器编译。

题目描述

这是一道函数式交互题。

交互库中有一个隐藏的区间 $[l,r]$，其中 $1\le l<r\le n$。

你需要通过调用交互函数 query，还原这个隐藏区间。

每次询问时，你可以给出一个长度为 $n$ 的 01 字符串 $S$。交互库会将 $S$ 的第 $l$ 至第 $r$ 个字符按顺序反转，得到字符串 $S'$。

若 $S=S'$，交互库返回 $0$。

否则，设 $T=\{p\mid S_p\ne S'_p\}$，交互库会返回 $\min T$ 或 $\max T$ 中的任意一个。

对于每次询问，交互库均可以任意选择返回 $\min T$ 或 $\max T$。你可以认为交互库会采用对你的程序最不利的策略。

你需要在至多 $15$ 次询问内确定隐藏区间 $[l,r]$。若使用不超过 $5$ 次询问，则可以获得该测试点的全部分数。

【实现细节】

选手不需要实现 main 函数或 query 函数。

提交代码时，请包含：

#include "reversal.h"

并实现以下函数：

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

其中，$n$ 表示字符串的长度。你需要在 solve 中调用交互库提供的函数：

int query(const std::string &S);

传入的字符串 $S$ 必须满足：

• S.size() == n。
• $S$ 中仅包含字符 '0' 和 '1'。

交互库会将 $S$ 的第 $l$ 至第 $r$ 个字符按顺序反转，得到字符串 $S'$。

若 $S=S'$，则 query(S) 返回 $0$；否则，设 $T=\{p\mid S_p\ne S'_p\}$，则 query(S) 返回 $\min T$ 或 $\max T$ 中的任意一个。

所有位置均从 $1$ 开始编号。

最终，solve 应返回 {l, r}，表示你认为隐藏区间为 $[l,r]$。

评测程序可能在同一次运行中多次调用 solve。每次调用对应一组相互独立的数据，交互库的状态与询问次数会在调用前重置。

【本地测试】

题目附件中提供以下文件：

• reversal.h：函数式交互接口。
• grader.cpp：本地测试用 grader。
• sample.in：本地测试输入示例。

假设你的代码文件名为 solution.cpp，将 solution.cpp、reversal.h 和 grader.cpp 放在同一目录下，使用以下命令编译：

g++ -std=c++17 -O2 solution.cpp grader.cpp -o solution

Linux 下可以使用以下命令运行：

./solution < sample.in

Windows cmd 中可以使用：

g++ -std=c++17 -O2 solution.cpp grader.cpp -o solution.exe
solution.exe < sample.in

【交互限制】

对于每一组数据：

• solve 最多调用 query $15$ 次。
• 若调用次数超过 $15$，该组数据判定为错误。
• 若传给 query 的字符串长度不为 $n$，或包含 '0'、'1' 以外的字符，该组数据判定为错误。
• solve 返回的答案必须满足 $1\le l<r\le n$。
• 若返回的区间不等于交互库隐藏的区间，该组数据判定为错误。

输入格式

【测试程序方式】

sample.in 的格式为：

n l r mask

其中，$[l,r]$ 为本地 grader 使用的隐藏区间。

若第 $k+1$ 次 query 的合法非零回复为 $\min T$ 和 $\max T$，则 mask 从低到高的第 $k$ 个二进制位决定返回哪一个：该位为 $0$ 时返回 $\min T$，为 $1$ 时返回 $\max T$。

若该次询问返回 $0$，对应二进制位不会影响结果。

若需要覆盖前 $5$ 次询问的全部左右回复方式，可以固定 $n,l,r$，并令 mask 依次取 $0,1,\ldots,31$。

本地 grader.cpp 仅用于调试；正式评测使用更强的对抗交互库，但 reversal.h 中的接口完全相同。

提示

【数据范围】

本题共有 $3$ 个测试点。一个测试点中的所有数据组均需正确完成，否则该测试点得 $0$ 分。

测试点编号	分值	$n\le$
$1$	$10$
$2$	$20$	$10^3$
$3$	$70$	$2\times 10^5$

对于 $100\%$ 的数据，保证 $2\le n\le 2\times 10^5$。

【评分方式】

对于一个答案全部正确的测试点，设第 $i$ 组数据使用了 $Q_i$ 次询问，并令

$$Q=\max_i Q_i.$$

定义

$$f(Q)= \begin{cases} 1, & Q\le 5,\\ 0.8^{Q-5}, & 6\le Q\le 15. \end{cases}$$

若该测试点的分值为 $\mathrm{score}$，则你在该测试点获得 $\lfloor f(Q)\cdot \mathrm{score} \rfloor$ 分。

若某一组数据中答案错误、调用 query 的格式不合法、询问次数超过上限，或程序发生其他错误，则整个测试点得 $0$ 分。