Problem Description

Abusing the judging system of this problem will result in an account ban.

Special note: To make judging work properly, please delete #include "mpc.h" at the beginning of your code and add the following code snippet:

#include <array>
struct player{
    bool last_message;
    std::array<int, 4096> memory;
};
int precalc(int n, int m);
bool transmit(player &player, int round, int position);

This is an interactive problem.

There are $n+1$ people, numbered from $0$ to $n$. Person $i(0 \le i \le n-1)$ has an integer $a_i$ in $[0,2^m-1]$.

Person $n$ wants to know the value of $a_0+a_1+\cdots+a_{n-1}$. To do this, they can communicate as follows:

1. First, choose the number of communication seconds $N$.
2. In each of the next $N$ seconds, all $i(0 \le i \le n-1)$ simultaneously send one bit of information to $(i+1)$.

• The message will be received before the next second begins. In particular, messages sent in the last second will not be received.
• Besides this, no other form of communication is allowed.

You need to complete this task using as few communication seconds as possible.

Implementation details

Please make sure your program starts with #include "mpc.h".

You do not need to and should not implement main. You need to implement the following two functions:

int precalc(int n, int m);

• n is the number of people, and m is the value range parameter of the integers.
• You need to return the number of communication seconds $N$.

bool transmit(player &player, int round, int position);

• round is the current communication second, taking an integer value in $[1,N]$.
• position is the index of the person currently transmitting information, taking an integer value in $[0,n]$.
• player is a struct type describing the person currently transmitting. This struct is implemented in mpc.h. It contains the following two member variables:
  • A boolean variable last_message, representing the information sent by the previous person in the previous second. If position is $0$ or round is $1$, then last_message is guaranteed to be $0$.
  • An integer array memory of length $4096$, describing the person’s “memory”.
    • In the transmit function, this array may be modified arbitrarily.
    • player.memory can only be modified inside transmit. If player.memory is not modified in transmit, then when the same person transmits multiple times, player.memory stores the same value each time.
    • The initial value of player.memory is set by the following rules:
      • When position is not $n$, positions $0$ to $m-1$ of memory take values in $\{0,1\}$, describing the binary representation of $a_{\text{position}}$ from low bit to high bit (i.e., the $i$-th bit corresponds to weight $2^i$), and all other positions are $0$.
      • Otherwise, all positions of the array are $0$.
• You need to return the information (one bit) that this person transmits to the next person in this second.
  • When position is $n$ or round is $N$, this return value will not have any effect.

After all calls to transmit end, you must ensure that in person $n$’s player.memory, the first $2200$ positions all take values in $\{0,1\}$, and the corresponding binary number is the sum of all $a_i$.

Under the problem conditions and Constraints, the interaction library consumes at most $0.15$ seconds of time and $128\text{MiB}$ of memory.

Using other forms of communication in the program, including but not limited to using global variables, will be considered as attacking the interaction library.

How to run the test program

A reference implementation of the interaction library, grader.cpp, is provided in the problem directory. The interaction library used in the final test is different from this implementation, so your solution must not depend on specific implementation details of the library.

You need to compile in this problem directory using the following command to obtain the executable:

g++ mpc.cpp grader.cpp -o mpc -O2 -std=c++17 -lm

The executable will read input from standard input in the following format:

• The first line contains two integers $n, m$.
• The next $n$ lines each contain $m$ 01 integers, from low to high, representing the binary representation of each person’s integer. The two integers in each line are separated by a space.

After reading is complete, the interaction library will first call init(n,m) once to get $N$, and then perform $\max(0,N)$ rounds of calls. In round $k(1 \le k \le \max(0,N))$, it will call all transmit functions with $\text{round}=k$, and after finishing the calls, it will update the corresponding player.last_message values.

• If $N \le 0$, then no calls will be made, and all player.memory values remain at their initial values.

If your program runs correctly, the executable will output data in the following format:

• The first line is a string of length $2200$, representing the sum of all $a_i$, output in binary from low bit to high bit.
• The second line is a string that outputs, in order, the number represented by the first $2200$ positions of person $n$’s player.memory after all interaction ends. There are no spaces between adjacent digits.
• The third line: if the above two strings are different, it will tell you the answer is wrong; otherwise, it will output your score on this testdata.

This problem directory also includes sample files 1.in, 1.ans, and a sample program mpc.cpp. The sample program can pass the provided sample.

Hint

Subtasks

For all testdata, $1 \le n,m \le 2000$.

This problem has 10 subtasks, each worth 10 points.

Scoring

This problem is first subject to the same limits as traditional problems, e.g. a compilation error will cause the entire problem to score 0 points; runtime errors, exceeding the time limit, exceeding the memory limit, etc. will cause the corresponding test point to score 0 points.

Besides the above conditions, on a test point, if $N > n+m+100$, or after all transmit calls end, the binary number corresponding to the first $2200$ bits in person $n$’s player.memory is not the sum of all $a_i$, you will get $0$ points. Otherwise, based on the value of $(N - n - m)$, your score on that test point is computed according to the following table:

Your score for a subtask is the minimum score among all test points in that subtask.

Translated by ChatGPT 5