Background

Little E and Little F are best friends.

Description

This is an interactive problem.

Little E has some important information to transmit to Little F. The content of the information can be represented as a binary integer of at most $128$ bits.

However, Little E only has pigeons. Lots and lots of pigeons. Black and white pigeons.

Little E can have pigeons of different colors take off in a certain order and fly to Little F, so that Little F can determine the specific content of the information based on the order of the colors of the landing pigeons. Of course, the number of pigeons must be agreed upon and fixed; otherwise, Little F might mistakenly think all pigeons have arrived before seeing all of them.

As is well known, the word "pigeon" is always associated with "time." Pigeons can be unreliable. However, Little E's pigeons are quite punctual; the difference between the order of takeoff and the order of landing will not exceed a positive integer $k$. Formally, if the $i$-th pigeon to take off is the $p_i$-th to land, then $\{p_i\}$ is a permutation such that for all $i$, $\left|i-p_i\right|\le k$.

Little E has naturally considered these situations and made an agreement with Little F in advance. If you were Little E, how would you make the agreement and send the information?

Implementation Details

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 for the function pigeon_num is as follows:

int pigeon_num(int Taskid, int k);

• This function receives the subtask ID Taskid and the value of the parameter $k$ from the problem.
• This function must return the number of pigeons $n$ that Little E needs to release.

The interface for the function send is as follows:

std::string send(int Taskid, int n, int k, __uint128_t msg);

• This function receives the subtask ID Taskid, the return value $n$ of the pigeon_num function, the parameter $k$ from the problem, and the information msg to be sent.
• This function must return a string of length exactly $n$, where the position at index $i$ ($0\le i < n$) represents the color of the $(i+1)$-th pigeon released by Little E, with 0 representing black and 1 representing white.

The interface for the function receive is as follows:

__uint128_t receive(int Taskid, int k, const std::string &msg);

• This function receives the subtask ID Taskid, the parameter $k$ from the problem, and the landing order msg of the pigeons seen by Little F.
• msg is a string of length $n$, where the position at index $i$ ($0\le i < n$) represents the color of the $(i+1)$-th pigeon that landed, with 0 representing black and 1 representing white. The value of msg satisfies the relationship described in the problem statement with the return value of a certain call to the send function.
• This function must correctly return the content of the information sent by Little E.

You may refer to the provided sample program pigeon.cpp, or you can write a program from scratch.

During evaluation, the interactor will be run twice, and the two runs will have independent time and memory limits.

In the first run, the interactor will call the pigeon_num function once, and then call the send function at most $1000$ times.

In the second run, the interactor will call the receive function at most $10000$ times.

It is guaranteed that under the problem constraints, the interactor will run within $1\texttt{s}$ and use no more than $512\textrm{MB}$ of memory. In other words, you effectively have at least $2\texttt{s}$ of time and $1.5\textrm{GB}$ of memory available.

Testing Your Program

Place the sample interactor grader.cpp and your code pigeon.cpp in the same directory and enter the following command in the terminal to compile:

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

Then run ./grader. The sample interactor uses standard input and standard output and only needs to be run once.

Note that the provided interactor is implemented differently from the one used in the actual evaluation. For example, in the provided interactor, the values of global variables modified by the send function can be viewed by the receive function.

Sample Interactor Input Format

The first line contains three non-negative integers $\mathrm{Taskid}$, $k$, and $T$. $\mathrm{Taskid}$ is the subtask ID, and $T$ is the number of messages to be sent.

The next $T$ lines each contain a non-negative $128$-bit integer representing the content of the information.

Sample Interactor Output Format

If your program is correct for the test case, the interactor will output four lines for each message:

• The first line Message is the information Little E wants to send, i.e., the content of the msg parameter in the send function.
• The second line Taking off is the order in which the pigeons take off, i.e., the return value of the send function.
• The third line Landing is the order in which the pigeons land, i.e., the msg parameter in the receive function.
• The fourth line Received is the information decoded by Little F, i.e., the return value of the receive function.
• The last line outputs Accepted using <num> pigeon(s)., where <num> is the number of pigeons released by Little E, i.e., the return value of the pigeon_num function.

