这是一道交互题

蒜斜的手里有一个01串 $a$， 你的手里有一个01串 $b$。你想知道 $b$ 是否是 $a$ 的一个子串，然而蒜斜并不愿意直接把 $a$ 完整地告诉你，所以你只能向蒜斜发起“带通配符的区间子串匹配”询问：每次你可以给蒜斜一个带通配符的串 $s$（即每个字符可能是$0,1$或通配符），以及两个下标 $0\le l\le r\le |a|-|s|$。蒜斜会回答你最小的和最大的下标 $i\in [l,r]$，使得 $a[i..i+|s|-1]$ 和 $s$ 匹配（通配符可以匹配任意字符），或者告诉你这样的 $i\in [l,r]$ 不存在。注意，字符串的下标从 $0$ 开始。

你的每个询问都要花费一定的代价。蒜斜并没有学过高级字符串算法，只能用暴力法来回答你的询问。对于越困难的询问，蒜斜需要的思考时间越长，花费代价也就越大。对于一次询问 $(s,l,r)$，花费的代价等于 $C+(r-l+1)\cdot w(s)$，其中 $w(s)$ 表示串 $s$ 里的非通配符字符数量，$C$ 是一个给定的参数。

你的任务是通过向蒜斜进行若干次询问，来判断 $b$ 是否是 $a$ 的一个子串。如果是 $b$ 是 $a$ 的子串，请回答任意一个位置 $i$ 使得 $a[i..i+|s|-1]=b$；否则，请回答 $-1$。你的所有询问的总代价不能超过 $S$。

交互格式

本题只支持 c++。

你需要包含头文件 interactor.h。

你不需要，也不应该实现主函数，你只需要实现如下一个函数：

1. int solve(int alen, std::vector<int> b, int C, int S);
   • 你可以在这个函数内发起若干次对蒜斜的询问。
   • 参数 alen 表示01串 $a$ 的长度。
   • 参数 b 是一个仅包含0和1的数组，表示01串 $b$。
   • 参数 C 和 S 的意义如题面中所述。
   • 你的答案应该作为这个函数的返回值。

你可以通过如下函数发起对蒜斜的询问：

1. std::pair<int,int> query(int l, int r, std::vector<int> s);
   • 参数 l 和 r 的意义如题面中所述。
   • 参数 s 是至少包含一个元素的整数数组，表示你的询问串 $s$。 数组中只允许包含整数$0,1,-1$，其中$-1$表示通配符。
   • 返回值是一个 pair<int,int>，其中第一个元素表示最小的下标 $i$，第二个元素表示最大的下标 $i$。如果不存在这样的下标，则两个元素均为 $-1$。

本题保证所使用的程序以及询问的值在交互开始之前已经完全确定，不会根据和你的程序的交互过程动态构造，因此题目中的交互操作都是确定性的，你不需要关心这些操作在交互库中的具体实现。

数据保证在总代价限制下，交互库运行所需的时间不超过 1s；交互库使用的内存大小固定，且不超过 64 MB。

测试程序方式

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

1. 你需要在本题目录下使用如下命令编译得到可执行程序：
   • g++ grader.cpp sample.cpp -o sample -O2 -lm
2. 对于编译得到的可执行程序：
   • 可执行文件将从标准输入读入以下格式的数据：
     • 第一行包含字符串 $a$
     • 第二行包含字符串 $b$
     • 第三行包含整数 $C$
     • 第四行包含整数 $S$
   • 读入完成之后，交互库将调用恰好一次函数 $\mathtt{\text{solve}}$。你的函数正确返回后，交互库会判断你的计算是否正确，若正确则会输出 AC 以及所用的总代价，否则会输出相应的错误信息。

试题目录下有出题人提供的一份参考代码 sample.cpp，注意这份代码 无法通过任何测试用例 。

数据范围

本题严禁任何形式的攻击交互库的行为，一旦发现，将取消相关选手的参赛资格。

Small Task: 串$b$是均匀随机生成的。

Large Task: 无特殊限制

对于所有测试数据，保证$|a|=75000,|b|=50000,C=30000,S=4000000$。

时间限制: $2\mathtt{\text{s}}$

空间限制: $512\mathtt{\text{MB}}$

下载

测评库下载