Problem:


Score : 400 points

Problem Statement

You are given a string S of length N consisting of ( and ). Your task is to insert some number of ( and ) into S to obtain a correct bracket sequence.

Here, a correct bracket sequence is defined as follows:  

() is a correct bracket sequence.

If X is a correct bracket sequence, the concatenation of (, X and ) in this order is also a correct bracket sequence.

If X and Y are correct bracket sequences, the concatenation of X and Y in this order is also a correct bracket sequence.

Every correct bracket sequence can be derived from the rules above.

Find the shortest correct bracket sequence that can be obtained. If there is more than one such sequence, find the lexicographically smallest one.

Constraints

The length of S is N.

1 ≤ N ≤ 100

S consists of ( and ).

Input

Input is given from Standard Input in the following format:

N
S

Output

Print the lexicographically smallest string among the shortest correct bracket sequences that can be obtained by inserting some number of ( and ) into S.

Sample Input 1

3
())

Sample Output 1

(())

Sample Input 2

6
)))())

Sample Output 2

(((()))())

Sample Input 3

8
))))((((

Sample Output 3

(((())))(((())))



Sample input:
3
())


Sample output:
(())

Submission status: Wrong Answer

Solution code:
N = int(input())
S = list(input())
L = 0
out = []
for i in range(N):
    X = S[i]
    if X=="(":
        L += 1
        out.append("(")
    elif X==")":
        if L>0:
            L += -1
            out.append(")")
        else:
            out.append("()")
for i in range(L):
    out.append(")")
print("".join(out))

Submission status: Wrong Answer

Solution code:
n=int(input())
s=input()
c=0
x=s.rfind(")")
if x==-1:
  print(s+")"*n)
else:
  s1=s[0:x+1]
  s2=s[x+1:]+")"*len(s[x+1:])
  if s1.count("(")>=s1.count(")"):
    print(s1+s2+")"*(s1.count("(")-s1.count(")")))
  else:
    print("("*(-s1.count("(")+s1.count(")"))+s1+s2)

Submission status: Wrong Answer

Solution code:
n=int(input())
s=input()
c=0
x=s.rfind(")")
if x==-1:
  print(s+")"*n)
else:
  s1=s[0:x+1]
  s2=s[x+1:]+")"*len(s[x+1:])
  if s1.count("(")>=s1.count(")"):
    print(s1+")"*(s1.count("(")-s1.count(")"))+s2)
  else:
    print("("*(-s1.count("(")+s1.count(")"))+s1+s2)

Submission status: Wrong Answer

Solution code:
n = int(input())
s = list(input())

c0 = 0
c1 = 0
z0 = 0
z1 = 0
for i in range(n):
    if s[i] == "(":
        c0 += 1
    else:
        if c0 > 0:
            c0 -= 1
        else:
            c1 += 1
z0 = c1
s = s[::-1]
for i in range(n):
    if s[i] == ")":
        c1 += 1
    else:
        if c1 > 0:
            c1 -= 1
        else:
            c0 += 1
z1 = c0
s = s[::-1]
ans = ["("]*z0 + s + [")"]*z1
print("".join(ans))

Submission status: Wrong Answer

Solution code:
n = int(input())
s = list(input())

c0 = 0
c1 = 0
z0 = 0
z1 = 0
for i in range(n):
    if s[i] == "(":
        c0 += 1
    else:
        c1 += 1
    if c0 < c1 and s[i] != "(":
        z0 += 1
    if c0 > c1 - z0 and s[i] != ")":
        z1 += 1

if s[-1] == ")":
    z1 -= 1
ans = ["("]*z0 + s + [")"]*max(z1,0)
print("".join(ans))

Submission status: Wrong Answer

Solution code:
n = int(input())
s = list(input())

c0 = 0
c1 = 0
z0 = 0
z1 = 0
for i in range(n):
    if s[i] == "(":
        c0 += 1
    else:
        c1 += 1
    if c0 < c1 and s[i] != "(":
        z0 += 1
    if c0 > c1 - z0 and s[i] != ")":
        z1 += 1
ans = ["("]*z0 + s + [")"]*max(z1-1,0)
print("".join(ans))

Submission status: Wrong Answer

Solution code:
n=int(input())
s=input()
tmp=0
ans=""
tt=""
for i in range(n):
    if s[i]==")":
        tmp-=1
        tt+=")"
    elif tmp>=0 and s[i]=="(":
        tmp+=1
        tt+="("
    elif tmp>0 and s[i-1]==")" and s[i]=="(":
        ans=ans+tt+")"*(tmp)
        tmp=1
        tt="("
    elif tmp<0 and s[i-1]==")" and s[i]=="(":
        tt="("*(-tmp)+tt
        ans=ans+tt
        tmp=1
        tt="("
if tmp<0:
    tt="("*(-tmp)+tt
    ans=ans+tt
if tmp>0:
    ans=ans+tt+")"*tmp
print(ans)

Submission status: Wrong Answer

Solution code:
input()
s=t=input()
l,r=p='()'
exec("t.replace(p,'');"*50)
c=t.count
print(l*c(r)+s+r*c(l))

Submission status: Wrong Answer

Solution code:
N = int(input())
S = input().strip()
C = {"(":0,")":0}
for i in range(N):
    C[S[i]] += 1
x = C["("]-C[")"]
if x>=0:
    S = S+")"*x
else:
    S = "("*(-x)+S
print(S)

Submission status: Wrong Answer

Solution code:
n = int(input())
s = input()
ans = ""
l=r=0
for i in range(n):
    if s[i]=="(": l+= 1
    else: r += 1
    if i+1 < n and s[i]+s[i+1]== ")(":
        ans += "("*max(l,r) + ")"*max(l,r)
        l=r=0
if max(l,r) != 0:ans += "("*max(l,r) + ")"*max(l,r)
print(ans)

Submission status: Wrong Answer

Solution code:
N=input()
S=input()
T=S
a,b=0,0
for i in range(len(S)+1):
  if i==len(S):
    if a-b>0:
      for i in range(a-b):
        T='('+T
    break
  if S[i]==')':
    a+=1
  else:
    if a-b>0:
      for i in range(a-b):
        T='('+T
    if a>0:
      b=0
    b+=1
    a=0
a,b=0,0
for i in range(len(T)):
  if T[i]==')':
    a+=1
  else:
    b+=1
for i in range(b-a):
  T=T+')'
print(T)

Submission status: Wrong Answer

Solution code:
N=input()
S=input()
T=S
s=''
a,b=0,0
for i in range(len(S)+1):
  if i==len(S):
    if a-b>0:
      for i in range(a-b):
        s='('+s
    T=s+T
    break
  if S[i]==')':
    a+=1
  else:
    if a-b>0:
      for i in range(a-b):
        s='('+s
    T=s+T
    s=''
    if a>0:
      b=0
    b+=1
    a=0
a,b=0,0
for i in range(len(T)):
  if T[i]==')':
    a+=1
  else:
    b+=1
for i in range(b-a):
  T=T+')'
print(T)

Submission status: Wrong Answer

Solution code:
import sys
#input = sys.stdin.buffer.readline

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()


def II(): return int(input())


def MI(): return map(int,input().split())


def MF(): return map(float,input().split())


def LI(): return list(map(int,input().split()))


def LF(): return list(map(float,input().split()))


def TI(): return tuple(map(int,input().split()))


# rstrip().decode('utf-8')


def main():
	n=II()
	s=input()
	
	A=[]
	if s[0]==")":
		A.append(0)
	s+="0"
	cnt=1
	for i in range(n):
		if s[i]==s[i+1]:
			cnt+=1
		else:
			A.append(cnt)
			cnt=1
	#print(A)
	
	l=0
	r=0
	now=0
	for i in range(len(A)):
		if i%2:
			r=2*min(A[i],now)
			l+=max(A[i]-now,0)
			now=max(A[i]-l,0)
		else:
			now+=A[i]
	#print(l,n-l-r)
	
	ans="("*l+s[:-1]+")"*(n-l-r)
	print(ans)
	
	
	
	
	
	

if __name__=="__main__":
	main()

Submission status: Wrong Answer

Solution code:
N = int(input())
S = input()

left = ''
right = ''

skip_idx = []
for idx, s in enumerate(S):
    if idx in skip_idx:
        continue
    if s == ')':
        left += '('
    else:
        # print(j)
        skip_flag = 0
        for n in range(idx, N):
            if S[n] == ')':
                skip_idx.append(n)
                skip_flag = 1
                break
        if not skip_flag:
            right += ')'
    # print(idx, s, left, right)

print(left+S+right)

Submission status: Wrong Answer

Solution code:
N = int(input())
S = input()

left = ''
right = ''

j = 0
skip_idx = []
for idx, s in enumerate(S):
    if idx in skip_idx:
        continue
    if s == ')':
        left += '('
    else:
        # print(j)
        for n in range(max(idx, j), N):
            if S[n] == ')':
                skip_idx.append(n)
                break
        j = n
        if j == N-1:
            right += ')'
    # print(idx, s, left, right)

print(left+S+right)

Submission status: Wrong Answer

Solution code:
n = int(input())
S = input()

for _ in range(51):
    S_ = S.replace('()', '')
nr = S_.count('(')
nl = S_.count(')')
print('('*nl+S+')'*nr)

Submission status: Wrong Answer

Solution code:
n = int(input())
S = input()
for _ in range(50):
    S_ = S.replace('()', '')
nr = S_.count('(')
nl = S_.count(')')
print('('*nl+S+')'*nr)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right
from itertools import accumulate

def main():
    N = int(input())
    T = input()
    if N == 1:
      print('()')
      exit()
    S = []
    for s in T:
        if s == '(':
            S.append(1)
        else:
            S.append(-1)
    S = list(accumulate(S))
    print(S)
    minS = min(S)
    for i in range(N):
        S[i] -= minS
    print('('*(-minS) + T + ')'*S[-1])
    

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right
from itertools import accumulate

def main():
    N = int(input())
    T = input()
    S = []
    for s in T:
        if s == '(':
            S.append(1)
        else:
            S.append(-1)
    S = list(accumulate(S))
    # print(S)
    minS = min(S)
    for i in range(N):
        S[i] -= minS
    print('('*(-minS) + T + ')'*S[-1])
    

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque
n = int(input())
s = input()
A = deque([])
for i in range(n):
  if s[i]=='(':
    A.append(s[i])
  elif s[i]==')':
    if len(A)!=0 and A[-1]=='(':
      A.append(s[i])
    elif len(A)==0 or A[-1]==')':
      A.appendleft("(")
      A.append(")")
cou = -1
for i in range(len(A)):
  if A[i]==')':
    cou = i
amari = len(A)-(cou+1)
#print(amari)
for j in range(amari):
  A.append(")")
print("".join(A))

Submission status: Wrong Answer

Solution code:
from collections import deque
n = int(input())
s = input()
A = deque([])
for i in range(n):
  if s[i]=='(':
    A.append(s[i])
  elif s[i]==')':
    if len(A)!=0 and A[-1]=='(':
      A.append(s[i])
    elif len(A)==0 or A[-1]==')':
      A.appendleft("(")
      A.append(")")
cou = 0
for i in range(len(A)):
  if A[i]==')':
    cou = i
amari = len(A)-(cou+1)
#print(amari)
for j in range(amari):
  A.append(")")
print("".join(A))

Submission status: Wrong Answer

Solution code:
N = 6
S = ')))())'


N = 8
S = '))))(((('

N = 3
S = '())'


N = int(input())
S = input()

def calculate(n, s):
    left = []
    right = []

    if n == 1:
        return '()'

    for i in range(0,n):

        if i > 0:
            if (s[i - 1] == '(') and (s[i] == ')'):
                    continue

        if i < (n - 1):
            if (s[i] == '(') and (s[i+1] == ')'):
                    continue


        if s[i] == ')':
            left.append('(')

        if s[i] == '(':
            right.append(')')


    left.reverse()

    return "".join(left) + s + "".join(right)

result = calculate(N, S)

print(result)

Submission status: Wrong Answer

Solution code:
N = int(input())

S = input()
jdg = 0
cntL = 0
cntR = 0
cnt = 0
ans = ""

for i in range(N):
    if jdg %2 == 0:
        if S[i] == "(":
            cntL += 1
        else:
            cntR += 1
            jdg += 1
    else:
        if S[i] == ")":
            cntR += 1
        else:
            if cntL >= cntR:
                ans += "(" * cntL
                ans += ")" * cntR
                cnt += cntL-cntR
            else:
                ans += "(" * cntL
                ans += ")" * cntR
                ans = "(" * (cntR-cntL) + ans
            cntR = 0
            cntL = 1
            jdg += 1
            
if cntL >= cntR:
    ans += "(" * cntL
    ans += ")" * cntR
    cnt += cntL - cntR
else:
    ans += "(" * cntL
    ans += ")" * cntR
    ans = "(" * (cntR-cntL) + ans
ans += ")" * cnt
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())

S = input()
jdg = 0
cntL = 0
cntR = 0
cnt = 0
ans = ""

for i in range(N):
    if jdg %2 == 0:
        if S[i] == "(":
            cntL += 1
        else:
            cntR += 1
            jdg += 1
    else:
        if S[i] == ")":
            cntR += 1
        else:
            if cntL >= cntR:
                ans += "(" * cntL
                ans += ")" * cntR
                cnt += cntL-cntR
            else:
                ans += "(" * cntL
                ans += ")" * cntR
                ans = "(" * (cntR-cntL) + ans
            cntR = 0
            cntL = 1
            jdg += 1
            
if cntL >= cntR:
    ans += "(" * cntL
    ans += ")" * cntL
else:
    if cntL >= cntR:
        ans += "(" * cntL
        ans += ")" * cntR
        cnt += cntL - cntR
    else:
        ans += "(" * cntL
        ans += ")" * cntR
        ans = "(" * (cntR-cntL) + ans
ans += ")" * cnt
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())

S = input()
jdg = 0
cntL = 0
cntR = 0

ans = ""

for i in range(N):
    if jdg %2 == 0:
        if S[i] == "(":
            cntL += 1
        else:
            cntR += 1
            jdg += 1
    else:
        if S[i] == ")":
            cntR += 1
        else:
            if cntL >= cntR:
                ans += "(" * cntL
                ans += ")" * cntL
            else:
                ans += "(" * cntL
                ans += ")" * cntR
                ans = "(" * (cntR-cntL) + ans
            cntR = 0
            cntL = 1
            jdg += 1
            
if cntL >= cntR:
    ans += "(" * cntL
    ans += ")" * cntL
else:
    if cntL >= cntR:
        ans += "(" * cntL
        ans += ")" * cntL
    else:
        ans += "(" * cntL
        ans += ")" * cntR
        ans = "(" * (cntR-cntL) + ans
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())

