CF1503A Balance the Bits

如果一个括号序列可以通过添加字符 $+$ 和 $1$ 变成一个合法的数学表达式，则称该括号序列是平衡的。例如，序列 "(())()"、"()" 和 "(()(()))" 是平衡的，而 ")("、"(()" 和 "(()))(" 不是。 给定一个长度为 $n$ 的二进制字符串 $s$。请构造两个长度为 $n$ 的平衡括号序列 $a$ 和 $b$，使得对于所有 $1\le i\le n$： - 如果 $s_i=1$，则 $a_i=b_i$； - 如果 $s_i=0$，则 $a_i\ne b_i$。 如果无法构造，请输出相应信息。

第一行包含一个整数 $t$（$1\le t\le 10^4$），表示测试用例的数量。 每个测试用例的第一行包含一个整数 $n$（$2\le n\le 2\cdot 10^5$，且 $n$ 为偶数）。 接下来一行包含一个长度为 $n$ 的字符串 $s$，仅由字符 $0$ 和 $1$ 组成。 所有测试用例中 $n$ 的总和不超过 $2\cdot 10^5$。

如果存在满足条件的两个平衡括号序列，第一行输出 "YES"。否则输出 "NO"。你可以使用大写或小写字母。 如果答案为 "YES"，则在接下来的两行分别输出满足条件的括号序列 $a$ 和 $b$。 如果有多组解，输出任意一组均可。

在第一个测试用例中，$a=$"()()()"，$b=$"((()))"。在第 $1$、$3$、$4$、$6$ 位字符相等，正好是 $s_i=1$ 的位置。 在第二个测试用例中，$a=$"()()((()))"，$b=$"(())()()()"。在第 $1$、$4$、$5$、$7$、$8$、$10$ 位字符相等，正好是 $s_i=1$ 的位置。 在第三个测试用例中，无解。 由 ChatGPT 4.1 翻译