4462. 通信题

题目背景

成功在 COGS 实现通信题！

漏洞是有的，也是避免不了的。所以请各位自觉。

这是一道通信题

题目描述

给定两个长度相等（不超过 $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。

实现细节

选手不需要，也不应该实现主函数。选手也不需要 freopen。必须使用文件输入输出评测机。

选手需要确保提交的程序包含头文件 communicate.h，即在程序开头加入以下代码：

#include "communicate.h"

选手需要在提交的程序源文件 communicate.cpp 中实现以下两个函数：

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 等），你可能会得到 Wrong answer。

测试程序方式

试题目录下的 grader.cpp 是交互库参考实现，最终测试时所用的交互库实现与该参考实现有所不同，因此选手的解法不应该依赖交互库实现。为了兼容各操作系统，样例交互库不会将两个函数在不同进程中运行，而是在一个进程中依次调用两个函数，如果你使用了全局变量，请注意可能需要的清理工作。

编译

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

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

该命令会在当前目录下生成可执行文件 grader（Linux / macOS）或 grader.exe（Windows）。

样例交互库输入格式

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

可执行文件将从标准输入读入以下格式的数据

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

样例交互库输出格式

可执行文件将输出以下格式的数据至标准输出：

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

输入输出样例 #1

输入 #1

0101011
0100011

输出 #1

4

说明/提示

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

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

下发文件

原理：将一次评测流程拆分成两个测试点，通过神秘方法传递通信内容