Background

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

Problem Description

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:

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:

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:

__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:

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.

Input Format

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.

Output Format

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 <num> pigeon(s)., where <num> 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.

0 6 1
97429867398990605044182047185430790478

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

Accepted using 5 pigeons.

Hint

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$.

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