P9071 [CTS2023] Pigeons (No Anti-Cheating)

Xiao E and Xiao F are a pair of best friends.

This is a **communication problem**. Xiao E has some very important information to send to Xiao F. The information can be represented by a binary integer of at most $128$ bits. However, Xiao E only has pigeons now. Lots and lots of pigeons. Black pigeons and white pigeons. Xiao E can let pigeons of different colors take off in a certain order and fly to Xiao F. Then Xiao F can figure out the exact information from the color order of the pigeons as they land. Of course, the number of pigeons must be agreed on in advance and fixed; otherwise, before seeing all the pigeons, Xiao F might mistakenly think that all pigeons have already flown by. But as everyone knows, the word “pigeon” is always associated with “time”. Pigeons may “stand you up”. However, Xiao E’s pigeons are fairly punctual: the difference between the takeoff order and the landing order will not exceed a positive integer $k$. Formally, suppose the $i$-th pigeon to take off is the $p_i$-th to land. Then $\{p_i\}$ is a permutation, and for all $i$, $\left|i-p_i\right|\le k$. Xiao E has naturally considered these situations and has agreed on them with Xiao F in advance. If you were Xiao E, how would you make the agreement and send the information? ### Implementation Details [Note]: To submit this problem, you need to add `extern "C"` before all functions. You do not need to and should not implement the main function. You need to implement three functions: `pigeon_num`, `send`, and `receive`. The interface of `pigeon_num` is: ```cpp int pigeon_num(int Taskid, int k); ``` - This function takes the subtask ID `Taskid` and the value of parameter `k` in the statement. - This function should return the number of pigeons $n$ that Xiao E needs to send. The interface of `send` is: ```cpp std::string send(int Taskid, int n, int k, __uint128_t msg); ``` - This function takes the subtask ID `Taskid`, the return value `n` of `pigeon_num`, the parameter `k` in the statement, and the message `msg` to be sent. - This function should return a string of length exactly $n$. The position with index $i(0\le i\lt n)$ represents the color of the $(i+1)$-th pigeon that Xiao E sends: `0` means black, and `1` means white. The interface of `receive` is: ```cpp __uint128_t receive(int Taskid, int k, const std::string &msg); ``` - This function takes the subtask ID `Taskid`, the parameter `k` in the statement, and the landing order `msg` seen by Xiao F. - `msg` is a string of length $n$. The position with index $i(0\le i\lt n)$ represents the color of the $(i+1)$-th pigeon that Xiao F sees landing: `0` means black, and `1` means white. The value of `msg` has the relationship described in the statement with the return value of some call to `send`. - This function should correctly return the information sent by Xiao E. You may refer to the sample program `pigeon.cpp` provided, or you may write a program from scratch. During evaluation, the interactive library will be run **twice**, and **time and memory are counted independently for the two runs**. In the first run, the interactive library will call `pigeon_num` once, and then call `send` no more than $1000$ times. In the second run, the interactive library will call `receive` no more than $10000$ times. It is guaranteed that under the problem limits, the evaluation interactive library runs in no more than $1\texttt{s}$ and uses no more than $512\textrm{MB}$ of memory. That is, the time you can actually use is at least $2\texttt{s}$, and the memory is at least $1.5\textrm{GB}$. **Since Luogu does not currently support judging communication problems, the judging logic is similar to the provided interactive library. This means it is easy to cheat. E_Space will not pursue cheating behavior here, but please do not write it in the solution.** ### How to Run the Test Program Put the sample interactive library `grader.cpp` and your code `pigeon.cpp` in the same directory, and compile in the terminal with the following command: ```bash g++ pigeon.cpp grader.cpp -o grader -g -Wall --std=c++11 ``` Then run `./grader`. The sample interactive library uses standard input and standard output, and **only needs to be run once**. Note that the provided interactive library is implemented differently from the one used in the actual evaluation. For example, in the provided interactive library, the value of a global variable modified in `send` can be seen by `receive`.

The first line contains three non-negative integers $\mathrm{Taskid}$, $k$, $T$. Here, $\mathrm{Taskid}$ is the subtask ID, and $T$ is the number of messages to be sent. The next $T$ lines each contain one non-negative $128$-bit integer, representing the content of a message.

