QOJ.ac

QOJ

Time Limit: 3 s Memory Limit: 2048 MB Total points: 100 Communication

# 5447. 鸽子

Statistics

题目背景

小 E 和小 F 是一对好闺蜜。

题目描述

这是一道通信题

小 E 有一些很重要的信息要传给小 F。信息的内容可以用一个不超过 $128$ 位的二进制整数来表示。

但是小 E 现在只有鸽子。好多好多的鸽子。黑色和白色的鸽子。

小 E 可以让不同颜色的鸽子按一定的顺序起飞,飞到小 F 那里,这样小 F 就可以根据降落的鸽子的颜色顺序来知道信息的具体内容了。当然鸽子的数量是需要约定好且固定的,不然小 F 可能会在看到所有鸽子之前误以为所有的鸽子都已经飞过来了。

但是众所周知,“鸽子”一词总是和“时间”联系在一起。鸽子会放鸽子。不过小 E 的鸽子还算守时,起飞和降落的顺序之差不会超过一个正整数 $k$。形式化地,设起飞的第 $i$ 只鸽子是第 $p_i$ 个降落的,那么 $\{p_i\}$ 是一个排列且对于所有的 $i$,$\left|i-p_i\right|\le k$。

小 E 自然是考虑到了这些情况,并提前与小 F 约定好了。请问如果你是小 E 你要怎样做下约定以及发送信息呢?

实现细节

你不需要也不应该实现主函数。你需要实现三个函数 pigeon_numsendreceive

函数 pigeon_num 的接口如下:

int pigeon_num(int Taskid, int k);
  • 该函数传入子任务编号 Taskid 和题目中参数 k 的值。
  • 该函数需要返回小 E 需要放飞的鸽子数量 $n$。

函数 send 的接口如下:

std::string send(int Taskid, int n, int k, __uint128_t msg);
  • 该函数传入子任务编号 Taskidpigeon_num 函数的返回值 n,题目中的参数 k 以及需要发送的信息 msg
  • 该函数需要返回一个长度恰好为 $n$ 的字符串,其中下标为 $i(0\le i\lt n)$ 的位置表示小 E 放飞的第 $i+1$ 只鸽子的颜色,0 表示黑色,1 表示白色。

函数 receive 的接口如下:

__uint128_t receive(int Taskid, int k, const std::string &msg);
  • 该函数传入子任务编号 Taskid,题目中的参数 k 以及小 F 看到的鸽子的降落顺序 msg
  • msg 为一个长度为 $n$ 的字符串,其中下标为 $i(0\le i\lt n)$ 的位置表示小 F 看到的第 $i+1$ 只降落的鸽子的颜色,0 表示黑色,1 表示白色。msg 的值与某次调用 send 函数的返回值有着题目描述中所满足的关系。
  • 该函数需要正确返回小 E 发送的信息的内容。

你可以参考下发的样例程序 pigeon.cpp,也可以从头开始写一个程序。

在评测时,交互库会被运行两次两次运行独立计算时间和空间

在第一次运行时,交互库会先调用一次 pigeon_num 函数,然后调用不超过 $1000$ 次 send 函数。

在第二次运行时,交互库会调用不超过 $10000$ 次 receive 函数。

保证在题目限制下,评测交互库的运行时间不超过 $1\texttt{s}$,运行内存不超过 $512\textrm{MB}$。也就是说,你实际可以利用的时间至少为 $2\texttt{s}$,空间至少为 $1.5\textrm{GB}$。

测试程序方式

将样例交互库 grader.cpp 和你的代码 pigeon.cpp 置于同一目录下并在终端中输入如下命令进行编译:

g++ pigeon.cpp grader.cpp -o grader -g -Wall --std=c++11

然后运行 ./grader 即可。样例交互库使用标准输入和标准输出,只需要运行一次

注意下发的交互库与实际评测时使用的交互库的实现不同。比如在下发的交互库中,通过 send 函数修改的全局变量的值能够被 receive 函数查看。

样例交互库输入格式

第一行三个非负整数 $\mathrm{Taskid}$,$k$,$T$。其中 $\mathrm{Taskid}$ 表示子任务编号,$T$ 表示发送信息的数量。

接下来 $T$ 行,每行一个非负 $128$ 位整数表示信息的内容。

样例交互库输出格式

如果你的程序在该测试点上是正确的,对于每一条信息,交互库会输出四行内容。

  • 第一行 Message 为小 E 想要发送的信息,即 send 函数中参数 msg 的内容。
  • 第二行 Taking off 为鸽子起飞的顺序,即 send 函数的返回值。
  • 第三行 Landing 为鸽子降落的顺序,即 receive 函数中参数 msg 的内容。
  • 第四行 Received 为小 F 解读出来的信息,即 receive 函数的返回值。
  • 最后一行输出 Accepted using <num> pigeon(s).,其中 <num> 是小 E 放飞的鸽子的数量,即 pigeon_num 函数的返回值。

