这是一道交互题
蒜斜的手里有一个01串
你的每个询问都要花费一定的代价。蒜斜并没有学过高级字符串算法,只能用暴力法来回答你的询问。对于越困难的询问,蒜斜需要的思考时间越长,花费代价也就越大。对于一次询问
你的任务是通过向蒜斜进行若干次询问,来判断
交互格式
本题只支持 c++
。
你需要包含头文件 interactor.h
。
你不需要,也不应该实现主函数,你只需要实现如下一个函数:
int solve(int alen, std::vector<int> b, int C, int S);
- 你可以在这个函数内发起若干次对蒜斜的询问。
- 参数
alen
表示01串 的长度。 - 参数
b
是一个仅包含0和1的数组,表示01串 。 - 参数
C
和S
的意义如题面中所述。 - 你的答案应该作为这个函数的返回值。
你可以通过如下函数发起对蒜斜的询问:
std::pair<int,int> query(int l, int r, std::vector<int> s);
- 参数
l
和r
的意义如题面中所述。 - 参数
s
是至少包含一个元素的整数数组,表示你的询问串 。 数组中只允许包含整数 ,其中 表示通配符。 - 返回值是一个
pair<int,int>
,其中第一个元素表示最小的下标 ,第二个元素表示最大的下标 。如果不存在这样的下标,则两个元素均为 。
- 参数
本题保证所使用的程序以及询问的值在交互开始之前已经完全确定,不会根据和你的程序的交互过程动态构造,因此题目中的交互操作都是确定性的,你不需要关心这些操作在交互库中的具体实现。
数据保证在总代价限制下,交互库运行所需的时间不超过 1s;交互库使用的内存大小固定,且不超过 64 MB。
测试程序方式
试题目录下的 grader.cpp
是我们提供的交互库参考实现,最终测试时所用的交互库实现与该参考实现有所不同,因此选手的解法不应该依赖交互库实现。
- 你需要在本题目录下使用如下命令编译得到可执行程序:
g++ grader.cpp sample.cpp -o sample -O2 -lm
- 对于编译得到的可执行程序:
- 可执行文件将从标准输入读入以下格式的数据:
- 第一行包含字符串
- 第二行包含字符串
- 第三行包含整数
- 第四行包含整数
- 第一行包含字符串
- 读入完成之后,交互库将调用恰好一次函数
。你的函数正确返回后,交互库会判断你的计算是否正确,若正确则会输出AC
以及所用的总代价,否则会输出相应的错误信息。
- 可执行文件将从标准输入读入以下格式的数据:
试题目录下有出题人提供的一份参考代码 sample.cpp
,注意这份代码 无法通过任何测试用例 。
数据范围
本题严禁任何形式的攻击交互库的行为,一旦发现,将取消相关选手的参赛资格。
Small Task: 串
Large Task: 无特殊限制
对于所有测试数据,保证
时间限制:
空间限制: