Pigeon Communication

In this problem, Little E needs to send an important 128-bit (or less) message to Little F using pigeons. The message is represented as a binary integer that does not exceed $128$ bits. Little E only has pigeons of two colors – black (represented by the character '0') and white (represented by the character '1').

The communication scheme works as follows. Little E arranges a fixed number of pigeons to fly in a predetermined order to Little F. The order in which the pigeons take off (the departure order) and the order in which they land (the arrival order) are related by a permutation $p$, where the $i$-th departing pigeon lands at position $p_i$. It is guaranteed that [ \left| i - p_i \right| \le k, \quad \text{for all } i, ] where $k$ is a given positive integer. This guarantees that the delay between the departure and arrival positions of each pigeon is bounded by $k$.

Your task is to design a scheme by which Little E can both agree on how many pigeons to send and encode the message in the pigeons' colors, such that Little F is able to recover the original message from the observed landing order. To achieve this, you need to implement three functions:

1. pigeon_num: decides the number of pigeons to be used.
2. send: converts the 128-bit message into a string of pigeon colors (using exactly n pigeons) for departure.
3. receive: recovers the original message from the observed landing order (which is a permutation of the sent order that satisfies the given delay constraint).

Implementation Note: In your submission, do not implement a main function. Instead, implement the three functions as described. Moreover, each function must be declared with extern "C" (for languages that support it).

Function Signatures:

For C++:

extern "C" int pigeon_num(int Taskid, int k);
extern "C" std::string send(int Taskid, int n, int k, __uint128_t msg);
extern "C" __uint128_t receive(int Taskid, int k, const std::string &msg);

For other languages, follow the analogous interface using their respective 128-bit integer representation (e.g., BigInteger in Java, or using int for Python as it supports arbitrary-precision integers).

Additional Details:

• You may assume that the identity permutation (i.e. the departure order equals the arrival order) is valid since it trivially satisfies \(|i-p_i| = 0 \le k\).
• For simplicity, you can choose to always use \(n=128\) pigeons and encode the message in its binary representation by zero-padding to 128 digits.
• The testing system will run the communication functions in two separate phases. In the first phase, your solution will be evaluated using at most 1000 calls to send after a call to pigeon_num. In the second phase, at most 10000 calls to receive will be made. The total available time is at least 2s and memory limit is at least 1.5GB.
• Note: Although the testing environment simulates the interaction described, this is a controlled setting where communication between the functions can be assumed.

inputFormat

This is an interactive communication problem. You are not reading from standard input. Instead, you must implement the three functions with the following interfaces:

1. int pigeon_num(int Taskid, int k): returns the number of pigeons to be used (recommended to be 128).
2. std::string send(int Taskid, int n, int k, __uint128_t msg): returns a binary string of length n representing the departure order of pigeons ('0' for black, '1' for white). The binary string encodes the 128-bit message msg.
3. __uint128_t receive(int Taskid, int k, const std::string &msg): recovers and returns the 128-bit message from the landing order provided in msg.

For languages where __uint128_t is not available, use the available arbitrary precision integer type.

outputFormat

This is an interactive communication problem. You are not writing to standard output. Instead, your implemented functions will be called by an interactive judge. Your solution must return the correct values for pigeon_num, send, and receive as described in the problem statement.

sample

Taskid=0, k=1, msg=5

pigeon_num returns 128; send returns a 128-character binary string representing the number 5 (i.e. 127 leading zeros followed by '101' at the end if using fixed length 128). receive correctly recovers the message 5.