If your program is correct on this test point, then for each message, the interactive library will output four lines. - The first line `Message` is the information Xiao E wants to send, i.e., the value of parameter `msg` in `send`. - The second line `Taking off` is the takeoff order of the pigeons, i.e., the return value of `send`. - The third line `Landing` is the landing order of the pigeons, i.e., the value of parameter `msg` in `receive`. - The fourth line `Received` is the information decoded by Xiao F, i.e., the return value of `receive`. - The last line outputs `Accepted using pigeon(s).`, where `` is the number of pigeons Xiao E sent, i.e., the return value of `pigeon_num`. Otherwise, if the program exits normally, the interactive library will output one of the following messages: - `Invalid number of pigeons.`: This means the return value of `pigeon_num` is not in $[1,4000]$. - `Invalid color of pigeon.`: This means the return value of `send` contains a character other than `0` or `1`. - `Too few or too many pigeons taking off.`: This means the length of the return value of `send` is not equal to the return value of `pigeon_num`. - `Received wrong message.`: This means the return value of `receive` is not equal to the parameter `msg` in `send`. Once the interactive library outputs an error message, it will stop immediately.

#### Sample Explanation This is the output of the sample interactive library when running the provided sample program `pigeon.cpp` on the sample input. For Xiao E, $97429867398990605044182047185430790478$ is a very meaningful number. So only a small number of pigeons is enough. ### Subtasks Subtask $0$ ($0.01$ points): Sample. It is guaranteed that the integer corresponding to the message equals $97429867398990605044182047185430790478$. The provided `pigeon.cpp` can pass the sample. The judging result of this subtask will be shown in the judging results. Subtask $1$ ($3.99$ points): It is guaranteed that the integer corresponding to the message is less than $1024$. $k\le 20$. Subtask $2$ ($12$ points): $k=1$. It is guaranteed that the integer corresponding to the message is less than $1048576$. Subtasks $3\sim 9$ (each subtask $12$ points, $84$ points in total): $k\le 20$. **Since Luogu does not support fractional scores, the displayed score of this problem will be multiplied by $100$ to represent the result after keeping two decimal places.** ### Scoring During evaluation, you only need to submit your source code on the OJ. Modifying other provided files will not affect the evaluation result. This problem is first subject to the same limits as traditional problems. For example, a compilation error will cause the whole problem to score $0$ points; runtime error, time limit exceeded, memory limit exceeded, etc. will cause the corresponding test points to score $0$ points. You may only access variables defined by yourself and those given by the interactive library, as well as their corresponding memory spaces. Attempting to access other spaces may lead to compilation errors or runtime errors. For each subtask, if your program has any of the following behaviors, it will be judged as $0$ points: - The return value of `pigeon_num` is not in $[1,4000]$. - The length of the return value of `send` is not equal to the return value of `pigeon_num`. - The return value of `send` contains characters other than `0` or `1`. - `receive` does not correctly return the information sent by Xiao E. In addition, for each subtask, your score is related to the number of pigeons Xiao E sends, i.e., the return value of `pigeon_num`. Let this value be $n$. In subtasks $1 \sim 2$, if $n\le 4000$, you can get full score for this test point; otherwise you get $0$. In subtasks $3\sim 9$, within the same subtask, all test points have the same value of $k$, and in higher-numbered subtasks, the value of $k$ is larger. Let $C(k)$ be a function of $k$. Then: - If $n\le C(k)$, you can get full score for this test point. - If $n\le C(k)+5$, then within this range, for each increase of $1$ in $n$, you lose $2\%$ of the full score of this test point. - If $C(k)+5 \lt n\le \lfloor 1.1\times C(k)\rfloor$, then within this range, for each increase of $1$ in $n$, you additionally lose $400\%/C(k)$ of the full score of this test point. - If $n\gt \lfloor 1.1\times C(k)\rfloor$, then within this range, for each increase of $1$ in $n$, you additionally lose $40\%/C(k)$ of the full score of this test point. - If your answer is correct, you can get at least $1$ point. In other words, your score on a test point is $\max(1, 12\times \min(1, f_k(n)))$, where $f_k(n)$ is a piecewise linear function of $n$ satisfying: - $f_k(C(k))=1$. - The $x$-coordinates of the two breakpoints are $C(k)+5$ and $\lfloor 1.1\times C(k)\rfloor$. - The slopes of the three segments formed by the two breakpoints are, in order, $-0.02$, $-4/C(k)$, and $-0.4/C(k)$. Your score for each subtask is the minimum score among all test points in the subtask. The value of $C(k)$ is given in the table below. The values of $k$ not appearing in the table will not appear in the testdata of subtasks $3\sim 9$. | $k$ | $1$ | $2$ | $5$ | $7$ | $10$ | $14$ | $20$ | | :----------- | :----------- | :----------- | :----------- | :----------- | :----------- | :----------- | :----------- | | $C(k)$ | $206$ | $284$ | $485$ | $605$ | $773$ | $983$ | $1277$ | **Gaining score by accessing input/output files, attacking the judging system, or attacking the judging library, etc., is cheating behavior, and the score obtained is invalid.** **Since Luogu does not currently support judging communication problems, the judging logic is similar to the provided interactive library. This means it is easy to cheat. E_Space will not pursue cheating behavior here, but please do not write it in the solution.** Translated by ChatGPT 5