https://codeforces.com/contest/1504/problem/C
시간 1초, 메모리 256MB

input :

• t (1 ≤ t ≤ 104)
• n (2 ≤ n ≤ 2⋅104, n is even).
• s (n길이의 문자열)

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).
  균형잡힌 괄호를 만들 수 있으면 "YES"를 그렇지 않은 경우에는 "NO"를 출력하시오.

• If the answer is "YES", output the balanced bracket sequences a and b satisfying the conditions on the next two lines.
  "YES"를 출력한다면 균형잡힌 괄호 a와 b를 그 다음 두 줄에 출력하시오.

조건 :

• if si=1, then ai=bi
• if si=0, then ai≠bi
  si = 1일 때는 a와 b의 괄호가 동일해야 하고, 0일 때는 달라야만 한다.

---

괄호를 만들 때 1의 개수가 홀수 라면 어떻게 될까?
극단적으로
10000 인 경우 균형잡힌 것을 만들 수 없다. 양 옆의 괄호가 달라야 하기 때문에 하나는 조건을 만족시키지 못한다.

101001 인 경우
((()()
()(())
동일한 괄호에 대해 하나는 닫히는 괄호로 형성을 못하기 때문에 조건을 만족시키지 못한다.

1

1의 개수는 짝수여야 한다. 그리고 0의 경우에는 언제나 둘 다 달라야 하기 때문에
계속 열고 닫고 해준다는 생각으로 로테이션을 돌려준다.

import sys

t = int(sys.stdin.readline())
for _ in range(t):
    n = int(sys.stdin.readline())
    data = sys.stdin.readline().rstrip()
    cnt_one = 0
    for i in data:
        if i == '1':
            cnt_one += 1

    if data[0] == '0' or data[-1] == '0' or cnt_one % 2 == 1:
        print("NO")
        continue

    fir_ans, sec_ans = "", ""
    idx, record = 0, 1
    for i in range(n):
        if data[i] == '1':
            fir_ans += ')' if 2 * idx >= cnt_one else '('
            sec_ans += fir_ans[-1]
            idx += 1
        else:
            fir_ans += ')' if record == 1 else '('
            sec_ans += '(' if record == 1 else ')'
            record = -record

    print("YES")
    print(fir_ans)
    print(sec_ans)

Counter와 Pypy3가 느리다.. 코포에선 Python3가 파이파이 인지 모르겠다.