← 返回题目列表

Codeforces · 1503/A

A. 平衡位

中文机器翻译题面 查看原题

如果可以通过添加字符“+”和“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$$$。

如果有多个解决方案,您可以打印任何一个。

示例

输入 #1

3
6
101101
10
1001101101
4
1100

输出 #1

YES
()()()
((()))
YES
()()((()))
(())()()()
NO

注意

在第一个测试用例中,$$$a=$$$"()()()" 和 $$$b=$$$"((()))"。 $$$1$$$、$$$3$$$、$$$4$$$ 和 $$$6$$$ 位置上的字符相等,这些位置与 $$$s_i=1$$$ 的位置完全相同。

在第二个测试用例中,$$$a=$$$"()()((()))" 和 $$$b=$$$"(())()()()"。 $$$1$$$、$$$4$$$、$$$5$$$、$$$7$$$、$$$8$$$、$$$10$$$ 中的字符是相等的,它们与 $$$s_i=1$$$ 的位置完全相同。

在第三个测试用例中,没有解决方案。