Public Judge

pjudge

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

# 21629. 【PER #1】新问题

Statistics

这是一道通信题。

给定正整数 $N$,pA 有 $N$ 个两两不同的整数 $v_0,\cdots,v_{N-1}$,pB 有 $M$ 个区间 $[a_0,b_0],\cdots,[a_{M-1},b_{M-1}]$。

对每个 $i\in[0,M)$,pB 想知道 $v_{a_i},v_{a_i+1},\cdots,v_{b_i}$ 中最大元素的下标是多少,为此 pA 可以向 pB 发送至多 $2\cdot 10^5$ 个 bit 的信息。

  • 注意,pA 向 pB 发送的信息数量上界仅为评测时使用的一个硬性上界,为了取得满分,pA 实际向 pB 发送的信息必须符合各个子任务的评分规则。

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

实现细节

你不需要,也不应该实现 main() 函数,或在任何文件以及标准输入/输出流中读入或输出任何信息。

本题仅支持 C++ 语言,你需要实现两份代码,来分别实现 pA 与 pB 的策略。

第一份代码为 save.cpp,它需要包含头文件 save.h,并通过实现以下函数来描述 pA 的策略:

void read_array(int subtask_id, const std::vector <int> &v);
  • 在每组测试数据中,该函数会被调用恰好一次;
  • 参数中的 subtask_id 表示当前测试点的子任务编号;
  • 参数中的 v 表示给定的序列 $v_0,\cdots,v_{N-1}$。

你可以调用以下函数:

void save_to_floppy(const std::string &bits);
  • 你只能在 read_array 函数中调用该函数,且调用恰好一次;
  • 参数中的 bits 是 $\texttt{01}$ 字符串,表示 pA 向 pB 发送的信息。

第二份代码为 load.cpp,它需要包含头文件 load.h,并通过实现以下函数来描述 pB 的策略:

std::vector <int> solve_queries(int subtask_id, int N, const std::string &bits, const std::vector <int> &a, const std::vector <int> &b);
  • 在每组测试数据中,该函数会被调用恰好一次;
  • 参数中的 subtask_id 表示当前测试点的子任务编号;
  • 参数中的 bits 是 $\texttt{01}$ 字符串,表示 pA 向 pB 发送的信息;
  • 参数中的 ab 描述 $M$ 组询问,第 $i$ 组询问的 $a_i$ 和 $b_i$ 分别为 a[i]b[i]

样例交互库

在下发文件中,你可以找到样例交互库 grader.cpp,你可以通过样例交互库的实现来帮助你理解并实现这道题目。需要注意的是,在进行最终测试时,交互库的实现与样例交互库有所不同,因此你不应当依赖此交互库的实现。

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

  • 第一行,一个整数,表示 subtask_id
  • 第二行,两个正整数 $N,M$;
  • 第三行,$N$ 个整数 $v_0,\cdots,v_{N-1}$;
  • 之后 $M$ 行,每行三个非负整数,分别表示 $a_i,b_i$ 以及这组询问的正确答案。

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

  • 如果你的答案正确,它将输出 OK!
  • 如果你的答案错误,它将输出对应的错误信息。

你可以在终端使用以下命令来编译你的程序:

g++ grader.cpp save.cpp load.cpp -o prog -O2

需要注意的是,上述命令会将 grader 与你实现的两个程序一起编译,你需要避免不同代码之间的全局变量或函数重名。

请不要在两份代码中共享全局变量。在最终评测时,save 过程与 load 过程将在两个不同的进程中被调用,它们之间不能共享任何全局变量与函数。

样例

以下是一组可能的对样例交互库的输入:

2
4 10
40 20 30 10
0 0 0
0 1 0
0 2 0
0 3 0
1 1 1
1 2 2
1 3 2
2 2 2
2 3 2
3 3 3

以下是一次合法的交互过程:在程序 save 中,交互库进行以下调用:

read_array(
  /* subtask_id = */ 2,
  /* v          = */ {40, 20, 30, 10});

选手程序在该函数中进行以下调用:

save_to_floppy(
  /* bits = */ "001100");

随后,在程序 load 中交互库进行以下调用:

solve_queries(
  /* subtask_id = */ 2,
  /* N          = */ 4,
  /* bits       = */ "001100",
  /* a          = */ {0, 0, 0, 0, 1, 1, 1, 2, 2, 3},
  /* b          = */ {0, 1, 2, 3, 1, 2, 3, 2, 3, 3});

该函数需要返回如下 $M$ 个整数的数组:

{0, 0, 0, 0, 1, 2, 2, 2, 2, 3}

在最终评测时,对于任何合法的交互过程,保证交互库使用的时间不超过 $0.2$ 秒,使用的内存不超过 $4\text{ MiB}$。

子任务

如果你在某个测试点中没有在时间限制($1.0$ 秒)与空间限制($512\text{ MiB}$)内返回结果,或发生了运行时错误,或最终返回的答案不正确,则你在该测试点的得分为 $0$。

否则,设 $L$ 为 pA 向 pB 发送的信息长度,每个子任务中的测试点会有不同的评分方式。

在一个子任务中,你所得到的分数即为所有测试点分数的最小值。

对于所有数据,$N\le 4\cdot 10^4$,$M\le 8\cdot 10^4$,$-10^9\le v_i\le 10^9$,$v_i$ 两两不同。

子任务编号 追加限制 评分方式
$1$ $N\le 500$,$M\le 1000$,$0\le v_i<N$ $7$
$2$ $N\le 10^4$,$M\le 2\cdot 10^4$ $21\cdot\min(1,2^{\log_2N+1-\frac LN})$
$3$ $ $ $72\cdot\min(1,2^{2-\frac LN})$

时间限制:$\texttt{1s}$

空间限制:$\texttt{512MB}$