Public Judge

pjudge

Time Limit: 1 s Memory Limit: 256 MB Total points: 50 Communication
统计

这是一道通信题。

FlowerHuahuaQingyu 是一群要好的好朋友,他们将在一起组队参加 P 国主办的 Pb 学奥林匹克竞赛。

在本次竞赛中,三人团队需要解决这样一个问题:

  • FlowerHuahua 手中分别有 $N$ 个长度恰好为 $L$ 的 0/1 序列。
    • Flower 手中的序列为 $A_0,A_1,\cdots, A_{N-1}$,Huahua 手中的序列为 $B_{0}, B_{1}, \cdots, B_{N-1}$。
  • 随后,裁判选定 $Q$ 组 $(x_i,y_i)$,满足 $0 \le x_i, y_i < N$。注意有可能 $x_i = y_i$
  • 对每个 $0 \le i < Q$,生成一个长度恰好为 $L$ 的 0/1 串 $C_i$,满足对任意 $0 \le j < N$,都有 $C_i[j] = A_{x_i}[j] \oplus B_{y_i}[j]$。其中 $\oplus$ 为按位异或运算。
  • 裁判将这 $Q$ 个串 $C_0,C_1,\cdots, C_{Q-1}$ 均发送给 Qingyu,但 Qingyu 手中没有 $A$ 与 $B$ 的任何信息。
  • Qingyu 的任务是找到 $Q$ 组 $(x'_i, y'_i)$,满足对任意 $0 \le i < Q$,$0 \le j < N$,都有 $C_i[j] = A_{x_i'}[j] \oplus B_{y_i'}[j]$。

显然这个任务对于 Qingyu 来说实在是过于困难。好在 FlowerHuahua 拥有超能力,可以对 Qingyu 单向发送悄悄话。具体地,FlowerHuahua 每个人都可以向 Qingyu 发送一个长度恰好为 $M=6\,000$0/1 串,来作为一些提示。可惜的是,Qingyu 并不具备同样的能力,因此其只能单向接受信息,而不能向他们进行提问。

整个团队的得分取决于 Qingyu 对问题回答的正确率 $P$。当 $P \geq 99\%$ 时,团队即可获得满分。

现在,他们需要你的帮助,来设计每个人的策略,使得他们的目标能够达成。

形式化的题意

两个程序 FlowerHuahua 各有 $N$ 个 $L$ 位二进制数 $A_{0\cdots N-1}$ 与 $B_{0\cdots n-1}$(可能有前导零)。他们各自可以向第三个程序 Qingyu 发送一些信息。第三个程序需要回答 $Q$ 组询问,每组询问需要找到两个下标 $i, j$,使得 $A_i$ 异或 $B_j$ 恰好为给定的二进制数。保证至少存在一组合法的解。

实现细节

这是一道通信题,本题仅支持 C++ 语言。

你需要提交三个程序,其中程序 Flower 描述 FlowerQingyu 发送信息的策略,程序 Huahua 描述 HuahuaQingyu 发送信息的策略,程序 Qingyu 描述 Qingyu 收到裁判给定的信息、Flower 的悄悄话与 Huahua 的悄悄话后,回答问题的策略。

Flower

你所提交的第一个程序为 Flower,描述 FlowerQingyu 发送信息的策略。

你需要包含头文件 Flower.h,并实现以下函数:

std::string FlowerMessage(int T, int N, int L, std::vector<std::string> A);
  • 在每个测试点中,该函数会被调用恰好一次。
  • 参数 $\texttt{T}$ 表示当前子任务的编号。
  • 参数 $\texttt{N}$ 的含义即为题目中的 $N$。
  • 参数 $\texttt{L}$ 的含义即为题目中的 $L$。
  • 参数 $\texttt{A}$ 为一个长度为 $N$ 的数组,其中 $\texttt{A}[i]$ ($0 \le i < N$) 为一个长度恰好为 $L$ 的字符串,描述 $A_i$。
  • 你需要返回一个长度恰好为 $M = 6\,000$ 的、只由 01 构成的字符串 $S_F$,描述 Flower 所要发送的信息。

Huahua

你所提交的第二个程序为 Huahua,其描述 HuahuaQingyu 发送信息的策略。

你需要包含头文件 Huahua.h,并实现以下函数:

std::string HuahuaMessage(int T, int N, int L, std::vector <std::string> B);
  • 在每个测试点中,该函数会被调用恰好一次。
  • 参数 $\texttt{T}$ 表示当前子任务的编号。
  • 参数 $\texttt{N}$ 的含义即为题目中的 $N$。
  • 参数 $\texttt{L}$ 的含义即为题目中的 $L$。
  • 参数 $\texttt{B}$ 为一个长度为 $N$ 的数组,其中 $\texttt{B}[i]$ ($0 \le i < N$) 为一个长度恰好为 $L$ 的字符串,描述 $B_i$。
  • 你需要返回一个长度恰好为 $M = 6\,000$ 的、只由 01 构成的字符串 $S_H$,描述 Huahua 所要发送的信息。

