Public Judge

pjudge

Time Limit: 2 s Memory Limit: 256 MB Total points: 100 Communication

# 21604. 【PTR #1】新问题

统计

这是一道通信题。

这是一个新问题。大家应该都知道这道题来自 JOISC,由于是测试赛,所以就不改题面了。

有一个长为 $N$ 的,由 $[0, N - 1]$ 内的整数构成的排列 $P_0, P_1, \cdots, P_{N-1}$。Anna 想要知道 $P_L, P_{L+1}, \cdots, P_R$ 中,最小的元素的下标是多少。但是 Anna 只知道 $n,L,R$ 的值,不知道排列 $P$ 的具体信息。

另一方面,Bruno 知道 $N$ 的值与整个排列 $P_0,P_1,\cdots, P_{N-1}$,但他却不知道 Anna 所询问的 $L, R$ 的值。

为了让 Anna 得到这个最小的下标,Anna 与 Bruno 之间可以互相发送信息。他们之间所发送的每个字符只能是 01,即每次一方可以向另一方发送一个 bit 的信息。由于通信仪器的限制,Alice 只能向 Bruno 发送至多 $18$ 个 bit 的信息,而 Bruno 只能向 Alice 发送至多 $10\,000$ 个 bit 的信息。

注意,Bruno 向 Anna 发送的信息数量上界仅为评测时使用的一个硬性上界,为了取得满分,Bruno 实际向 Anna 发送的信息不能超过 300 个 bit。

编写一个程序,实现 Anna 与 Bruno 两个人之间的策略。

实现细节

你需要提交两个文件。

Anna

你所需要提交的第一个文件为 Anna.cpp,它需要实现 Anna 的策略。你需要包含头文件 Anna.h,并实现以下函数:

void InitA(int N, int L, int R)

在每组测试数据中,该函数将会被调用恰好一次。

  • 参数中的 N 表示排列的长度 $N$
  • 参数中的 LR 表示 Anna 所询问的 $L$ 与 $R$。
void ReceiveA(bool x)

每当 Bruno 向 Anna 发送一个字符时,该函数会被调用。

  • 参数中的 x 描述 Bruno 向 Anna 所发送的字符。其中 true 表示这个字符为 1false 表示这个字符为 0
int Answer()

该函数会在信息传递完成后被调用恰好一次。该函数需要返回 Anna 所询问的最小元素的下标

在该文件中,你可以调用以下函数:

void SendA(bool y)

Anna 通过调用该函数向 Bruno 发送一个字符。

  • 参数中的 y 描述 Anna 向 Bruno 所发送的字符。其中 true 表示这个字符为 1false 表示这个字符为 0

Bruno

你所需要提交的第一个文件为 Bruno.cpp,它需要实现 Bruno 的策略。你需要包含头文件 Bruno.h,并实现以下函数:

void InitB(int N, std::vector<int> P)

在每组测试数据中,该函数将会被调用恰好一次。

  • 参数中的 N 表示排列的长度 $N$
  • 参数中的 P 描述一个长为 $N$ 的数组。其中对每个 $0 \leq i \leq N - 1$, P[i] 即为排列中 $P_i$ 的值。
void ReceiveB(bool y)

每当 Anna 向 Bruno 发送一个字符时,该函数会被调用。

  • 参数中的 y 描述 Anna 向 Bruno 所发送的字符。其中 true 表示这个字符为 1false 表示这个字符为 0

在该文件中,你可以调用以下函数:

void SendB(bool x)

Bruno 通过调用该函数向 Anna 发送一个字符。

  • 参数中的 x 描述 Bruno 向 Anna 所发送的字符。其中 true 表示这个字符为 1false 表示这个字符为 0

实现细节

你可以假设你的程序会通过如下方式进行执行:

对于每组测试数据,评测系统准备了两个队列:$Q_Y$ 存储由 Anna 发送的字符,$Q_X$ 存储由 Bruno 发送的字符。在评测开始时,函数 InitAInitB 将被调用,双方所发送的字符将被置入对应的队列中。随后,将不断重复以下过程:

  • 如果 $Q_x$ 与 $Q_y$ 有任意一个队列非空,则从对应的队列中弹出一个字符,并调用对应的函数。如果两个队列均非空,则会随机选择一个队列进行对应的调用。
    • 每当 SendA 被调用时,所发送的字符将被压入 $Q_Y$。
    • 每当 SendB 被调用时,所发送的字符将被压入 $Q_X$。
  • 如果两个队列均为空,则会调用函数 Answer,随后程序将被终止。

样例交互库

样例交互库将从标准输入中按照以下格式读入数据:

N L R
P[0] P[1] ... P[N-1]

当程序成功结束后,样例交互库将输出以下信息到标准输出:

  • 如果你的答案正确,它将输出 Anna 向 Bruno 发送的字符总数 $Y$ 与 Bruno 向 Anna 发送的字符总数 $X$,具体格式为 Accepted: Y X
  • 如果你的答案错误,它将输出 Wrong Answer[X]

子任务

对于所有数据:

  • $1 \leq N \leq 1\,000\,000$
  • $0 \leq L \leq R \leq N - 1$
  • $1 \leq P_i \leq N (0 \leq i \leq N - 1)$
  • $P_i \ne P_j (0 \leq i < j \leq N - 1)$

每个子任务的分值如下:

  • Subtask 1(1 point): $N \leq 1\,000$
  • Subtask 2(9 points): $N \leq 10\,000$
  • Subtask 3(90 points): 没有额外的限制。
    • 设 $T$ 为 Bruno 向 Anna 发送的字符总数。
    • 你在每个测试点中的得分将通过以下方式计算:
      • 若 $5\,000 < T \leq 10\,000$,你的得分为 $25 \times \frac{10000 - T}{5000}$
      • 若 $1\,000 < T \leq 5\,000$,你的得分为 $25 + 40 \times \frac{5000-T}{4000}$
      • 若 $300 < T \leq 1\,000$,你的得分为 $65 + 25 \times \frac{1000 - T}{700}$
      • 若 $T \leq 300$,你的得分为 $90$