否则如果程序正常退出,交互库会输出以下内容之一:

  • Invalid number of pigeons.:输出这句话说明 pigeon_num 函数的返回值不在 $[1,4000]$ 之间。
  • Invalid color of pigeon.:输出这句话说明 send 函数的返回值中有非 01 的字符。
  • Too few or too many pigeons taking off.:输出这句话说明 send 函数的返回值的长度不等于 pigeon_num 函数的返回值。
  • Received wrong message.:输出这句话说明 receive 函数的返回值与 send 函数中的参数 msg 不相等。

一旦交互库输出了报错语句,交互库程序就会立即停止运行。

样例一

输入

0 6 1
97429867398990605044182047185430790478

输出

Message:    97429867398990605044182047185430790478
Taking off: 10101
Landing:    10011
Received:   97429867398990605044182047185430790478

Accepted using 5 pigeons.

解释

这是样例交互库在下发样例程序 pigeon.cpp 在样例输入下的输出。

对于小 E 来说,$97429867398990605044182047185430790478$ 是一个很有意义的数。所以只需要放飞少量鸽子就够了。

子任务

子任务 $0$($0.01$ 分):样例。保证信息对应的整数等于 $97429867398990605044182047185430790478$。下发的 pigeon.cpp 能够通过样例。该子任务的评测结果会显示在评测结果中。

子任务 $1$($3.99$ 分):保证信息对应的整数小于 $1024$。 $k\le 20$。

子任务 $2$($12$ 分):$k=1$。保证信息对应的整数小于 $1048576$。

子任务 $3\sim 9$(每个子任务 $12$ 分,共 $84$ 分):$k\le 20$。

评分方式

评测时,你只需在 OJ 上提交你的源程序,修改下发的其他文件不会对评测结果产生影响。

本题首先会受到和传统题相同的限制,例如编译错误会导致整道题目得 $0$ 分,运行时错误、超过时间限制、超过空间限制等会导致相应测试点得 $0$ 分等。你只能访问自己定义的和交互库给出的变量及其对应的内存空间,尝试访问其他空间将可能导致编译错误或运行错误。

对于每个子任务,如果你的程序有以下行为,将会被判为 $0$ 分:

  • pigeon_num 函数的返回值不在 $[1,4000]$ 之内;
  • send 函数的返回值的长度不等于 pigeon_num 函数的返回值;
  • send 函数的返回值的内容包含 01 之外的字符;
  • receive 函数没有正确地返回小 E 发送的信息内容。

此外,对于每个子任务,你的得分与小 E 放飞的鸽子的数量,即 pigeon_num 函数的返回值有关。设这个值为 $n$。

在子任务 $1 \sim 2$ 中,如果 $n\le 4000$,那么你就能得到该测试点的满分,否则得到零分。

在子任务 $3\sim 9$ 中,同一个子任务中所有测试点的 $k$ 的值相同,且编号越大的子任务中 $k$ 的值越大。设 $C(k)$ 为一个关于 $k$ 的函数,则

  • 如果 $n\le C(k)$,那么你可以得到该测试点的满分。
  • 若 $n\le C(k)+5$,那么在此范围内 $n$ 的值每多 $1$,你就会失去该测试点满分乘以 $2\%$ 的分数。
  • 若 $C(k)+5 \lt n\le \lfloor 1.1\times C(k)\rfloor$,那么在此范围内 $n$ 的值每多 $1$,你就会额外失去该测试点满分乘以 $400\%/C(k)$ 的分数。
  • 若 $n\gt \lfloor 1.1\times C(k)\rfloor$,那么在此范围内 $n$ 的值每多 $1$,你就会额外失去该测试点满分乘以 $40\%/C(k)$ 的分数。
  • 若你的答案正确,你至少可以得到 $1$ 分。

换句话说,你在一个测试点的得分等于 $\max(1, 12\times \min(1, f_k(n)))$,其中 $f_k(n)$ 是一个关于 $n$ 的分段线性函数,满足:

  • $f_k(C(k))=1$
  • 两个拐点的横坐标分别为 $C(k)+5$ 和 $\lfloor 1.1\times C(k)\rfloor$。
  • 被两个拐点分割所形成的三段区间的斜率依次为 $-0.02$,$-4/C(k)$ 和 $-0.4/C(k)$。

你的每个子任务的得分是子任务中所有测试点得分的最小值。

$C(k)$ 的函数值由下表给出。在下表中未出现的 $k$ 值不会出现在子任务 $3\sim 9$ 的测试数据中。

$k$$1$$2$$5$$7$$10$$14$$20$
$C(k)$$206$$284$$485$$605$$773$$983$$1277$

通过访问输入输出文件、攻击评测系统或攻击评测库等方式得分属于作弊行为,所得分数无效。

时间限制: 3.0 秒

空间限制: 2 GiB