#P12509. 【模板】通信题

    ID: 14083 远端评测题 1000ms 512MiB 尝试: 0 已通过: 0 难度: 3 上传者: 标签>交互题Special Judge哈希 hashing通信题

【模板】通信题

题目背景

本题来源: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) 提交。

给定两个长度相等(不超过 10610^6)且至多有一个位置的字符不同的 01 串 S,TS,T(下标从 11 开始)。Alice 只知道 SS,Bob 只知道 TT

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

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

特别地,如果 S=TS=T,Bob 应返回 0。

实现细节

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

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

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

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

评分方式

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

如果 Alice 的返回值不是满足 X[0,220)X \in [0, 2^{20}) 的整数 XX、Bob 的返回值不是满足 P[0,N]P \in [0, N] 的整数 PP、Bob 返回的 P>0P>0 且满足 SP=TPS_P=T_P,或者 Bob 返回 P=0P=0STS\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)。

样例交互库输入格式

  • 第一行一个字符串 SS
  • 第二行一个字符串 TT

样例交互库输出格式

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

0101011
0100011
4

提示

对于所有测试数据,记 NNSS 的长度,保证 1N1061 \leq N \leq 10^6

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

测试点编号 NN \leq
151 \sim 5 3030
6106 \sim 10 10310^3
111511 \sim 15 3×1043 \times 10^4
162016 \sim 20 10610^6