题目背景
小 E 和小 F 是一对好闺蜜。
题目描述
这是一道通信题。
小 E 有一些很重要的信息要传给小 F。信息的内容可以用一个不超过 128 位的二进制整数来表示。
但是小 E 现在只有鸽子。好多好多的鸽子。黑色和白色的鸽子。
小 E 可以让不同颜色的鸽子按一定的顺序起飞,飞到小 F 那里,这样小 F 就可以根据降落的鸽子的颜色顺序来知道信息的具体内容了。当然鸽子的数量是需要约定好且固定的,不然小 F 可能会在看到所有鸽子之前误以为所有的鸽子都已经飞过来了。
但是众所周知,“鸽子”一词总是和“时间”联系在一起。鸽子会放鸽子。不过小 E 的鸽子还算守时,起飞和降落的顺序之差不会超过一个正整数 k。形式化地,设起飞的第 i 只鸽子是第 pi 个降落的,那么 {pi} 是一个排列且对于所有的 i,|i−pi|≤k。
小 E 自然是考虑到了这些情况,并提前与小 F 约定好了。请问如果你是小 E 你要怎样做下约定以及发送信息呢?
实现细节
你不需要也不应该实现主函数。你需要实现三个函数 pigeon_num
,send
和 receive
。
函数 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);
- 该函数传入子任务编号
Taskid
,pigeon_num
函数的返回值n
,题目中的参数k
以及需要发送的信息msg
。 - 该函数需要返回一个长度恰好为 n 的字符串,其中下标为 i(0≤i<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≤i<n) 的位置表示小 F 看到的第 i+1 只降落的鸽子的颜色,0
表示黑色,1
表示白色。msg
的值与某次调用send
函数的返回值有着题目描述中所满足的关系。- 该函数需要正确返回小 E 发送的信息的内容。
你可以参考下发的样例程序 pigeon.cpp
,也可以从头开始写一个程序。
在评测时,交互库会被运行两次,两次运行独立计算时间和空间。
在第一次运行时,交互库会先调用一次 pigeon_num
函数,然后调用不超过 1000 次 send
函数。
在第二次运行时,交互库会调用不超过 10000 次 receive
函数。
保证在题目限制下,评测交互库的运行时间不超过 1s,运行内存不超过 512MB。也就是说,你实际可以利用的时间至少为 2s,空间至少为 1.5GB。
测试程序方式
将样例交互库 grader.cpp
和你的代码 pigeon.cpp
置于同一目录下并在终端中输入如下命令进行编译:
g++ pigeon.cpp grader.cpp -o grader -g -Wall --std=c++11
然后运行 ./grader
即可。样例交互库使用标准输入和标准输出,只需要运行一次。
注意下发的交互库与实际评测时使用的交互库的实现不同。比如在下发的交互库中,通过 send
函数修改的全局变量的值能够被 receive
函数查看。
样例交互库输入格式
第一行三个非负整数 Taskid,k,T。其中 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
函数的返回值中有非0
或1
的字符。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≤20。
子任务 2(12 分):k=1。保证信息对应的整数小于 1048576。
子任务 3∼9(每个子任务 12 分,共 84 分):k≤20。
评分方式
评测时,你只需在 OJ 上提交你的源程序,修改下发的其他文件不会对评测结果产生影响。
本题首先会受到和传统题相同的限制,例如编译错误会导致整道题目得 0 分,运行时错误、超过时间限制、超过空间限制等会导致相应测试点得 0 分等。你只能访问自己定义的和交互库给出的变量及其对应的内存空间,尝试访问其他空间将可能导致编译错误或运行错误。
对于每个子任务,如果你的程序有以下行为,将会被判为 0 分:
pigeon_num
函数的返回值不在 [1,4000] 之内;send
函数的返回值的长度不等于pigeon_num
函数的返回值;send
函数的返回值的内容包含0
或1
之外的字符;receive
函数没有正确地返回小 E 发送的信息内容。
此外,对于每个子任务,你的得分与小 E 放飞的鸽子的数量,即 pigeon_num
函数的返回值有关。设这个值为 n。
在子任务 1∼2 中,如果 n≤4000,那么你就能得到该测试点的满分,否则得到零分。
在子任务 3∼9 中,同一个子任务中所有测试点的 k 的值相同,且编号越大的子任务中 k 的值越大。设 C(k) 为一个关于 k 的函数,则
- 如果 n≤C(k),那么你可以得到该测试点的满分。
- 若 n≤C(k)+5,那么在此范围内 n 的值每多 1,你就会失去该测试点满分乘以 2% 的分数。
- 若 C(k)+5<n≤⌊1.1×C(k)⌋,那么在此范围内 n 的值每多 1,你就会额外失去该测试点满分乘以 400%/C(k) 的分数。
- 若 n>⌊1.1×C(k)⌋,那么在此范围内 n 的值每多 1,你就会额外失去该测试点满分乘以 40%/C(k) 的分数。
- 若你的答案正确,你至少可以得到 1 分。
换句话说,你在一个测试点的得分等于 max,其中 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