Background

Do not use $\texttt{\#include "message.h"}$.

Please submit in C++ 20, and paste the following at the top of your file:

#include <vector>

std::vector<bool> send_packet(std::vector<bool>);
void send_message(std::vector<bool>, std::vector<bool>);
std::vector<bool> receive_message(std::vector<std::vector<bool>>);

Problem Description

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<bool> M, std::vector<bool> 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<bool> send_packet(std::vector<bool> 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<bool> receive_message(std::vector<std::vector<bool>> 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.

Hint

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:

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