括号（Brackets）

题目描述

这是一个交互式 / 函数实现题。

邪恶的 Doofenshmirtz 准备占领 Plovdiv。为了阻止他，特工 Perry 需要破解他电脑上的密码。

你只知道密码是一个长度为 $N$ 的括号串，只由普通括号 ( 和 ) 组成。并且保证：

• $N$ 为偶数；
• 密码中左括号 ( 和右括号 ) 的数量相等。

你可以调用评测库提供的函数 isValid(L, R)。它会告诉你密码中从第 $L$ 个字符到第 $R$ 个字符组成的子串是否是一个合法括号序列。字符串下标从 $1$ 开始。

合法括号序列定义如下：

• () 是合法括号序列；
• 如果 $A$ 是合法括号序列，那么 (A) 也是合法括号序列；
• 如果 $A$ 和 $B$ 都是合法括号序列，那么它们的拼接 $AB$ 也是合法括号序列。

不过，反病毒程序会在你询问次数超过 $Q$ 次时触发。因此，你需要在不超过 $Q$ 次询问的条件下恢复整个密码。

实现细节

你需要包含头文件：

#include "brackets.h"

你需要实现如下函数：

std::string findBrackets(int N, int Q);

该函数会被评测程序调用恰好一次。

参数含义如下：

• N：密码长度；
• Q：最多允许调用 isValid 的次数。

你需要返回一个长度为 $N$ 的字符串，表示你恢复出的密码。

评测库提供如下函数：

bool isValid(int L, int R);

它会返回密码中区间 $[L,R]$ 是否是一个合法括号序列。

调用 isValid(L, R) 时必须满足：

$$1 \le L \le R \le N.$$

如果你的程序调用次数超过 $Q$，或者调用时下标非法，评测结果为错误。

isValid 的时间复杂度为 $O(1)$。

你的程序只需要实现 findBrackets，不要实现 main 函数，不要从标准输入读入，也不要向标准输出输出内容。你可以定义任意辅助函数、全局变量和常量。

Hydro 评测说明

本题在 Hydro OJ 上采用函数实现题形式。

评测程序会从测试数据文件中读取真实密码，然后调用你的 findBrackets(N, Q)。如果你返回的字符串与真实密码完全相同，并且所有询问合法、询问次数不超过 $Q$，则该测试点通过。

为了适配 Hydro OJ，本题下发的 brackets.h 已经包含评测主程序。评测程序最终只输出一个整数：

• 1：通过该测试点；
• 0：未通过该测试点。

因此请不要在程序中输出任何额外内容。

本地测试输入格式

虽然选手程序本身不需要读入，但若使用下发的 brackets.h 本地测试，测试数据格式如下：

第一行包含两个整数 $N,Q$。

第二行包含一个长度为 $N$ 的字符串，表示真实密码。

本地测试输出格式

评测程序输出一个整数：

• 若你的函数成功恢复密码，输出 1；
• 否则输出 0。

示例通信

假设真实密码为：

((()))

且评测程序调用：

findBrackets(6, 9)

一次可能的交互过程如下：

调用	返回值
isValid(1, 6)	true
isValid(1, 2)	false
isValid(2, 4)
isValid(2, 5)	true
isValid(3, 4)

此时可以确定密码为：

((()))

于是 findBrackets 应返回字符串 "((()))"。

样例测试

样例输入 #1

6 9
((()))

样例输出 #1

1

数据范围

对于所有测试数据：

$$1 \le N \le 10^5.$$

并保证 $N$ 为偶数，密码中左括号和右括号数量相等。

子任务

子任务	分值	附加限制
$1$	$14$	$1 \le N \le 1000$，$Q=\dfrac{N^2}{4}$，整个密码本身是合法括号序列
$2$	$7$	$1 \le N \le 1000$，$Q=\dfrac{N^2}{4}$
$3$	$57$	$1 \le N \le 10^5$，$Q=N-1$，整个密码本身是合法括号序列
$4$	$22$	$1 \le N \le 10^5$，$Q=N-1$

@下发的头文件