{"problem":{"name":"[CTS2023] 鸽子（无防作弊）","description":{"content":"这是一道**通信题**。 小 E 有一些很重要的信息要传给小 F。信息的内容可以用一个不超过 $128$ 位的二进制整数来表示。 但是小 E 现在只有鸽子。好多好多的鸽子。黑色和白色的鸽子。 小 E 可以让不同颜色的鸽子按一定的顺序起飞，飞到小 F 那里，这样小 F 就可以根据降落的鸽子的颜色顺序来知道信息的具体内容了。当然鸽子的数量是需要约定好且固定的，不然小 F 可能会在看到所有鸽子之前","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":3000,"memory_limit":2097152},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9071"},"statements":[{"statement_type":"Markdown","content":"这是一道**通信题**。\n\n小 E 有一些很重要的信息要传给小 F。信息的内容可以用一个不超过 $128$ 位的二进制整数来表示。\n\n但是小 E 现在只有鸽子。好多好多的鸽子。黑色和白色的鸽子。\n\n小 E 可以让不同颜色的鸽子按一定的顺序起飞，飞到小 F 那里，这样小 F 就可以根据降落的鸽子的颜色顺序来知道信息的具体内容了。当然鸽子的数量是需要约定好且固定的，不然小 F 可能会在看到所有鸽子之前误以为所有的鸽子都已经飞过来了。\n\n但是众所周知，“鸽子”一词总是和“时间”联系在一起。鸽子会放鸽子。不过小 E 的鸽子还算守时，起飞和降落的顺序之差不会超过一个正整数 $k$。形式化地，设起飞的第 $i$ 只鸽子是第 $p_i$ 个降落的，那么 $\\{p_i\\}$ 是一个排列且对于所有的 $i$，$\\left|i-p_i\\right|\\le k$。\n\n小 E 自然是考虑到了这些情况，并提前与小 F 约定好了。请问如果你是小 E 你要怎样做下约定以及发送信息呢？\n\n### 实现细节\n\n【备注】：提交此题需要在所有函数前加上 `extern \"C\"`。\n\n你不需要也不应该实现主函数。你需要实现三个函数 `pigeon_num`，`send` 和 `receive`。\n\n函数 `pigeon_num` 的接口如下：\n\n```cpp\nint pigeon_num(int Taskid, int k);\n```\n\n- 该函数传入子任务编号 `Taskid` 和题目中参数 `k` 的值。\n- 该函数需要返回小 E 需要放飞的鸽子数量 $n$。\n\n函数 `send` 的接口如下：\n\n```cpp\nstd::string send(int Taskid, int n, int k, __uint128_t msg);\n```\n\n- 该函数传入子任务编号 `Taskid`，`pigeon_num` 函数的返回值 `n`，题目中的参数 `k` 以及需要发送的信息 `msg`。\n- 该函数需要返回一个长度恰好为 $n$ 的字符串，其中下标为 $i(0\\le i\\lt n)$ 的位置表示小 E 放飞的第 $i+1$ 只鸽子的颜色，`0` 表示黑色，`1` 表示白色。\n\n函数 `receive` 的接口如下：\n\n```cpp\n__uint128_t receive(int Taskid, int k, const std::string &msg);\n```\n\n- 该函数传入子任务编号 `Taskid`，题目中的参数 `k` 以及小 F 看到的鸽子的降落顺序 `msg`。\n- `msg` 为一个长度为 $n$ 的字符串，其中下标为 $i(0\\le i\\lt n)$ 的位置表示小 F 看到的第 $i+1$ 只降落的鸽子的颜色，`0` 表示黑色，`1` 表示白色。`msg` 的值与某次调用 `send` 函数的返回值有着题目描述中所满足的关系。\n- 该函数需要正确返回小 E 发送的信息的内容。\n\n你可以参考下发的样例程序 `pigeon.cpp`，也可以从头开始写一个程序。\n\n在评测时，交互库会被运行**两次**，**两次运行独立计算时间和空间**。\n\n在第一次运行时，交互库会先调用一次 `pigeon_num` 函数，然后调用不超过 $1000$ 次 `send` 函数。\n\n在第二次运行时，交互库会调用不超过 $10000$ 次 `receive` 函数。\n\n保证在题目限制下，评测交互库的运行时间不超过 $1\\texttt{s}$，运行内存不超过 $512\\textrm{MB}$。也就是说，你实际可以利用的时间至少为 $2\\texttt{s}$，空间至少为 $1.5\\textrm{GB}$。\n\n**由于洛谷暂不支持通信题的评测，评测方式逻辑与下发交互库类似。这意味着可以轻松地作弊。E_Space 在这里不追究有关于此的作弊行为，但请不要写到题解中去。**\n\n### 测试程序方式\n\n将样例交互库 `grader.cpp` 和你的代码 `pigeon.cpp` 置于同一目录下并在终端中输入如下命令进行编译：\n\n```bash\ng++ pigeon.cpp grader.cpp -o grader -g -Wall --std=c++11\n```\n\n然后运行 `./grader` 即可。样例交互库使用标准输入和标准输出，**只需要运行一次**。\n\n注意下发的交互库与实际评测时使用的交互库的实现不同。比如在下发的交互库中，通过 `send` 函数修改的全局变量的值能够被 `receive` 函数查看。\n\n## Input\n\n第一行三个非负整数 $\\mathrm{Taskid}$，$k$，$T$。其中 $\\mathrm{Taskid}$ 表示子任务编号，$T$ 表示发送信息的数量。\n\n接下来 $T$ 行，每行一个非负 $128$ 位整数表示信息的内容。\n\n## Output\n\n如果你的程序在该测试点上是正确的，对于每一条信息，交互库会输出四行内容。\n\n- 第一行 `Message` 为小 E 想要发送的信息，即 `send` 函数中参数 `msg` 的内容。\n- 第二行 `Taking off` 为鸽子起飞的顺序，即 `send` 函数的返回值。\n- 第三行 `Landing` 为鸽子降落的顺序，即 `receive` 函数中参数 `msg` 的内容。\n- 第四行 `Received` 为小 F 解读出来的信息，即 `receive` 函数的返回值。\n- 最后一行输出 `Accepted using <num> pigeon(s).`，其中 `<num>` 是小 E 放飞的鸽子的数量，即 `pigeon_num` 函数的返回值。\n\n否则如果程序正常退出，交互库会输出以下内容之一：\n\n- `Invalid number of pigeons.`：输出这句话说明 `pigeon_num` 函数的返回值不在 $[1,4000]$ 之间。\n- `Invalid color of pigeon.`：输出这句话说明 `send` 函数的返回值中有非 `0` 或 `1` 的字符。\n- `Too few or too many pigeons taking off.`：输出这句话说明 `send` 函数的返回值的长度不等于 `pigeon_num` 函数的返回值。\n- `Received wrong message.`：输出这句话说明 `receive` 函数的返回值与 `send` 函数中的参数 `msg` 不相等。\n\n一旦交互库输出了报错语句，交互库程序就会立即停止运行。\n\n[samples]\n\n## Background\n\n小 E 和小 F 是一对好闺蜜。\n\n## Note\n\n#### 样例解释\n\n这是样例交互库在下发样例程序 `pigeon.cpp` 在样例输入下的输出。\n\n对于小 E 来说，$97429867398990605044182047185430790478$ 是一个很有意义的数。所以只需要放飞少量鸽子就够了。\n\n### 子任务\n\n子任务 $0$（$0.01$ 分）：样例。保证信息对应的整数等于 $97429867398990605044182047185430790478$。下发的 `pigeon.cpp` 能够通过样例。该子任务的评测结果会显示在评测结果中。\n\n子任务 $1$（$3.99$ 分）：保证信息对应的整数小于 $1024$。 $k\\le 20$。\n\n子任务 $2$（$12$ 分）：$k=1$。保证信息对应的整数小于 $1048576$。\n\n子任务 $3\\sim 9$（每个子任务 $12$ 分，共 $84$ 分）：$k\\le 20$。\n\n**由于洛谷不支持小数得分，本题的得分显示将乘以 100 来表示保留两位小数之后的结果。**\n\n### 评分方式\n\n评测时，你只需在 OJ 上提交你的源程序，修改下发的其他文件不会对评测结果产生影响。\n\n本题首先会受到和传统题相同的限制，例如编译错误会导致整道题目得 $0$ 分，运行时错误、超过时间限制、超过空间限制等会导致相应测试点得 $0$ 分等。你只能访问自己定义的和交互库给出的变量及其对应的内存空间，尝试访问其他空间将可能导致编译错误或运行错误。\n\n对于每个子任务，如果你的程序有以下行为，将会被判为 $0$ 分：\n\n- `pigeon_num` 函数的返回值不在 $[1,4000]$ 之内；\n- `send` 函数的返回值的长度不等于 `pigeon_num` 函数的返回值；\n- `send` 函数的返回值的内容包含 `0` 或 `1` 之外的字符；\n- `receive` 函数没有正确地返回小 E 发送的信息内容。\n\n此外，对于每个子任务，你的得分与小 E 放飞的鸽子的数量，即 `pigeon_num` 函数的返回值有关。设这个值为 $n$。\n\n在子任务 $1 \\sim 2$ 中，如果 $n\\le 4000$，那么你就能得到该测试点的满分，否则得到零分。\n\n在子任务 $3\\sim 9$ 中，同一个子任务中所有测试点的 $k$ 的值相同，且编号越大的子任务中 $k$ 的值越大。设 $C(k)$ 为一个关于 $k$ 的函数，则\n\n- 如果 $n\\le C(k)$，那么你可以得到该测试点的满分。\n- 若 $n\\le C(k)+5$，那么在此范围内 $n$ 的值每多 $1$，你就会失去该测试点满分乘以 $2\\%$ 的分数。\n- 若 $C(k)+5 \\lt n\\le \\lfloor 1.1\\times C(k)\\rfloor$，那么在此范围内 $n$ 的值每多 $1$，你就会额外失去该测试点满分乘以 $400\\%/C(k)$ 的分数。\n- 若 $n\\gt \\lfloor 1.1\\times C(k)\\rfloor$，那么在此范围内 $n$ 的值每多 $1$，你就会额外失去该测试点满分乘以 $40\\%/C(k)$ 的分数。\n- 若你的答案正确，你至少可以得到 $1$ 分。\n\n换句话说，你在一个测试点的得分等于 $\\max(1, 12\\times \\min(1, f_k(n)))$，其中 $f_k(n)$ 是一个关于 $n$ 的分段线性函数，满足：\n\n- $f_k(C(k))=1$\n- 两个拐点的横坐标分别为 $C(k)+5$ 和 $\\lfloor 1.1\\times C(k)\\rfloor$。\n- 被两个拐点分割所形成的三段区间的斜率依次为 $-0.02$，$-4/C(k)$ 和 $-0.4/C(k)$。\n\n你的每个子任务的得分是子任务中所有测试点得分的最小值。\n\n$C(k)$ 的函数值由下表给出。在下表中未出现的 $k$ 值不会出现在子任务 $3\\sim 9$ 的测试数据中。\n\n| $k$ | $1$ | $2$ | $5$ | $7$ | $10$ | $14$ | $20$ |\n| :----------- | :----------- | :----------- | :----------- | :----------- | :----------- | :----------- | :----------- |\n| $C(k)$ | $206$ | $284$ | $485$ | $605$ | $773$ | $983$ | $1277$ |\n\n**通过访问输入输出文件、攻击评测系统或攻击评测库等方式得分属于作弊行为，所得分数无效。**\n\n**由于洛谷暂不支持通信题的评测，评测方式逻辑与下发交互库类似。这意味着可以轻松地作弊。E_Space 在这里不追究有关于此的作弊行为，但请不要写到题解中去。**","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9071","tags":["2023","交互题","Special Judge","通信题","CTSC/CTS"],"sample_group":[["0 6 1\n97429867398990605044182047185430790478","Message:    97429867398990605044182047185430790478\nTaking off: 10101\nLanding:    10011\nReceived:   97429867398990605044182047185430790478\n\nAccepted using 5 pigeons."]],"created_at":"2026-03-03 11:09:25"}}