P17120 [Algo Beat 009 & MROI-R1] Parallel Parentheses

:::warning[Must-read Information]{open} - This problem supports only the C++ language. - Please do not submit using C++14 (GCC 9). - During the contest, it is forbidden to exploit vulnerabilities in the judging library, hack the judging library, or use other methods to obtain undeserved scores. Otherwise, your score for this problem will be cancelled. ::: **This is a distributed computing problem**. Little R gives you a string $S$ of length $M$ consisting of `(` and `)`. Let $S_{i,j}$ denote the substring of $S$ from the $i$-th character to the $j$-th character, i.e., $S_iS_{i+1}\dots S_{j}$. You need to find the maximum value of $r-l+1$ such that $S_{l,r}$ is a valid parentheses string. :::info[What is a valid parentheses string?] - The empty string is valid. - If $A$ is valid, then $(A)$ is valid. - If $A, B$ are valid, then $AB$ is valid. ::: ### [Definition of the Distributed Environment] - There are $N$ nodes in the system, numbered $0, 1, \dots, N-1$. - The string $S$ is evenly divided into $N$ blocks (it is guaranteed that $M$ is a multiple of $N$), each of length $L = {M \over N}$. - Node $id$ is responsible for maintaining block $id$, i.e., the substring $S_{id \times L, (id+1) \times L - 1}$. - Nodes can send messages to each other through a complete-graph network, i.e., one node can send a message to any other node. ### [List of Supported Functions] - `GetN()`: returns the total number of nodes $N$. - `GetMyId()`: returns the id $id$ of the current node. - `GetM()`: returns the total length $M$ of the string. - `GetCharAt(long long i)`: returns $S_i$. **Note**: the requested index $i$ must be within the range that the current node is responsible for. - `PutInt(int target, int val)` / `PutLL(int target, long long val)`: puts data `val` into the buffer to be sent to `target`, taking $4, 8$ bytes respectively. - `Send(int target)`: sends the contents of the buffer. **Note**: if the message is empty, unpredictable errors may occur. - `Receive(int source)`: blocks, waits for, and receives a message from `source`. - `GetInt(int source)` / `GetLL(int source)`: reads data from the received message. **Note**: `GetInt` reads only the first $4$ bytes of the current buffer, and `GetLL` reads only the first $8$ bytes (after reading, they are removed from the buffer). If the current buffer size is insufficient, unpredictable errors may occur. The sample grader does not check this. Please declare these functions at the beginning of your code: ```cpp int GetN(); int GetMyId(); long long GetM(); char GetCharAt(long long i); void PutInt(int target, int val); void PutLL(int target, long long val); void Send(int target); void Receive(int source); int GetInt(int source); long long GetLL(int source); ``` ### [Implementation] You need to implement a function `long long LongestValidParentheses()`. **Only when $\bm {id}$ is $\bm 0$ will your return value be considered as your answer**. When $id \neq 0$, you may return any value, but note that you must return something (otherwise it is undefined behavior). ### [Special Limits] - Time and memory limits: the grader and the function you implement share $5$ seconds and $512 \text{ MB}$. It is guaranteed that the **time available for you to use** is at least $4$ seconds, and the memory is at least $256 \text{ MB}$. **Note**: the time and memory you use are the sum over all $N$ nodes. - Communication limit: during its entire lifetime, for each node, the total size of all messages sent and received must not exceed **$\bm{37\,500\,000}$ bytes**. **Special note**: the same static array is independent across different processes, and can be reused within each process without causing data contamination. ### [Scoring] Let the **sum** of the communication volume (total bytes of Send and Receive) over **all nodes** be $C$. **Note**: if the sent data type is `int`, it takes $4$ bytes; otherwise (type `long long`), it takes $8$ bytes. $$ \text{Score}(C)= \begin{cases} 100 & C\le 424\\ \max\left\{1,\left\lfloor 1+99\cdot \frac{\frac{1}{1+25t}-\frac{1}{26}} {1-\frac{1}{26}} \right\rfloor\right\} & 424

Your program should not read any content from standard input. Note that the sample input is the input of the sample grader. ### [Sample Grader Input Format] - The first line contains two integers $N, M$. - The second line contains a string $S$ consisting only of `(` and `)`, with length $M$.

Your program should not write any content to standard output.

### [Constraints] - $1 \le N \le 16$. - $1 \le M \le 1.6 \times 10^7$. - $1 \le L \le 1\,066\,666$. - $M \bmod N = 0$. Except for the sample, this problem has only one Subtask, and the final score during evaluation is the minimum score among this Subtask. ::cute-table{tuack} |Subtask ID|Special Property|Dependent Subtasks|Score| |:-:|:-:|:-:|:-:| |$0$|Sample|None|$0$| |$1$|None|$0$|$100$| Translated by ChatGPT 5