Otherwise, if the program terminates normally, the interactor will output one of the following:

• Invalid number of pigeons.: This means the return value of pigeon_num is not in the range $[1, 4000]$.
• Invalid color of pigeon.: This means the return value of send contains characters 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 msg parameter in the send function.

Once the interactor outputs an error message, it will stop immediately.

Examples

Input 1

0 6 1
97429867398990605044182047185430790478

Output 1

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

Accepted using 5 pigeons.

Note

This is the output of the sample interactor using the provided pigeon.cpp with the sample input.

For Little E, $97429867398990605044182047185430790478$ is a very meaningful number. Therefore, only a small number of pigeons need to be released.

Subtasks

Subtask $0$ ($0.01$ points): Sample. It is guaranteed that the integer corresponding to the information is equal to $97429867398990605044182047185430790478$. The provided pigeon.cpp can pass the sample. The result of this subtask will be displayed in the evaluation results.

Subtask $1$ ($3.99$ points): It is guaranteed that the integer corresponding to the information is less than $1024$. $k\le 20$.

Subtask $2$ ($12$ points): $k=1$. It is guaranteed that the integer corresponding to the information is less than $1048576$.

Subtasks $3\sim 9$ ($12$ points each, $84$ points total): $k\le 20$.

Scoring

During evaluation, you only need to submit your source code on the OJ; modifying other provided files will not affect the evaluation results.

This problem is subject to the same constraints as traditional problems. For example, compilation errors will result in $0$ points for the entire problem, and runtime errors, time limit exceeded, or memory limit exceeded will result in $0$ points for the corresponding test case. You may only access variables you have defined and those provided by the interactor and their corresponding memory space; attempting to access other memory may result in compilation or runtime errors.

For each subtask, if your program exhibits any of the following behaviors, it will be judged as $0$ points:

• The return value of pigeon_num is not in the range $[1, 4000]$;
• The length of the return value of send is not equal to the return value of pigeon_num;
• The content of the return value of send contains characters other than 0 or 1;
• receive does not correctly return the information content sent by Little E.

Furthermore, for each subtask, your score is related to the number of pigeons released by Little E, i.e., the return value of pigeon_num. Let this value be $n$.

In subtasks $1 \sim 2$, if $n\le 4000$, you will receive full marks for the test case; otherwise, you will receive zero points.

In subtasks $3\sim 9$, the value of $k$ is the same for all test cases within the same subtask, and $k$ increases as the subtask number increases. Let $C(k)$ be a function of $k$:

• If $n\le C(k)$, you will receive full marks for the test case.
• If $n\le C(k)+5$, for every $1$ increase in $n$ within this range, you will lose $2\%$ of the full marks for the test case.
• If $C(k)+5 < n\le \lfloor 1.1\times C(k)\rfloor$, for every $1$ increase in $n$ within this range, you will additionally lose $400\%/C(k)$ of the full marks for the test case.
• If $n > \lfloor 1.1\times C(k)\rfloor$, for every $1$ increase in $n$ within this range, you will additionally lose $40\%/C(k)$ of the full marks for the test case.
• If your answer is correct, you will receive at least $1$ point.

In other words, your score for a test case is equal to $\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 abscissae of the two inflection points are $C(k)+5$ and $\lfloor 1.1\times C(k)\rfloor$.
• The slopes of the three intervals divided by the two inflection points are $-0.02$, $-4/C(k)$, and $-0.4/C(k)$ respectively.

Your score for each subtask is the minimum score among all test cases in that subtask.

The values of $C(k)$ are given in the table below. Values of $k$ not appearing in the table will not appear in the test data for subtasks $3\sim 9$.

Any attempt to access input/output files, attack the evaluation system, or attack the interactor is considered cheating, and the resulting score will be invalid.