S = input()
jdg = 0
ans = []
cntL = 0
cntR = 0

for i in range(N):
    if jdg %2 == 0:
        if S[i] == "(":
            cntL += 1
        else:
            cntR += 1
            jdg += 1
    else:
        if S[i] == ")":
            cntR += 1
        else:
            ans.append(max(cntR,cntL))
            cntR = 0
            cntL = 1
            jdg += 1
ans.append(max(cntR,cntL))

A = ""
for a in ans:
    A += "(" * a
    A += ")" * a
print(A)

Submission status: Wrong Answer

Solution code:
N = int(input())
S = input()
diff = [0] * (N + 1)
for i in range(N):
    if S[i] == "(":
        diff[i + 1] = diff[i] + 1
    else:
        diff[i + 1] = diff[i] - 1
min_diff = min(diff)
print("(" * min_diff + S + ")" * (diff[N] - min_diff))

Submission status: Wrong Answer

Solution code:
N = int(input())
S = input()
sep_h = 0
for i in range(N):
    if S[i] == "(":
        sep_h = i
        break
sep_f = N
for i in range(N - 1, -1, -1):
    if S[i] == ")":
        sep_f = i + 1
        break

open_cnt = 0
close_cnt = 0
for i in range(sep_h, sep_f):
    if S[i] == "(":
        open_cnt += 1
    else:
        close_cnt += 1
