A. Balance the Bits--Codeforces Round #712 (Div. 1)

Problem - 1503A - Codeforces

A. Balance the Bits

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

A sequence of brackets is called balanced if one can turn it into a valid math expression by adding characters '+' and '1'. For example, sequences '(())()', '()', and '(()(()))' are balanced, while ')(', '(()', and '(()))(' are not.

You are given a binary string ss of length nn. Construct two balanced bracket sequences aa and bb of length nn such that for all 1≤i≤n1≤i≤n:

• if si=1si=1, then ai=biai=bi
• if si=0si=0, then ai≠biai≠bi

If it is impossible, you should report about it.

Input

The first line contains a single integer tt (1≤t≤1041≤t≤104) — the number of test cases.

The first line of each test case contains a single integer nn (2≤n≤2⋅1052≤n≤2⋅105, nn is even).

The next line contains a string ss of length nn, consisting of characters 0 and 1.

The sum of nn across all test cases does not exceed 2⋅1052⋅105.

Output

If such two balanced bracked sequences exist, output "YES" on the first line, otherwise output "NO". You can print each letter in any case (upper or lower).

If the answer is "YES", output the balanced bracket sequences aa and bb satisfying the conditions on the next two lines.

If there are multiple solutions, you may print any.

Example

input

Copy

3
6
101101
10
1001101101
4
1100

output

Copy

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

Note

In the first test case, a=a="()()()" and b=b="((()))". The characters are equal in positions 11, 33, 44, and 66, which are the exact same positions where si=1si=1.

In the second test case, a=a="()()((()))" and b=b="(())()()()". The characters are equal in positions 11, 44, 55, 77, 88, 1010, which are the exact same positions where si=1si=1.

In the third test case, there is no solution.

==================================================================================================================================================

C题很多套路是，1特殊到一般，2排除不可能情况之后的构造。

本题是第二种

首先0就代表了上下必须要有一个位置是右括号),显然出现在开头可以直接跳过，同理结尾也是如此

然后考虑奇偶性，1的话上下一样，而我们左括号必须是总长度一半，如果1是奇数，那么0必定是奇数

这样总长度才是偶数，而1是奇数时，左右括号一定是一偶一奇，同理0里面也是1偶一奇

假设 1里面左偶右奇  那么上下1都必定是左偶右奇，而0里面的一奇一偶，只可能满足一方的，反转之后就无法满足令一方。故1必定是偶数。

然后我们考虑构造，数据范围可以看出构造一定是线性的。这个只能靠感性猜测，我们猜先填1会比较方便，一半左一半右

1      1                 1          1

（   （               ）             ）

然后我们猜测0的位置

1     0  1   0      1       1

（    （  （     ）      ）   ）

1     0   1        1    0   1

（ （   ）    （  ）   ）

可以看出0其实是连续翻转着填的

总之此类题目不要想太多深奥结论，就从最简单的特殊情况，奇偶性，考虑简单线性递推即可。结果总会意外巧合。

# include<iostream>
using namespace std;
char ans[200000+10];
 
int main ()
{
 
 
 
    int t;
 
    cin>>t;
 
    while(t--)
    {
 
 
    int len;
 
    cin>>len;
 
 
        string s;
 
        cin>>s;
 
        if(s[0]=='0'||s[s.length()-1]=='0')
        {
            cout<<"NO"<<endl;
 
            continue;
 
        }
 
        int cnt0=0,cnt1=0;
 
        for(int i=0;i<s.length();i++)
        {
            if(s[i]=='0')
                cnt0++;
            else
                cnt1++;
 
        }
 
 
        if(cnt0%2)
        {
            cout<<"NO"<<endl;
 
            continue;
 
        }
 
        int cnt00=0,cnt11=0;
 
        for(int i=0;i<s.length();i++)
        {
            if(s[i]=='1')
            {
                cnt11++;
 
                if(cnt11<=cnt1/2)
                {
                    ans[i]='(';
                }
                else
                {
                    ans[i]=')';
                }
            }
            else
            {
                cnt00++;
 
                if(cnt00&1)
                {
                    ans[i]='(';
 
                }
                else
                {
                    ans[i]=')';
 
                }
            }
        }
 
        cout<<"YES"<<endl;
 
        for(int i=0;i<s.length();i++)
        {
            cout<<ans[i];
        }
 
        cout<<endl;
 
        for(int i=0;i<s.length();i++)
        {
            if(s[i]=='0')
            {
                if(ans[i]=='(')
                {
                    cout<<')';
                }
                else
                {
                    cout<<'(';
                }
            }
            else
            {
                cout<<ans[i];
            }
        }
 
        cout<<endl;
 
 
 
    }
    return 0;
 
}