P16542 [EGOI 2026] Population Census / Census

Because Luogu does not support interactive problems with communication among 100 processes, this problem provides a communication library but cannot be judged properly.

A little-known fact about Cesenatico is that there is a secret society living here, consisting of $N$ female informatics scientists. This society is very secretive; the members do not know each other. Each member has a unique ID: a non-negative integer $I$. The only way members can communicate is indirectly, by writing numbers with chalk at different locations in town. Every 100 years, the society conducts a population census to count how many members there are. After the census ends, each member should know the total number of members in the society. The census lasts for multiple days. On each day, every member who is still participating in the process must choose and perform exactly one action: **read**, **write**, or **stop** participating. - If a member chooses **read**, she selects a location $P$. During the day, she visits that location and reads the number written there. - If a member chooses **write**, she selects a location $P$ and a number $V$. In the evening, she visits that location and changes the number there to $V$. Because it is already late, she cannot read the old number before writing the new one. - If a member chooses **stop**, she will take no actions on subsequent days (i.e., she no longer participates in the process). If a member sees another member writing a number, she might recognize the other person. Therefore, the society strictly forbids two or more members from choosing to write at the same location on the same day. (There is no such restriction for reading, because reading can be done discreetly.) If one or more members read a location on a day when another member intends to write a new number to that same location, all reads happen before the write. How should the society plan the census process so that the number of days needed for everyone to learn the correct total number of members is minimized? ### Implementation Details This is a communication (interactive) problem. Your program will have an unknown number ($1 \leq N \leq 100$) of instances running simultaneously. Each instance simulates one member of the society. There are $10^{18}$ locations. A location $P$ must satisfy $0 \leq P < 10^{18}$. Initially, the value written at every location is $V = 0$. A newly written value $V$ must always be an integer satisfying $0 \leq V \leq 10^9$. In most subtasks, $V$ can only be $0$ or $1$. See the “Scoring” section for more details. When an instance of your program starts, it should first read one line containing two integers $I$ and $M$ ($0 \leq I \leq M-1$): the unique ID of the member represented by this instance, and the total number of possible IDs. In each testdata, all instances will receive the same value of $M$ and different values of $I$. Note that some IDs might not be assigned to any member. Then, for each day of the census process, your program should choose the action it wants to perform and output one corresponding line: | **Action** | **Meaning** | |:-:|:-:| | $r$ $P$ | **Read location $P$.** After outputting this line, your program should read one line containing the current value written at $P$. | | $w$ $P$ $V$ | **Write the new value $V$ at location $P$.** If multiple instances write to the same $P$ on the same day, you will receive a **Not correct** verdict. Except for the samples and subtask $3$, you must output $0 \le V \le 1$; see the “Scoring” section for details. | | $!$ $N$ | **Answer and stop:** report that there are $N$ members and stop participating in the census. After answering, your program should exit normally. (Note that other instances of your program may continue running for a few more days.) | If any instance of your program answers with an incorrect value of $N$, violates the protocol, uses more than $500$ days, or exceeds the (per-process) time/memory limits, your submission will be judged as Not correct. Otherwise, your program will be judged as (Partially) Correct on the testdata, and it will be scored based on the value $D$ (the maximum number of days taken by any instance to answer). To get full score, you need to solve every testdata with $D \leq 61$ and $V \leq 1$. See the “Scoring” section for details. **Flush your output.** If you do not use the provided template, make sure to flush standard output after printing each line, otherwise your program may be judged as Not correct. In Python, if you use `input()` to read lines, this happens automatically. In C++, `cout

#

#

### Samples The first sample. Each pair of columns shows the interaction between the judge program and one instance. :::align{center}  ::: The second sample. :::align{center}  ::: ### Sample Explanation **First sample.** The society has $N = 5$ members, with IDs $0, 1, 2, 3, 4$, and $M = 100$ (for subtasks 1, 3, and 4). Instance $i$ corresponds to the member whose ID is $i$. The interaction above is just one possible legal sequence of actions; it does *not* mean this is an efficient or reasonable strategy. It is only used to demonstrate how interaction works. **Second sample.** The society has $N = 2$ members, with IDs 0 and 3, and $M = 8000$ (for subtasks 2, 3, and 4). On day 1, the member with ID 0 writes 0 at location 0 (no change), and the member with ID 3 writes 1 at location 2. :::align{center}  ::: On day 2, the member with ID 0 writes 1 at location 1, and the member with ID 3 reads the same location. Note that reading happens during the day, before the evening write. Therefore, the member with ID 3 still sees 0. :::align{center}  ::: On day 3, they both read location 2, which contains 1. On day 4, the member with ID 0 answers that there are $2$ members (correct), while the member with ID 3 reads the 1 at location 1. The member with ID 0 exits immediately after that and no longer participates in the following days. Finally, on day $D = 5$, the remaining member also answers correctly with $N = 2$. ### Constraints - $1 \leq N \leq 100$. - $1 \leq M \leq 100\ 000$. - You can use at most $500$ days. ### Scoring Your program will be tested on testdata split into several subtasks. To receive the score for a subtask, you must solve all testdata in that subtask correctly. - **Subtask 0** [$0$ points]: Samples (you may write any integer $0 \le V \le 1\,000\,000\,000$). - **Subtask 1** [$11$ points]: $M \le 100$, and the $N$ members have IDs $0, 1, \dots, N - 1$. - **Subtask 2** [$12$ points]: $1 \le N \le 2$. - **Subtask 3** [$22$ points]: $M \le 8000$, and you may write any integer $0 \le V \le 1\,000\,000\,000$. - **Subtask 4** [$55$ points]: No additional constraints. **In subtasks 1, 2, and 4, in each write operation you can only write $V = 0$ or $V = 1$.** Let $X_s$ be the maximum score for subtask $s$ (as above), and let $D_s$ be the maximum number of days used by your program on the tests of subtask $s$. Then: $$ \begin{aligned} \text{score}_s = &\begin{cases} X_s & \text{if } D_s \le 61 \\ X_s \cdot (0.2 + 0.8 \cdot 1.01^{(60-D_s)}) & \text{if } 61 < D_s \le 500 \\ 0 & \text{if } 500 < D_s. \end{cases} \end{aligned} $$ The value of $score_s$ is rounded to the nearest integer for each subtask, and your total score is the sum of these scores. To get full score for this problem, you need $D \leq 61$ and $V \leq 1$ for every testdata. :::align{center}  ::: Total score, assuming each subtask is solved with the same maximum $D$. ### Testing To make it easier to test your solution, we provide a simple tool. Using this tool is optional. Note that Luogu’s judge is different from this testing tool. To use the tool, you need an input file. You can use the provided sample inputs `census.input0.txt` and `census.input1.txt`, or create your own. The input file should start with a line containing the number of members $N$ and the number of possible IDs $M$, followed by a line containing $N$ numbers specifying the IDs of the society members. For a Python program, assumed to be `census.py` (typically run as `pypy3 census.py`), run the testing tool as follows: ``` python3 testing_tool.py pypy3 census.py < census.input0.txt ``` For a C++ program, first compile your solution: ``` g++ -DEVAL -std=gnu++20 -O2 -pipe -static -s -o census census.cpp ``` Then run the testing tool: ``` python3 testing_tool.py ./census < census.input0.txt ``` Note that in this problem, standard output is used to interact with the judge, so it should not be used for debugging. Instead, you can use standard error output (stderr). In C++, you can use `cerr