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

:::warning[必读信息]{open} - 本题仅支持 C++ 语言。 - 请勿使用 C++14 (GCC 9) 提交。 - 比赛期间，禁止利用评测库漏洞、hack 评测库等方式获得不应得的分数，否则将被取消此题成绩。 ::: **这是一道分布式计算题**。 小 R 给了你一个长度为 $M$ 的由 `(` 和 `)` 组成的字符串 $S$。记 $S_{i,j}$ 表示 $S$ 第 $i$ 个字符到第 $j$ 个字符的子串，即 $S_iS_{i+1}\dots S_{j}$。 你需要求出最大的 $r-l+1$，满足 $S_{l,r}$ 是一个合法括号串。 :::info[什么是合法括号串？] - 空串合法； - 若 $A$ 合法，则 $(A)$ 合法； - 若 $A, B$ 合法，则 $AB$ 合法。 ::: ### 【分布式环境定义】 - 系统中共有 $N$ 个节点，编号为 $0, 1, \dots, N-1$。 - 字符串 $S$ 被均分为 $N$ 块（保证 $M$ 是 $N$ 的倍数），每块长度 $L = {M \over N}$。 - 节点 $id$ 负责维护第 $id$ 块，即子串 $S_{id \times L, (id+1) \times L - 1}$。 - 节点之间可以通过完全图网络互相发送消息，即一个节点可以向任意一个其他节点发送消息。 ### 【支持函数列表】 - `GetN()`：返回节点总数 $N$。 - `GetMyId()`：返回当前运行节点的编号 $id$。 - `GetM()`：返回字符串总长度 $M$。 - `GetCharAt(long long i)`：返回 $S_i$。 **注意**：请求的下标 $i$ 必须在当前节点的负责范围内。 - `PutInt(int target, int val)` / `PutLL(int target, long long val)`：将数据 `val` 放入发往 `target` 的缓冲区，分别占 $4, 8$ 字节。 - `Send(int target)`：将缓冲区的内容发送给 `target`。 **注意**：如果消息为空，可能出现无法预料的错误。 - `Receive(int source)`：阻塞等待并接收来自 `source` 的消息。 - `GetInt(int source)` / `GetLL(int source)`：从收到的消息中读取数据。 **注意**：`GetInt` 只会读取当前缓冲区前 $4$ 字节，`GetLL` 只会读取当前缓冲区前 $8$ 字节（读取后从缓冲区中移除）。如果当前缓冲区大小不足，可能出现无法预料的错误。样例评分器并没有判断这一点。 请在代码最前面声明这些函数： ```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); ``` ### 【实现方式】 你需要实现一个函数 `long long LongestValidParentheses()`。**当且仅当 $\bm {id}$ 为 $\bm 0$ 时，你的返回值会被认为是你得到的答案**。当 $id \neq 0$ 时，你可以返回任意值，但注意不能不返回（这是未定义行为）。 ### 【特殊限制】 - 时间、空间限制：评分器与你实现的函数共用 $5$ 秒，$512 \text{ MB}$。保证**可供你使用的时间**不少于 $4$ 秒，空间不少于 $256 \text{ MB}$。 **注意**：你使用的时间、空间均分别为 $N$ 个节点所使用的时间、空间之和。 - 通信限制：每个节点在整个运行生命周期内，发送和接收的消息总大小不能超过 **$\bm{37\,500\,000}$ 字节**。 **特别说明**：同一个静态数组在不同进程中是独立的，并可以在每个进程内部复用，不会造成数据污染。 ### 【评分方式】 记**所有节点**通信量（Send 与 Receive 字节之和）**之和**为 $C$。 **注意**：若发送信息类型为 `int`，则占用 $4$ 字节；否则（类型为 `long long`）占用 $8$ 字节。 $$ \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

你的程序不应从标准输入读取任何内容。注意样例输入是示例评分器输入。 ### 【示例评分器输入格式】 - 第一行两个整数 $N,M$。 - 第二行一个仅包含 `(` 和 `)` 的字符串 $S$，长度为 $M$。

你的程序不应向标准输出写入任何内容。

### 【数据范围】 - $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$。 除样例外，本题仅一个 Subtask，评测时最终得分为取该 Subtask 得分最小值。 ::cute-table{tuack} |子任务编号|特殊性质|依赖子任务|分值| |:-:|:-:|:-:|:-:| |$0$|是样例|无|$0$| |$1$|无|$0$|$100$|