# 题解：子串询问恢复排列 贡献：出题人解法提供重复枢轴的邻接探测、二分找邻居和双向延伸思路。Codex（GPT-6）给出端点搜索顺序及741次询问上界，补齐协议、实现、交互器和验证。 ## 用公共子串探测邻接 取枢轴 $u$ 和互异候选 $c_1,\ldots,c_s$ ，询问 $$[u,c_1,u,c_2,\ldots,u,c_s,u].$$ 其长度为 $2s+1$ ，取 $s\le49$ .回复至少2，当且仅当某候选在隐藏排列中与 $u$ 相邻。因为询问中的每对相邻元素都包含 $u$ ，不可能由两个无关候选产生假匹配。回复可能为3，但只需判断是否至少2。 出题人方案以此检查候选集合，二分定位邻居，先确定枢轴两侧邻居的方向，再沿左右两端继续找未使用邻居。这里保留同一探测原理，将延伸安排成先右后左，从而只需一次可能失败的端点搜索。 ## 初始化和延伸 $n=1$ 时直接回答。否则从1开始，在其余标签中寻找一个邻居。该集合保证有解，二分时每次测试至多49个候选；询问 `[1,v]` 可确定找到的邻居 $v$ 位于哪侧。此时已知一个方向正确的连续片段。 向右延伸时，端点 $u$ 的左邻居已经使用，未使用标签中只有它的右邻居可能与其相邻。对候选子集询问 $$[u,c_1,u,c_2,\ldots,u,c_s],\qquad s\le50.$$ 回复至少2等价于右邻居在该子集中。向左延伸则改问 $[c_1,u,c_2,u,\ldots,c_s,u]$ . 搜索须保留“没有邻居”这个可能结果。尚不知道是否存在邻居、候选数为 $U$ 时，测试 $\min(50,\lfloor(U+1)/2\rfloor)$ 个候选。肯定回复排除“没有”，并进入已知存在的普通二分；否定回复删去所测候选。空集表示找到了排列端点。 先持续向右延伸。第一次发现右邻居不存在后，改为向左延伸；所有剩余标签都位于左侧，因此再无失败搜索。只有一个候选但尚未证明存在时，也必须询问。 ## 正确性与询问上界 初始化得到正确的连续片段。每次成功搜索找到该片段的直接前驱或后继，所以扩展后仍是正确片段。右侧失败只可能意味着已到全排列的右端；随后左侧必可容纳所有剩余标签。最终片段包含全部标签，故是隐藏排列。 初始化至多8次邻居探测、1次方向探测。每次成功延伸消耗一个未使用标签；$U$ 从至多118递减到1。若 $U\le100$ ，把“没有”视为一个额外结果，可在 $\lceil\log_2(U+1)\rceil$ 次内完成。$100100]\right)+8=741<800.$$ 所有询问长至多100。无需依赖随机排列或实测平均询问数。 ## 实现与测试 [std.cpp](std.cpp) 是提交程序，[solver.hpp](solver.hpp) 保存算法。每个询问都刷新输出，读到 $-1$ 或输入结束立即退出。程序只读取 $n$ 和评测回复。 [judge.py](judge.py) 持有隐藏排列并通过管道与程序交互，验证格式、次数、最终答案、退出和多余输出。[simulate.cpp](simulate.cpp) 只用于离线验证共享算法，它可以读隐藏排列，不能作为交互提交。使用方法见[测试说明](tests/README.md)。 设 $Q$ 为询问次数，$L$ 为最长询问长度。候选维护和构造所需时间为 $O(n^2+QL)$ ，辅助空间 $O(n+L)$ .性能测量运行真实交互，墙钟时间包含Python交互器和管道开销；内存只测提交进程。 ## 性能 正式数据每份运行五次并另测峰值。标准程序最慢中位数 0.074435 秒，峰值 5.28 MiB；按2倍取整到0.5秒，时限为 0.5 秒。 [环境说明](../../../docs/评测环境与性能.md)与[逐次测量](../../../docs/benchmark-R34.json)可供复现；其他环境需重新校准。