English Problem Statement

去年元夜时，花市灯如昼。月上柳梢头，人约黄昏后。

今年元夜时，月与灯依旧。不见去年人，泪湿春衫袖。

这是一道交互题。仅支持使用 C++ 语言（版本不低于 C++ 14）提交。

题目描述

在跳蚤王国的古老传说中，尘雨巷是一条被迷雾笼罩的环形秘巷。每当雨季来临，尘埃与水雾交织成帘，巷中的 $n$ 盏魔法灯若隐若现。作为伏特国王最信任的探险家，你被传送至某盏魔法灯前——你既不知道巷子的长度 $n$，也不知道初始位置和魔法灯的状态。雨季结束前，你必须完成伏特给你的任务——勘破巷子的长度 $n$！

尘雨巷是一个长度为 $n$ 的环形巷子。这个巷子中排列着 $n$ 盏魔法灯，每盏魔法灯可能为开启状态或关闭状态。一开始，你被传送到其中一盏魔法灯面前，但是你并不知道你的面前是哪一盏魔法灯，也不知道每个魔法灯目前的状态。

为了勘破巷子的长度 $n$，你可以使用若干次魔法，每次魔法是下面的四种之一：

• 雨幕穿行（顺）：顺时针移动到下一盏魔法灯面前，消耗 $1$ 点体力；
• 雨幕穿行（逆）：逆时针移动到下一盏魔法灯面前，消耗 $1$ 点体力；
• 尘埃之窥：查询你面前的魔法灯的状态，消耗 $1$ 点体力；
• 雾中秘仪：改变你面前的魔法灯的状态（即将开启状态变为关闭状态，将关闭状态变为开启状态），不消耗体力。

由于你的时间有限，你必须在雨季结束前（至多使用 $2 \times 10^6$ 次魔法）求出巷子的长度 $n$。此外，伏特国王还将根据你花费的体力点数多少授予不同的奖赏，具体见“子任务”部分。

实现细节

选手不需要，也不应该实现 main 函数。

选手应确保提交的程序包含头文件 lane.h，可在程序开头加入以下代码实现：

#include "lane.h"

选手需要实现以下函数：

int solve(int c);

• $c$ 表示伏特国王颁布的子任务编号；
• 该函数需要返回 $n$ 的值，表示巷子的长度 $n$；
• 由于伏特国王可能要求你进行多次探险，因此对于每个测试点，该函数可能会被交互库调用多次。

选手可以通过调用以下函数向交互库发送一次魔法的使用：

void clockwise();

• 调用该函数表示使用魔法“雨幕穿行（顺）”：消耗 $1$ 点体力，顺时针移动到下一盏魔法灯面前。

void anticlockwise();

• 调用该函数表示使用魔法“雨幕穿行（逆）”：消耗 $1$ 点体力，逆时针移动到下一盏魔法灯面前。

bool ask();

• 调用该函数表示使用魔法“尘埃之窥”：消耗 $1$ 点体力，查询你面前的魔法灯的状态；
• 该函数会返回一个 bool 类型的值：若魔法灯是开启状态，则返回 true，否则返回 false。

void flip();

• 调用该函数表示使用魔法“雾中秘仪”：不消耗体力，改变你面前的魔法灯的状态（即将开启状态变为关闭状态，将关闭状态变为开启状态）。

测试程序方式

试题目录下的 grader.cpp 是提供的交互库参考实现，最终测试所用的交互库与该参考实现有所不同，因此选手的解法不应该依赖交互库实现。

最终的评测交互库与样例交互库的实现不同，且可能是适应性的：在不与 ask 此前返回的结果相矛盾的前提下，最终的评测交互库可能会动态调整 $n$ 的值和魔法灯的状态。

选手可以在本题目录下使用如下命令编译得到可执行程序：

g++ grader.cpp lane.cpp -o lane -O2 -std=c++14 -static

你也可以添加 -DDEBUG 选项来开启调试模式，此时编译命令如下：

g++ grader.cpp lane.cpp -o lane -O2 -std=c++14 -static -DDEBUG

对于编译得到的可执行程序：

• 可执行文件将从标准输入读入以下格式的数据：
  • 输入的第一行包含两个整数 $c, T$，表示子任务编号和探险次数；
  • 对于每组数据包含两行：
    • 第一行包含一个正整数 $n$；
    • 第二行包含一个由 $n$ 个字符组成的字符串，每个字符都是 0 或者 1，表示从初始位置开始，开关的初始状态（0 表示关闭，1 表示开启）按照顺时针排列得到的数组。
