P10213 [CTS2024] Multi-party Computation.

## 滥用本题评测将被封号 **特别注意**：为了能够正常评测，请删去代码开头的 `#include "mpc.h"` 并加入以下代码段： ```cpp #include struct player{ bool last_message; std::array memory; }; int precalc(int n, int m); bool transmit(player &player, int round, int position); ```

## 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: ```cpp #include struct player{ bool last_message; std::array 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: ```cpp 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$. ```cpp 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.

N/A

N/A

## Subtasks For all testdata, $1 \le n,m \le 2000$. This problem has 10 subtasks, each worth 10 points. | Subtask ID | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | | :--------: | :--: | :--: | :--: | :--: | :--: | :--: | :--: | :--: | :--: | :--: | | $n =$ | 5 | 1000 | 1000 | 1000 | 3 | 10 | 500 | 1000 | 1500 | 2000 | | $m =$ | 5 | 1 | 10 | 30 | 1000 | 1000 | 1000 | 1000 | 1500 | 2000 | ## 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: | $(N - n - m) \in$ | $[14,100]$ | $[12, 13]$ | $[9, 11]$ | $[6,8]$ | $[5,5]$ | $[4,4]$ | $(-\infty, 3]$ | | :---------------: | :--------: | :--------: | :-------: | :-----: | :-----: | :-----: | :------------: | | Score | 1 | 2 | 3 | 4 | 6 | 8 | 10 | Your score for a subtask is the minimum score among all test points in that subtask. Translated by ChatGPT 5