CF1167D Bicolored RBS

如果一个字符串只包含字符“(”和“)” ，则称其为括号序列。如果通过在该序列中插入字符“+”和“1”可以得到一个正确的算术表达式，则称该括号序列为正规括号序列（简称 RBS）。例如，""、"(())" 和 "()()" 是 RBS，而 ")(" 和 "(()" 不是。 我们可以发现，RBS 中的每一个左括号都与某个右括号配对。基于此，我们可以定义 RBS 的嵌套深度为括号对的最大数量，使得第 $2$ 对括号嵌套在第 $1$ 对括号内，第 $3$ 对括号嵌套在第 $2$ 对括号内，依此类推。例如，"" 的嵌套深度为 $0$，"()()()" 的嵌套深度为 $1$，"()((())())" 的嵌套深度为 $3$。 现在，给定一个长度为偶数 $n$ 的 RBS $s$。你需要将 $s$ 中的每个括号染成红色或蓝色。由所有红色括号组成的括号序列 $r$ 必须是 RBS，由所有蓝色括号组成的括号序列 $b$ 也必须是 RBS。$r$ 和 $b$ 可以为空。你不能改变 $s$、$r$ 或 $b$ 中字符的顺序，且每个括号都必须被染色。 在所有可能的染色方案中，你需要选择一种，使得 $r$ 和 $b$ 的嵌套深度的最大值最小。如果有多种方案，输出任意一种即可。

第一行包含一个偶数 $n$（$2 \le n \le 2 \cdot 10^5$），表示 RBS $s$ 的长度。 第二行包含一个正规括号序列 $s$（$|s| = n$，$s_i \in \{ (,\ ) \}$）。

输出一个长度为 $n$ 的字符串 $t$，仅包含字符“0”和“1”。如果 $t_i$ 等于 0，则 $s_i$ 属于 RBS $r$，否则 $s_i$ 属于 $b$。

在第一个样例中，一种最优方案是 $s = $ "$\color{blue}{()}$"。$r$ 为空，$b = ()$。答案为 $\max(0, 1) = 1$。 在第二个样例中，最优方案是 $s = $ "$\color{red}{(}\color{blue}{(}\color{red}{)}\color{blue}{)}$"。$r = b = ()$，答案为 $1$。 在第三个样例中，可以让 $s = $ "$\color{red}{(}\color{blue}{((}\color{red}{)()}\color{blue}{)())}$"。$r = ()()$，$b = (()())$，答案为 $2$。 由 ChatGPT 4.1 翻译