ans = "(" * (close_cnt - open_cnt)
ans += "(" * sep_h
ans += S
ans += ")" * (N - sep_f)
ans += ")" * (open_cnt - close_cnt)
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
S = input()
sep_h = 0
for i in range(N):
    if S[i] == "(":
        sep_h = i
        break
sep_f = N
for i in range(N - 1, -1, -1):
    if S[i] == ")":
        sep_f = i + 1
        break

open_cnt = 0
close_cnt = 0
for i in range(sep_h, sep_f):
    if S[i] == "(":
        open_cnt += 1
    else:
        close_cnt += 1
ans = "(" * (close_cnt - open_cnt)
ans += "(" * sep_h + S[:sep_h]
ans += S[sep_h:sep_f]
ans += S[sep_f:] + ")" * (N - sep_f)
ans += ")" * (open_cnt - close_cnt)
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
S = input()
sep_h = 0
for i in range(N):
    if S[i] == "(":
        sep_h = i + 1
        break
sep_f = N
for i in range(N - 1, -1, -1):
    if S[i] == ")":
        sep_f = i + 1
        break

open_cnt = 0
close_cnt = 0
for i in range(sep_h, sep_f):
    if S[i] == "(":
        open_cnt += 1
    else:
        close_cnt += 1
ans = "(" * sep_h + ")" * sep_h
ans += "(" * (close_cnt - open_cnt)
ans += S[sep_h:sep_f]
ans += ")" * (open_cnt - close_cnt)
ans += "(" * (N - sep_f) + ")" * (N - sep_f)
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
S = input()
leading_seg = N
trailing_open = N
for i in range(N - 1, -1, -1):
    if S[i] == ")":
        leading_seg = i + 1
        trailing_open = i + 1
        break