Qingyu

你所提交的第三个程序为 Qingyu,其描述 Qingyu 回答问题的策略。

你需要包含头文件 Qingyu.h,并实现以下函数:

std::vector <std::pair <int, int> > Solve(int T, int N, int L, int Q, std::vector <std::string> C, std::string SF, std::string SH);
  • 在每个测试点中,该函数会被调用恰好一次。
  • 参数 $\texttt{T}$ 表示当前子任务的编号。
  • 参数 $\texttt{N}$ 的含义即为题目中的 $N$。
  • 参数 $\texttt{L}$ 的含义即为题目中的 $L$。
  • 参数 $\texttt{Q}$ 的含义即为题目中的 $Q$。
  • 参数 $\texttt{C}$ 为一个长度为 $Q$ 的数组,其中 $\texttt{C}[i]$ ($0 \le i < Q$) 为一个长度恰好为 $L$ 的字符串,描述 $C_i$。
  • 参数 $\texttt{SF}$ 为一个长度恰好为 $M = 6\,000$ 的、只由 01 构成的字符串 $S_F$,描述 Flower 所要发送的信息。
  • 参数 $\texttt{SH}$ 为一个长度恰好为 $M = 6\,000$ 的、只由 01 构成的字符串 $S_H$,描述 Flower 所要发送的信息。
  • 你需要返回一个长度恰好为 $Q = 500$ 的、由二元组 $(x', y')$ 构成的数组。第 $i$ ($0 \le i < Q$) 个二元组描述了 $x'_{i+1}, y'_{i+1}$ 的值。
    • 对于某组询问,如果存在多个符合条件的二元组,你可以输出任意一个。
    • 输入数据保证至少存在一对合法的 $(x', y')$。

样例交互库

本题下发文件中含有样例交互库 grader.cpp,选手可使用以下命令编译得到可执行文件:

g++ Flower.cpp Huahua.cpp Qingyu.cpp grader.cpp -o answer -O2 -std=c++14

可执行文件将从标准输入中通过以下格式读取输入数据:

  • 输入的第一行包含四个整数 $T, N, L, Q$。
  • 接下来 $N$ 行,第 $i$ 行包含一个长度恰好为 $L$ 的 0/1 串,描述每个 $A[]$。
  • 接下来 $N$ 行,第 $i$ 行包含一个长度恰好为 $L$ 的 0/1 串,描述每个 $B[]$。
  • 接下来 $Q$ 行,第 $i$ 行包含一个长度恰好为 $L$ 的 0/1 串,描述每个 $C[]$。

可执行文件将向标准输出中输出以下数据:

  • 若通信过程出现了错误,则输出对应的错误信息。
  • 否则,输出将包含恰好 $Q$ 行,每行两个整数 $x_i, y_i$,描述选手的答案。

需要注意的是,样例交互库既不会检查选手的程序是否使用了非法手段传递信息,也不会检查你最终输出的答案是否正确。

在最终评测时,程序 FlowerHuahuaQingyu 将被分别编译并在三个不同的进程中运行。本题的时间限制(1.0 秒)与空间限制(256 MiB)均指每个进程所能使用的时间与空间的最大值。在任意一个进程中超过该限制都会导致发生相应的错误。保证在最终评测时,三个程序各自的交互库使用的时间不超过 0.1 秒,空间不超过 16 MiB,即选手至少有 0.9 秒的时间与 240 MiB 的空间可用。

最终评测时所使用的交互库是 non-adaptive 的,即所有给定的串均在你的程序运行前固定,不会根据 FlowerHuahua 所返回的信息进行动态构造。

请注意,你不需要,也不能从标准输入中读取任何数据,也不能向标准输出中输出任何信息,否则可能导致通信的过程出现异常。

样例数据

样例 1

见下发文件。

本组样例满足子任务 $1$ 的特殊限制。

样例 2

见下发文件。

本组样例满足子任务 $2$ 的特殊限制。

样例 3

见下发文件。

本组样例满足子任务 $3$ 的特殊限制。

子任务

请注意,本题满分为 50 分。

对于除样例外的所有数据,$Q = 500$,$N$ 与 $L$ 的范围如表所示:

子任务编号 $N = $ $L = $ 特殊性质 分值
$1$ $100$ $30$ $5$
$2$ $100$ $5$
$3$ $200$ $1\,000$ A $10$
$4$ $30$
  • 特殊性质 A:保证 $A[i], B[i]$ 的生成方式均为每位独立在 01 中均匀随机生成。本组子任务中仅有 10 组测试数据。

在每个测试点中,记满分为 $S$,你可以根据正确率 $P$ 得到部分分:

$P$ 分值
$0.99 \le P$ $1.0 \times S$
$0.90 \le P < 0.99$ $P \times S$
$0.50 \le P < 0.90$ $P^2 \times S$
$P < 0.50$ $P^3 \times S$

即,为了获得满分,你需要在 $500$ 组询问中正确回答至少 $495$ 组。

Hack

Hack 功能在本题中不可用。