• 对于每组数据，交互库将调用一次函数 solve 进行测试，测试全部完成后，交互库将会输出以下信息：
  • 第一行包含你的得分信息；
  • 第二行包含交互库关于测试结果给出的描述；
• 如果开启了调试模式，交互库会向标准错误流打印每一组数据以及每一次操作的详细信息。请确保开启调试模式时输入的测试数据较小从而避免意外产生。

交互示例

假设 $n = 2$，开关的初始状态为 $[0, 1]$，下面是一个合法的交互过程：

题目附件说明

本题附件中包含：

1. grader.cpp 是提供的交互库参考实现。
2. lane.h 是头文件，选手不用关心具体内容。
3. template_lane.cpp 是提供的示例代码，选手可在此代码的基础上实现。
4. lane1.in、lane2.in 和 lane3.in 是大样例，分别对应三个子任务。

子任务

记总探险次数，即函数 solve 的总调用次数为 $T$；每次探险的巷子长度 $n$ 的总和为 $\sum n$。对于所有测试数据保证：$1 \leq n \leq 10^5$，$1 \leq T \leq 10^6$，$\sum n \leq 10^7$。

伏特国王共颁布了 $3$ 个子任务：

• 初探尘雨（子任务 1，$3$ 分）：
  • 保证 $T \leq 10$；
  • 保证初始状态下所有魔法灯均为关闭状态；
  • 只要对于单个测试点的每次探险，选手程序都使用不超过 $2 \times 10^6$ 次魔法，正确确定巷子的长度 $n$，就可以得到满分；否则不得分。
• 雾锁千巷（子任务 2，$40$ 分）：
  • 保证 $n \leq 2 \times 10^3$，$T \leq 5 \times 10^3$；
  • 对于单个测试点的每次探险，选手程序至多使用 $20n$ 次魔法，否则不得分；
  • 对于单个测试点，设在 $T$ 次探险中，$x$ 表示消耗的体力点数 $q$ 与巷子的长度 $n$ 的比值 $\frac{q}{n}$ 的最大值，则选手程序在该测试点的得分：
    • 若 $x \leq 7.83$，则得到 $40$ 分（满分）；
    • 若 $x > 15$，则得到 $0$ 分；
    • 若 $7.83 < x \leq 15$，则得到 $40 \times \frac{15 - x}{15 - 7.83}$ 分。
• 终勘轮回（子任务 3，$57$ 分）：
  • 无特殊限制；
  • 对于单个测试点的每次探险，选手程序至多使用 $20n$ 次魔法，否则不得分；
  • 若一次探险设消耗的体力点数为 $q$，巷子的长度 $n$，那么伏特对这次探险的满意度为：
    • 若 $n \leq 2 \times 10^3$，则满意度等于 $\frac{q}{2n}$
    • 若 $n > 2 \times 10^3$，则满意度等于 $\frac{q}{n}$
  • 对于单个测试点，设 $x$ 表示在 $T$ 次探险中伏特的满意度的最大值，则选手程序在该测试点的得分：
    • 若 $x \leq 5.35$，则得到 $57$ 分（满分）；
    • 若 $x > 8$，则得到 $0$ 分；
    • 若 $5.35 < x \leq 8$，则得到 $57 \times \frac{8 - x}{8 - 5.35}$ 分。

一个子任务的得分为其中所有测试点得分的最小值，得分向下取整保留两位小数。

题目保证在规定的魔法使用次数限制下，交互库运行所需的时间不超过 $\texttt{3s}$；交互库使用的内存大小固定，且不超过 $\texttt{64MB}$。

提示

注意：

• 选手不应通过非法方式获取交互库的内部信息，如试图直接读取魔法灯的状态，或直接与标准输入、输出流进行交互。此类行为将被视为作弊；
• 最终的评测交互库与样例交互库的实现不同，且可能是适应性的：在不与 ask 此前返回的结果相矛盾的前提下，最终的评测交互库可能会动态调整 $n$ 的值和魔法灯的状态。

本题首先会受到和传统相同的限制，例如编译错误会导致整道题目得 $0$ 分，运行时错误、超过时间限制、超过空间限制都会导致相应测试点得 $0$ 分。选手只能在程序中访问自己定义的和交互库给出的变量或数据，及其相应的内存空间。尝试访问其他位置空间将可能导致编译错误或运行错误。

时间限制： $\texttt{5s}$（交互库至多使用 $\texttt{3s}$）

空间限制： $\texttt{512MB}$（交互库至多使用 $\texttt{64MB}$）