P11050 [IOI 2024] Message Tamperer

Do not use $\texttt{\#include "message.h"}$. Please submit in C++ 20, and paste the following at the top of your file: ```cpp #include std::vector send_packet(std::vector); void send_message(std::vector, std::vector); std::vector receive_message(std::vector); ```

## Task Description Aisha and Basma are two friends who communicate with each other. Aisha has a message $M$ that she wants to send to Basma. The message is a sequence of $S$ bits (i.e., some 0s and 1s). Aisha communicates with Basma by sending **packets**. A packet is a sequence of $31$ bits, with positions indexed from $0$ to $30$. To send the message $M$ to Basma, Aisha sends several packets. However, a third person, Cleopatra, is sabotaging the communication between Aisha and Basma and can **tamper** with the sent packets. In each packet, Cleopatra can modify the bits at exactly $15$ positions. More specifically, given an array $C$ of length $31$ where each element is either $0$ or $1$, its meaning is: * $C[i] = 1$ means the bit at position $i$ can be modified by Cleopatra. We call such positions **controlled** by Cleopatra. * $C[i] = 0$ means the bit at position $i$ cannot be modified by Cleopatra. The array $C$ contains exactly $15$ ones and $16$ zeros. When sending the message $M$, the set of positions controlled by Cleopatra is the same for all packets. Aisha knows exactly which $15$ positions are controlled by Cleopatra. Basma only knows that $15$ positions are controlled, but does not know which ones. Let $A$ be the packets Aisha chooses to send (called the **original packets**). Let $B$ be the packets Basma receives (called the **tampered packets**). For each $i$ with $0 \leq i < 31$: * If Cleopatra cannot control the bit at position $i$ ($C[i]=0$), then Basma will receive the $i$-th bit that Aisha sent ($B[i]=A[i]$). * Otherwise, if Cleopatra controls the bit at position $i$ ($C[i]=1$), then the value of $B[i]$ is decided by Cleopatra. After each packet is sent, Aisha immediately learns the content of the tampered packet. After Aisha finishes sending all packets, Basma receives all tampered packets **in the sending order**, and she must reconstruct the original message $M$. Your task is to design and implement a strategy so that when Aisha sends the message $M$ to Basma, Basma can recover $M$ from the tampered packets. In particular, you need to implement two functions. The first function performs Aisha's actions: given the message $M$ and the array $C$, send several packets to transmit the message. The second function performs Basma's actions: given several tampered packets, recover the original message $M$. ## Implementation Details The first function you need to implement is: ``` void send_message(std::vector M, std::vector C) ``` * $M$: an array of length $S$, describing the message Aisha wants to send to Basma. * $C$: an array of length $31$, marking the positions in a packet that are controlled by Cleopatra. * In each test case, this function can be called **at most 2100 times**. This function calls the following function to send a packet: ``` std::vector send_packet(std::vector A) ``` * $A$: the original packet (an array of length $31$), representing the bits Aisha sends. * This function returns the tampered packet $B$, representing the bits Basma receives. * During one call to `send_message`, this function can be called at most $100$ times. The second function you need to implement is: ``` std::vector receive_message(std::vector R) ``` * $R$: an array describing several tampered packets. These packets come from the packets Aisha sent during one call to `send_message`, and they are listed in Aisha's sending order. Each element of $R$ is an array of length $31$, representing one tampered packet. * This function should return an array containing $S$ bits, equal to the original message $M$. * In each test case, this function may be called **multiple times**. For each call to `send_message`, there will be **exactly one** corresponding call to this function. The **call order** of `receive_message` does not have to match the order of the corresponding `send_message` calls. Note that in the grading system, the two functions `send_message` and `receive_message` are called in **different programs**.

N/A

N/A

## Constraints * $1 \leq S \leq 1024$. * $C$ has exactly $31$ elements, with $16$ zeros and $15$ ones. ## Subtasks and Scoring If in any test case, the calls to the function ``send_packet`` do not follow the rules above, or the return value of some call to `receive_message` is not correct, then your solution gets $0$ points for that test case. Otherwise, let $Q$ be the maximum, over all test cases, of the number of times `send_packet` is called during one call to `send_message`. Let $X$ be: - $1$, if $Q \leq 66$. - $0.95 ^ {Q - 66}$, if $66 < Q \leq 100$. - $0$, if $100 < Q$. Then the score is computed by: | Subtask | Score | Additional Constraints | | :----: | :----------: | -------------------- | | 1 | $10 \cdot X$ | $S \leq 64$ | | 2 | $90 \cdot X$ | No additional constraints. | Note that in some test cases, the behavior of the grader is **adaptive**. This means that the return value of `send_packet` may depend on its input and on the return values of previous calls. ## Example Consider the following call. ``` send_message([0, 1, 1, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]) ``` The message Aisha tries to send to Basma is $[0, 1, 1, 0]$. Bits $0$ to $15$ of the packet cannot be modified by Cleopatra, while bits $16$ to $30$ can be modified by Cleopatra. To make this example easier to explain, we assume that Cleopatra behaves deterministically: she alternates between filling the bits she controls with $0$ and $1$. That is, she sets the first position she controls to $0$ (position $16$ in the example), the second controlled position to $1$ (position $17$), the third controlled position to $0$ (position $18$), and so on. One possible choice Aisha can make is to send two bits of the original message in one packet. For example, she does it as follows: she sends the first bit using the first $8$ positions she controls, and sends the second bit using the next $8$ positions she controls. So Aisha sends the following packet: ``` send_packet([0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]) ``` Since Cleopatra can change the last $15$ bits, Aisha decides to set them arbitrarily, because they may be overwritten. With Cleopatra's assumed strategy, the function returns: $[0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0]$. Aisha decides to send the last two bits of $M$ in the second packet, similarly to before: ``` send_packet([1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]) ``` With Cleopatra's assumed strategy, the function returns: $[1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0]$. Aisha could send more packets, but she does not. Then the grader makes the following call: ``` receive_message([[0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0], [1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0]]) ``` Basma recovers the message $M$ as follows. From each packet, she extracts the first bit that appears twice consecutively, and the last bit that appears twice consecutively. That is, she extracts two bits $[0, 1]$ from the first packet, and two bits $[1, 0]$ from the second packet. Putting them together, she recovers the message $[0, 1, 1, 0]$, which is the correct return value for the call to `receive_message`. It can be proven that under the assumed strategy of Cleopatra, for a message of length $4$, no matter what the value of $C$ is, Basma can correctly recover $M$ in this way. However, in general, this is not correct. ## Sample Grader The sample grader is not adaptive. Cleopatra behaves deterministically and alternates between filling the bits she controls with $0$ and $1$, just like she did in the example. Input format: **The first line of input contains an integer $T$, specifying the number of test cases.** Then there are $T$ test cases, each described in the following format: ``` S M[0] M[1] ... M[S-1] C[0] C[1] ... C[30] ``` Output format: The sample grader outputs the results for the $T$ test cases in the input order, in the following format: ``` K L D[0] D[1] ... D[L-1] ``` Here, $K$ is the number of calls to `send_packet`, $D$ is the message returned by `receive_message`, and $L$ is its length. Translated by ChatGPT 5