题目背景

本题来源：http://8.136.99.126/p/P98，感谢 035966_L3 提供的题目。

以下排名不分先后。

• Update 2025/5/12 15:00：感谢 Moeebius 提供的 hack 代码，已更新交互库。
• Update 2025/5/12 21:18：感谢 SmokingTurtle 提供的 hack 思路，已更新交互库。
• Update 2025/5/13 14:40：感谢 破壁人五号 和 Argvchs 提供的 hack 代码，以及 Moeebius 提供的防范思路；已更新交互库。
• Update 2025/5/13 18:34：感谢 MrPython 提供的 hack 代码，已更新交互库。
• Update 2025/5/14 08:38：感谢 N_z_ 和 Exschawasion 提供的 hack 代码，已更新交互库。

题目描述

这是一道通信题，只支持 C++ 语言。请不要使用 C++14 (GCC 9) 提交。

给定两个长度相等（不超过 $10^6$）且至多有一个位置的字符不同的 01 串 $S,T$（下标从 $1$ 开始）。Alice 只知道 $S$，Bob 只知道 $T$。

Bob 想要确定 $S,T$ 字符不同的那个位置。为了达成这一目的，Alice 决定偷偷帮助他。

具体来说，Alice 可以向 Bob 传递一个整数 $X$，满足 $X \in [0, 2^{20})$。

特别地，如果 $S=T$，Bob 应返回 0。

实现细节

你不需要，也不应该实现主函数。

你应该实现以下两个函数：

int Alice(std::string S);

• 在单组测试点中，该函数只会被调用一次。
• $S$：长度不超过 $10^6$ 的 std::string 数组，表示题目中的 $S$。
• 该函数返回一个满足 $X \in [0, 2^{20})$ 的整数 $X$，表示 Alice 给 Bob 传递的数。

int Bob(std::string T, int X);

• 在单组测试点中，该函数只会被调用一次。
• $T$：长度不超过 $10^6$ 的 std::string 数组，表示题目中的 $T$。
• $X$：满足 $X \in [0, 2^{20})$ 的整数 $X$，表示 Alice 给 Bob 传递的数。
• 记 $N$ 为 $T$ 的长度，该函数返回一个满足 $P \in [0, N]$ 的整数 $P$，表示 $S,T$ 字符不同的位置。如果 $S=T$，返回 0。

在最终评测时，对于单组测试点，上述两个函数会在不同的进程中运行。也就是说，你不能通过全局变量等方式试图在函数间传递信息。

评分方式

本题首先会受到和传统题相同的限制。例如编译错误会导致整道题目得 0 分，运行时错误、超过时间限制、超过空间限制都会导致相应测试点得 0 分。选手只能在程序中访问自己定义的和交互库给出的变量或数据，及其相应的内存空间。尝试访问其他位置空间将可能导致编译错误或运行错误。禁止通过操作标准输入输出等行为攻击交互库，一经发现，本题直接得 0 分。

如果 Alice 的返回值不是满足 $X \in [0, 2^{20})$ 的整数 $X$、Bob 的返回值不是满足 $P \in [0, N]$ 的整数 $P$、Bob 返回的 $P>0$ 且满足 $S_P=T_P$，或者 Bob 返回 $P=0$ 且 $S\neq T$，测试点得 0 分；否则得满分。

如果你的程序出现非预期行为（例如在函数里调用 exit 等），你可能会得到 Unknown Error。

样例交互库

下发文件有 grader.cpp，你可以使用其辅助调试。为了兼容各操作系统，样例交互库不会将两个函数在不同进程中运行，而是在一个进程中依次调用两个函数，如果你使用了全局变量，请注意可能需要的清理工作。

编译

你可以将下发文件的 grader.cpp 复制到你编写的 communication.cpp 同一目录下，然后使用 g++ communication.cpp grader.cpp -std=c++14 -O2 -o grader 编译，该命令会在当前目录下生成可执行文件 grader（Linux / macOS）或 grader.exe（Windows）。

样例交互库输入格式

• 第一行一个字符串 $S$。
• 第二行一个字符串 $T$。

样例交互库输出格式

如果你的通信过程或返回值存在错误，交互库会输出 Wrong Answer；否则输出 Accepted。

0101011
0100011

4

提示

对于所有测试数据，记 $N$ 为 $S$ 的长度，保证 $1 \leq N \leq 10^6$。

样例输出表示 Bob 函数的正确返回值。

测试点编号	$N \leq$
$1 \sim 5$	$30$
$6 \sim 10$	$10^3$
$11 \sim 15$	$3 \times 10^4$
$16 \sim 20$	$10^6$