open_cnt = 0
close_cnt = 0
for i in range(leading_seg):
    if S[i] == "(":
        open_cnt += 1
    else:
        close_cnt += 1
ans = S[trailing_open:] + ")" * (N - trailing_open)
if open_cnt == close_cnt:
    print(S[:leading_seg] + ans)
elif open_cnt > close_cnt:
    print(S[:leading_seg] + ")" * (open_cnt - close_cnt) + ans)
else:
    print("(" * (close_cnt - open_cnt) + S[:leading_seg] + ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
s = input()
l_cnt = 0
r_cnt = 0
for i in s:
    if i == '(':
        l_cnt += 1
    else:
        r_cnt += 1

if l_cnt == r_cnt:
    print(s)
    
if l_cnt < r_cnt:
    print('('*(r_cnt - l_cnt) +s)
    
if l_cnt > r_cnt:
    print(s +')'*(l_cnt - r_cnt))

Submission status: Wrong Answer

Solution code:
def main():
    from collections import deque
    n = int(input())
    s = input()
    t = s.count("()")
    c_l = 0
    c_r = 0

    for i in s:
        if i == ")":
            c_l += 1
        else:
            c_r += 1

    c_l -= t
    c_r -= t
    print(c_l * "(" + s + ")" * c_r)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    from collections import deque
    n = int(input())
    s = input() + "?"

    lb = 0
    rb = 0
    timer = 0
    for i, j in zip(s, s[1:]):
        if timer < 0:
            timer += 1
            continue
        if [i, j] == ["(", ")"]:
            timer = -1
            continue
        if i == ')':
            lb += 1
        else:
            rb += 1

    print("(" * lb + s[:-1] + ")" * rb)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
s = input()

r_cnt, l_cnt = 0, 0
for i in range(n):
    if i != n - 1 and s[i] == "(" and s[i + 1] != ")":
        r_cnt += 1
    elif i != 0 and s[i] == ")" and s[i - 1] != "(":
        l_cnt += 1

if s[0] == ")":
    l_cnt += 1
if s[-1] == "(":
    r_cnt += 1

print(l_cnt * "(" + s + r_cnt * ")")

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    S = input()
    a, b = 0, 0
    m = float('inf')
    for s in S:
        if s == '(':
            a += 1
        else:
            b += 1
        m = min(m, a - b)
    print(''.join(['(' * (-m), S, ')' * (a - b - m)]))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
S = input()
l = 0
r = 0
for i in range(N):
  if S[i] == ')':
    if r > 0:
      r+=1
    else:
      l+=1
  else:
    r+=1
for _ in range(l):
  print('(', end='')
print(S, end='')
for _ in range(r):
  print(')', end='')

Submission status: Wrong Answer

Solution code:
n = int(input())
s = input()
x = s.count("(")
y = s.count(")")

if x > y:   
    s += ")"*abs(x-y)
else:
    s = "("*abs(x-y) + s
print(s)

Submission status: Wrong Answer

Solution code:
n = int(input())
S = input()
"""
)))((()())
-3  -1  
左に何個、右に何個
"""
l = 0
r = 0
prev = ")"
tmp = 0
for s in S:
    if prev == ")" and s == ")":
        l += 1
    elif prev == ")" and s == "(":
        r += 1
    elif prev == "(" and s == ")":
        r -= 1
    else:
        r += 1
    prev = s
ans = "("*l + S + ")"*r
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

N = int(input())
S = input()
q = deque()

now_a = 0
i = 0
while i < N:
# for i, s in enumerate(S):
    if S[i] == ")":
        q.appendleft("(")
        q.append(")")
        i += 1
    else:
        now_a += 1
        if i == N - 1 or S[i + 1] == ")":  # aの出現の最後だったら
            for j in range(now_a):
                q.append("(")
            for j in range(now_a):
                q.append(")")
            i += now_a + 1
            now_a = 0
        else:
            i += 1

    # print(i, *q)
print(*q, sep="")

Submission status: Wrong Answer

Solution code:
N=int(input())
n=input()
l=0;r=0
for i in n:
    if i=="(":
        r+=1
    else:
        if r:
            r-=1
        else:
            l+=1
print("("*r+n+")"*l)

Submission status: Wrong Answer

Solution code:
n=int(input())
s=list(input())

i=0
cnt=0
while(i<n):
    if s[n-1-i]=='(':
        cnt+=1
        i+=1
        continue
    else:
        for j in range(cnt):
            s.append(')')
        break

a=s.count('(')
b=s.count(')')
if a<b and s[-1]==')':
    c=b-a
    for i in range(c):
        s.insert(0,'(')

    
print(''.join(s))

Submission status: Wrong Answer

Solution code:
from sys import stdin, setrecursionlimit


def main():
    input = stdin.buffer.readline
    n = int(input())
    s = list(input()[:-1].decode())
    ans = []
    c1 = 0
    c2 = 0
    for i in range(n):
        if s[i] == '(':
            c1 += 1
        elif s[i] == ')':
            c2 += 1

        if c1 == 0 and c2 == 1:
            ans = ['('] + ans + [')']
            c1 = c2 = 0
        elif c1 >= 1 and c2 == 1:
            ans = ans + ['('] + [')']
            c1 -= 1
            c2 = 0
    ans = ans + ['('] * (c1 - c2) + [')'] * (c1 - c2)

    print(*ans, sep='')


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Wrong Answer

Solution code:
from sys import stdin, setrecursionlimit


def main():
    input = stdin.buffer.readline
    n = int(input())
    s = list(input()[:-1].decode())
    ans = []
    c1 = 0
    c2 = 0
    idx = 0
    for i in range(n):
        if s[i] == '(':
            c1 += 1
        elif s[i] == ')':
            c2 += 1

        if c1 < c2:
            ans = ans[:i - 1] + ['('] + ans[i - 1:] + [')']
            c1 = 0
            c2 = 0
            idx = i
        elif c1 == c2:
            ans.extend(s[idx:i + 1])
            c1 = 0
            c2 = 0
            idx = i

    if c1 > c2:
        ans.extend('(' * (c1 - c2))
        ans.extend(')' * (c1 - c2))

    print(*ans, sep='')


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Wrong Answer

Solution code:
_,s=open(0);t=s
p,q=o="()"
while o in s:s=s.replace(o,"")
f=s.count
print(p*f(q)+t+q*f(p))

Submission status: Wrong Answer

Solution code:
input()
t=s=input()
p,q="()"
while"()"in s:s=s.replace(p+q,"")
print(p*s.count(q)+t+q*s.count(q))

Submission status: Wrong Answer

Solution code:
n = int(input())
s = input()
d = []
cnt = 0
for i in range(n):
    if s[i] == "(":
        cnt += 1
    else:
        cnt -= 1
    d.append(cnt)
x = min(d)
print("("*(-x)+s+")"*(d[-1]-x))

Submission status: Wrong Answer

Solution code:
#dpでできないかな？
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n=I()
s=SI()
i=0
state=1
count=0
l=[];r=[]
for i in range(n):
    if state==1:
        if s[i]=="(":
            count+=1
        elif s[i]==")":
            l.append(count)
            state=-1
            count=1
    elif state==-1:
        if s[i]==")":
            count+=1
        elif s[i]=="(":
            r.append(count)
            state=1
            count=1
if s[-1]==")":
    r.append(count)
else:
    l.append(count)
    r.append(0)
#print(l)
#print(r)
minus,plus=0,0
for i in range(len(l)):
    if l[i]-r[i]<0:
        minus+=r[i]-l[i]
    else:
        plus+=l[i]-r[i]
#print(minus)
#print(plus)
for i in range(minus):
    print("(",end="")
print(s,end="")
for j in range(plus):
    print(")",end="")

Submission status: Wrong Answer

Solution code:
#dpでできないかな？
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n=I()
s=SI()
i=0
state=1
count=0
l=[];r=[]
for i in range(n):
    if state==1:
        if s[i]=="(":
            count+=1
        elif s[i]==")":
            l.append(count)
            state=-1
            count=1
    elif state==-1:
        if s[i]==")":
            count+=1
        elif s[i]=="(":
            r.append(count)
            state=1
            count=1
if s[-1]==")":
    r.append(count)
else:
    l.append(count)
    r.append(0)
'''print(l)
print(r)'''
minus,plus=0,0
for i in range(len(l)):
    if l[i]-r[i]<0:
        minus+=r[i]-l[i]
    else:
        plus+=l[i]-r[i]
for i in range(minus):
    print("(",end="")
print(s,end="")
for j in range(plus):
    print(")",end="")

Submission status: Wrong Answer

Solution code:
#dpでできないかな？
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n=I()
s=SI()
i=0
state=1
count=0
l=[];r=[]
for i in range(n):
    if state==1:
        if s[i]=="(":
            count+=1
        elif s[i]==")":
            l.append(count)
            state=-1
            count=1
    elif state==-1:
        if s[i]==")":
            count+=1
        elif s[i]=="(":
            r.append(count)
            state=1
            count=1
if s[-1]==")":
    r.append(count)
else:
    l.append(count)
    r.append(0)
'''print(l)
print(r)'''
minus,plus=0,0
for i in range(len(l)):
    if l[i]-r[i]<0:
        minus+=r[i]-l[i]
    else:
        plus+=l[i]-r[i]
for i in range(minus):
    print("(",end="")
print(s,end="")
for j in range(plus):
    print(")",end="")

Submission status: Wrong Answer

Solution code:
N=int(input())
S=input()

x=0
y=0

for i in S:
    if i=="(":
        x+=1
    else:
        if x<=0:
            y+=1
        else:
            x-=1
print("("*x+S+")"*x)

Submission status: Wrong Answer

Solution code:
N=int(input())
S=input()

x=0
y=0

for i in S:
    if i=="(":
        x+=1
    else:
        if x<=0:
            y+=1
        else:
            x-=1

Submission status: Wrong Answer

Solution code:
N = int(input())
S = list(input())
c = 0
for i in S:
    if i == "(":
        c += 1
    else:
        c -= 1
if c == 0:
    ans = "".join(S)
    print(ans)
elif c > 0:
    S = S + [")"]*c
    ans = "".join(S)
    print(ans)
else:
    S = ["("]*(-c) + S
    ans = "".join(S)
    print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import groupby
N = int(input())
S = input()

b = S.count('(')
e = S.count(')')
for s in S:
    if s == ')':
        S = '(' + S
        e -= 1
    else:
        break
for s in reversed(S):
    if s == '(':
        S += ')'
        b -= 1
    else:
        break
if b > e:
    S += ')' * (b-e)
if b < e:
    S = '(' * (e-b) + S
print(S)

Submission status: Wrong Answer

Solution code:
N=int(input())
l=input()
l=l.replace("()","X")
ans=l
for i in range(len(l)):
   if l[i]=="X":
      continue
   elif l[i] == "(":
      ans=ans+")"
   elif l[i] == ")":
      ans="("+ans
ans=ans.replace("X","()")
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
s = input().replace("()", "X").replace("(", "(S").split("S")

ans = ""
for q in s:
    ans += q.count(")") * "(" + q
ans += ")" * len(ans[ans.rfind(")") + 1:])
print(ans.replace("X", "()"))

Submission status: Wrong Answer

Solution code:
N=int(input())
S=input()

left=0
right=0
cnt1=0
cnt2=0

for i in range(N):
    if S[i]=="(":
        cnt1+=1
    elif S[i]==")":
        cnt2+=1
        if i<N-2 and S[i+1]=="(":
            left+=max(0,cnt2-cnt1)
            right+=max(0,cnt1-cnt2)
            cnt1=0
            cnt2=0

left+=max(0,cnt2-cnt1)
right+=max(0,cnt1-cnt2)

print("("*left+S+")"*right)

Submission status: Wrong Answer

Solution code:
N = int(input())
S = input()

L = []

if (S[0] == ")"):
    L.append(0)
cnt = 1
for i in range(N-1):
    if S[i] != S[i+1]:
        L.append(cnt)
        cnt = 1
    else:
        cnt += 1

L.append(cnt)

if(S[-1] == "("):
    L.append(0)

if L[0] < L[1]:
    L[0] = L[1]

if L[-1] < L[-2]:
    L[-1] = L[-2]

L_cnt = 0
R_cnt = 0

for i in range(len(L)):
    if i % 2 == 0:
        L_cnt += L[i]
    else:
        R_cnt += L[i]

if L_cnt > R_cnt:
    d = L_cnt - R_cnt
    L[-1] += d
else:
    d = R_cnt - L_cnt
    L[0] += d

ans = ""

for i in range(len(L)):
    if i % 2 == 0:
        ans += "(" * L[i]
    else:
        ans += ")" * L[i]

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
S = input()

L = []

if (S[0] == ")"):
    L.append(0)
cnt = 1
for i in range(N-1):
    if S[i] != S[i+1]:
        L.append(cnt)
        cnt = 1
    else:
        cnt += 1

L.append(cnt)

if(S[-1] == "("):
    L.append(0)

if L[0] < L[1]:
    L[0] = L[1]

if L[-1] < L[-2]:
    L[-1] = L[-2]



L_cnt = 0
R_cnt = 0

for i in range(len(L)):
    if i % 2 == 0:
        L_cnt += L[i]
    else:
        R_cnt += L[i]

if L_cnt > R_cnt:
    d = L_cnt - R_cnt
    L[-1] += d
else:
    d = R_cnt - L_cnt
    L[0] += d

ans = ""

for i in range(len(L)):
    if i % 2 == 0:
        ans += "(" * L[i]
    else:
        ans += ")" * L[i]

print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
S=input()
stack= []
ans=""
L=0
R=0

for i in range(N):
  if S[i]=="(":
    stack.append(S[i])
  else:
    if len(stack)>0:
      stack.pop()
    else:
      R += 1

L=len(stack)
ans = L * "(" + ans + R * ")"

print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
S=input()
stack= []
ans=""

for i in range(N):
  if S[i]=="(":
    stack.append(S[i])
  else:
    if len(stack)>0:
      ans = ans + stack.pop()+  ")"
    else:
      ans = "(" + ans + ")"

nokori=len(stack)
ans = nokori * "(" + ans + nokori * ")"

print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
S=input()
stack= []
ans=""

for i in range(N):
  if S[i]=="(":
    stack.append(S[i])
  else:
    if len(stack)>0:
      ans = stack.pop()+ ans + ")"
    else:
      ans = "(" + ans + ")"

nokori=len(stack)
ans = nokori * "(" + ans + nokori * ")"

print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
S=input()
stack= []
ans=""

for i in range(N):
  if S[i]=="(":
    stack.append(S[i])
  else:
    if len(stack)>0:
      ans = stack.pop()+ ans + ")"
    else:
      ans = "(" + ans + ")"

nokori=len(stack)
ans += nokori * "(" + nokori * ")"

print(ans)