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:
import itertools
N = int(input())
motoS = input()
S = list(motoS)
gr = itertools.groupby(S)
ls = []
for key,group in gr:
    ls.append(len(list(group)))
if S[0] == ')':
    ls.insert(0,0)
if S[-1] == '(':
    ls.append(0)
start = 0
end = 0
for i in range(len(ls)//2):
    if ls[2*i+1] - ls[2*i] >= 0:
        start += ls[2*i+1] - ls[2*i]
    if ls[2*i+1] - ls[2*i] <= 0:
        end += ls[2*i] - ls[2*i+1]
print('('*start+motoS+')'*end)

Submission status: Wrong Answer

Solution code:
n=int(input())
s=input()
a=s.count("(")
b=n-a 
if a==b:
    print(s);exit()
if a-b>0:
    print(s+")"*(a-b));exit()
print("("*(b-a)+ s)

Submission status: Wrong Answer

Solution code:
n = int(input())
s = input()
ss = s.replace('()', '')
left, right = ss.count('('), ss.count(')')
print('(' * right + s + ')' * left)

Submission status: Wrong Answer

Solution code:
n = int(input())
s = input()
S = s.replace("()", "")
print(S.count(")")*"(" + s + S.count("(")*")")

Submission status: Wrong Answer

Solution code:
n = int(input())
a = input()
cr = 0
cl = 0
ans = a
for i in range(n):
  if a[i] == "(":
    cl += 1
  elif a[i] == ")":
    cr += 1
  if cl == 0 and cr != 0:
    ans = "(" + ans
    cr -= 1
  if cl != 0 and cr != 0:
    if cr >= cl:
      cr -= cl
      cl -= cl
    else:
      cr -= cr
      cl -= cr
if cl != 0:
  for i in range(cl):
    ans = ans+")"
print(ans)

Submission status: Wrong Answer

Solution code:
n = input()
cnt = 0
S = input()
for s in S:
    if s == "(":
        cnt += 1
    else:
        cnt -= 1

if cnt > 0:
    print(S + ")" * cnt)
elif cnt < 0:
    print("(" * (-cnt) + S)
else:
    print(S)

Submission status: Wrong Answer

Solution code:
N = int(input())
S_ = input()
s=S_

count = 0
new_left = 0
new_right = 0

for si in s:
    if si == '(':
        count += 1
    else:
        count -= 1

        if count == -1:
            count = 0
            new_left += 1

new_right = count
print(new_left,new_right)
print('(' * new_left + s + ')' * new_right)

Submission status: Wrong Answer

Solution code:
N = int(input())
S_=input()
S = list(S_)
 
right = 0
left = 0
 
divid = [0]
for s_1 in range(len(S)-1):
    s_2 = s_1+1
    if S[s_1] == ')' and S[s_2] == '(':
        divid.append(s_2)
divid.append(len(S))
 
for s1,s2 in zip(divid[:-1],divid[1:]):
    S_temp = S[s1:s2]
    right_temp = 0
    left_temp = 0
    for s in S_temp:
        if s == '(':
            left_temp += 1
        if s == ')':
            right_temp += 1    
    
    right += max(0,right_temp - left_temp)
    left += max(0,left_temp - right_temp)
    
#     print(s1,s2,S_temp)
#     print(right,left)
print('('*right+S_+')'*left)

Submission status: Wrong Answer

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

chk = []
def calc(lc,rc,S,num,chk):
    while(1):
        if num == len(S)-1:
            if S[num]==")":
                rc += 1
                chk.append([lc,rc])
            else:
                chk.append([lc,rc])
                chk.append([1,0])
            return int(num)
        if S[num]=="(":
            chk.append([lc,rc])
            return int(num-1)
        num += 1
        rc += 1


lf=0
rf=0

lc=0
rc = 0

f=0
cnt = 0
for i in range(N):
    if cnt>=N:
        break
    if S[cnt]==")":
        cnt = calc(lc,0,S,cnt,chk)
        #print(cnt)
        lc = 0
    else:
        lc += 1
    cnt += 1

if lc>0:
    chk.append([lc,0])
#print(chk)
ans_l = 0
ans_r = 0
for i in range(len(chk)):
    l = chk[i][0]
    r = chk[i][1]
    if l>r:
        ans_r += l-r
    else:
        ans_l += r-l

for i in range(ans_l):
    S = "(" + S
for i in range(ans_r):
    S = S + ")"

print(S)

Submission status: Wrong Answer

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

chk = []
def calc(lc,rc,S,num,chk):
    while(1):
        if num == len(S)-1:
            if S[num]==")":
                rc += 1
            chk.append([lc,rc])
            return int(num)
        if S[num]=="(":
            chk.append([lc,rc])
            return int(num-1)
        num += 1
        rc += 1


lf=0
rf=0

lc=0
rc = 0

f=0
cnt = 0
for i in range(N):
    if cnt>=N:
        break
    if S[cnt]==")":
        cnt = calc(lc,0,S,cnt,chk)
        #print(cnt)
        lc = 0
    else:
        lc += 1
    cnt += 1

if lc>0:
    chk.append([lc,0])
#print(chk)
ans_l = 0
ans_r = 0
for i in range(len(chk)):
    l = chk[i][0]
    r = chk[i][1]
    if l>r:
        ans_r += l-r
    else:
        ans_l += r-l

for i in range(ans_l):
    S = "(" + S
for i in range(ans_r):
    S = S + ")"

print(S)

Submission status: Wrong Answer

Solution code:
def main():
    #input data
    import sys
    input = lambda:sys.stdin.readline().strip()
    N = int(input())
    S = input()
    
    #solve
    right=0
    left=0

    for i in range(N):
        if S[i]=='(':
            right+=1
        else:
            left+=1
    ans=S
    if left<right:
        ans=S+(right-left)*')'
    if left>right:
        ans='('*(left-right)+S
    if left==right:
        ans='('*(right)+S+')'*(left)
    print(ans)

if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    #input data
    import sys
    input = lambda:sys.stdin.readline().strip()
    N = int(input())
    S = input()
    
    #solve
    from itertools import groupby
    def runLengthEncode(S: str)->list:
        '''
        str to list(tuple).required itertools.groupby
        '''
        grouped = groupby(S)
        res = []
        for k, v in grouped:
            res.append((k, len(list(v))))
        return res
    
    runs = runLengthEncode(S)

    from collections import deque
    left=deque()
    right=deque()

    idx = len(runs)-1
    #)()()(
    while idx>=0:
        if idx==len(runs)-1 and runs[idx][0]=='(':
            right.append('('*runs[idx][1]+')'*runs[idx][1])
            idx-=1
        elif idx==0 and runs[idx][0]==')':
            left.append('('*runs[idx][1]+')'*runs[idx][1])
            break
        elif idx==0:
            break
        else:
            tmp = runs[idx][1]-runs[idx-1][1]
            if tmp>0:
                left.append('('*tmp)
                right.appendleft('('*runs[idx-1][1]+')'*runs[idx][1])
            else:
                right.appendleft('('*runs[idx-1][1]+')'*runs[idx-1][1])
            idx-=2
    # print(left,right)
    print(''.join(left+right))
    
if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    #input data
    import sys
    input = lambda:sys.stdin.readline().strip()
    N = int(input())
    S = input()
    
    #solve
    from itertools import groupby
    def runLengthEncode(S: str)->list:
        '''
        str to list(tuple).required itertools.groupby
        '''
        grouped = groupby(S)
        res = []
        for k, v in grouped:
            res.append((k, len(list(v))))
        return res
    
    runs = runLengthEncode(S)

    from collections import deque
    left=deque()
    right=deque()

    idx = len(runs)-1
    #)()()(
    while idx>=0:
        if idx==len(runs)-1 and runs[idx][0]=='(':
            right.append('('*runs[idx][1]+')'*runs[idx][1])
            idx-=1
        elif idx==0 and runs[idx][0]==')':
            left.append('('*runs[idx][1]+')'*runs[idx][1])
            break
        elif idx==0:
            break
        else:
            tmp = runs[idx][1]-runs[idx-1][1]
            if tmp>0:
                left.appendleft('('*tmp)
                right.appendleft('('*runs[idx-1][1]+')'*runs[idx][1])
            else:
                right.appendleft('('*runs[idx-1][1]+')'*runs[idx-1][1])
            idx-=2
    # print(left,right)
    print(''.join(left+right))
    
if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    #input data
    import sys
    input = lambda:sys.stdin.readline().strip()
    N = int(input())
    S = input()
    
    #solve
    from itertools import groupby
    def runLengthEncode(S: str)->list:
        '''
        str to list(tuple).required itertools.groupby
        '''
        grouped = groupby(S)
        res = []
        for k, v in grouped:
            res.append((k, len(list(v))))
        return res
    
    runs = runLengthEncode(S)

    from collections import deque
    left=deque()
    right=deque()

    idx = len(runs)-1
    #)()()(
    while idx>=0:
        if idx==len(runs)-1 and runs[idx][0]=='(':
            right.append('('*runs[idx][1]+')'*runs[idx][1])
            idx-=1
        elif idx==0 and runs[idx][0]==')':
            left.appendleft('('*runs[idx][1]+')'*runs[idx][1])
            break
        elif idx==0:
            break
        else:
            tmp = runs[idx][1]-runs[idx-1][1]
            if tmp>0:
                left.appendleft('('*tmp)
                right.appendleft('('*runs[idx-1][1]+')'*runs[idx][1])
            else:
                right.appendleft('('*runs[idx-1][1]+')'*runs[idx-1][1])
            idx-=2
    # print(left,right)
    print(''.join(left+right))
    
if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    #input data
    import sys
    input = lambda:sys.stdin.readline().strip()
    N = int(input())
    S = input()
    
    #solve
    from itertools import groupby
    def runLengthEncode(S: str)->list:
        '''
        str to list(tuple).required itertools.groupby
        '''
        grouped = groupby(S)
        res = []
        for k, v in grouped:
            res.append((k, len(list(v))))
        return res
    
    runs = runLengthEncode(S)

    from collections import deque
    left=deque()
    right=deque()

    idx = len(runs)-1
    #)()()(
    while idx>=0:
        print(idx)
        if idx==len(runs)-1 and runs[idx][0]=='(':
            right.append('('*runs[idx][1]+')'*runs[idx][1])
            idx-=1
        elif idx==0 and runs[idx][0]==')':
            left.appendleft('('*runs[idx][1]+')'*runs[idx][1])
            break
        elif idx==0:
            break
        else:
            tmp = runs[idx][1]-runs[idx-1][1]
            if tmp>0:
                left.appendleft('('*tmp)
                right.appendleft('('*runs[idx-1][1]+')'*runs[idx][1])
            else:
                right.appendleft('('*runs[idx-1][1]+')'*runs[idx-1][1])
            idx-=2
    # print(left,right)
    print(''.join(left+right))
    
if __name__=='__main__':
    main()

Submission status: Wrong Answer

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

l = 0
while s[l] == ")" and l < len(s)-1:
    l += 1

r = len(s)-1
while s[r] == "(" and r > 0:
    r -= 1

opens = 0
for i in range(l, r+1):
    if s[i] == "(":
        opens += 1
    else:
        opens -= 1

s = "("*l + s + ")"*(len(s)-1 - r)

if opens >= 0:
    s = s + ")" * opens
else:
    s = "("*abs(opens) + s

print(s)

Submission status: Wrong Answer

Solution code:
n = int(input())
s = input()
l, r, c = 0, 0, 0
for a in s:
    print(a, l, r, c)
    if a == '(':
        c += 1
    else:
        if c:
            c -= 1
        else:
            l += 1
r = c
print("("*l + s + ")"*r)

Submission status: Wrong Answer

Solution code:
n = int(input())
s = input()
l, r, c = 0, 0, 0
for a in s:
    if a == '(':
        c += 1
    else:
        if c:
            c -= 1
        else:
            r -= 1
    l = n
print("("*l + s + ")"*r)

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    s = input().replace(')(', ') (').split()
    ans = ''
    for a in s:
        tmp = a
        lc = a.count('(')
        rc = a.count(')')
        if lc < rc:
            ans = '('*(rc - lc) + ans
        elif rc < lc:
            tmp += ')'*(lc - rc)
        ans += tmp
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n=int(input())
s=input()
l=[]
for i in s:
  if i==')':
    if len(l)>0:
      if l[-1]=='(':
        l.pop()
      else:
        l.append(i)
    else:
      l.append(i)
print(len(l)*'(' + s)

Submission status: Wrong Answer

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

ans = ""
index1 = n
index2 = 0


left = 0
right = 0


for i in range(n):
    if s[-i-1] == ")":
        index1 = n - i 
        break
for i in range(n):
    if s[i] == "(":
        index2 = i
        break

#s = "(" * index2 + s

lis = s[index2:index1]
left = lis.count("(") 
right = lis.count(")") 
if right >= left:
    ans +="(" * index2 + "(" * (right-left) + s + ")" * (n-index1)
else:
    ans +="(" * index2 + s + ")" * (left-right) + ")"  * (n-index1)


print(ans)

Submission status: Wrong Answer

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

ans = ""
index = 0


left = 0
right = 0


for i in range(n):
    if s[-i-1] == ")":
        index = n - i 
        break

lis = s[:index]
left = lis.count("(") 
right = lis.count(")") 
if right >= left:
    ans += "(" * (right-left) + s + ")" * (n-index)
else:
    ans += s + ")" * (left-right) + ")"  * (n-index)


print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
S=input()
new_S=S.split(')(')
if len(new_S)==1:
    pass
else:
    for n in range(len(new_S)):
        if n%2==0:
            new_S[n]=new_S[n]+')'
        else:
            new_S[n]='('+new_S[n]
for s in new_S:
    right=s.count(')')
    left=s.count('(')
    if right==left:
        pass
    elif right>left:
        new_S[0]='('*(right-left)+new_S[0]
    else:
        new_S[-1]=new_S[-1]+')'*(left-right)
answer=''
for s in new_S:
    answer+=s
print(answer)

Submission status: Wrong Answer

Solution code:
N=int(input())
S=input()
d = [0]*(N+1) # d[i]: Sの最初のi文字における
              # "(" - ")"
for i in range(1, N+1):
    d[i] = S[:i].count("(") - S[:i].count(")")
x = min(d)
# x = 0 かつ d[N]=0ならよい
if x == 0 and d[N] == 0:
    print(S)
    exit()

ans = "("*max(abs(x), abs(d[N]-x)) + S + ")"*min(abs(x), abs(d[N]-x))
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
S=input()
stack = []
i = 0
cnts = []
while i < N:
    if i == N-1 and S[i] != ")":
        l_cnt = 0
        stack.append(S[i])
        while stack:
            stack.pop()
            l_cnt += 1
        cnts.append(l_cnt)
        break
    if S[i] == "(":
        stack.append(S[i])
        i += 1
    elif S[i] == ")":
        l_cnt = 0
        while stack:
            stack.pop()
            l_cnt += 1
        r_cnt = 1
        while i+1 < N and S[i+1] == ")":
            i += 1
            r_cnt += 1
        cnts.append(max(r_cnt, l_cnt))
        i+=1
ans = ""
for c in cnts:
    ans += "("*c
    ans += ")"*c
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
s = str(input())
mn = [0 for _ in range(n)]
c = 0
x = 0
y = 0
for i in range(n):
  if s[i] == "(":
    c += 1
    x += 1
  else:
    c -= 1
    y += 1
  mn[i] = c
m = -min(mn)
t1 = "("*m
t2 = ")"*(m+x-y)
print(t1+s+t2)

Submission status: Wrong Answer

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

countr, countl = 0, 0
loc = 0
ans = s
now = False
for i in range(n):
    if i == n-1:
        if s[i] == ')':
            countl += 1
        else:
            countr += 1
        num = countl-countr
        if num >= 0:
            if not now:
                ans = ans[:loc]+'('*num+ans[loc:]
            else:
                ans = '('*num+ans
        else:
            ans = ans+')'*abs(num)
            
    elif s[i] == ')' and s[i+1] == '(':
        countl += 1
        ans = ans[:loc]+'('*countl+ans[loc:]
        loc = i+countl
        countl, countr = 0, 0
        now = True
    elif s[i] == ')' and s[i+1] == ')':
        countl += 1
    elif s[i] == '(' and s[i+1] == '(':
        countr += 1
    elif s[i] == '(' and s[i+1] == ')':
        countr += 1
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n = int(input())
s = str(input())
l = 0
r = 0
x = []
w = ""
for i in range(n-1):
    if s[i]+s[i+1] == ')(':
        w += s[i]
        x.append(w)
        w = ""
    else:
        w += s[i]
w += s[n-1]
if len(w) != 0:    
    x.append(w)
for h in x:
    a = h.count('(')
    b = h.count(')')
    if a < b:
        l += (b-a)
    elif b < a:
        r += (a-b)
m = ""
for j in x:
    m += j
print('('*l + m + ')'*r)

Submission status: Wrong Answer

Solution code:
icase=0
if icase==0:
    n=int(input())
    s=input()
elif icase==1:
    n=3
    s="())"
elif icase==2:
    n=6
    s=")))())"
elif icase==3:
    n=8
    s="))))(((("

l=[]
r=[]
sim=s[0]
if sim=="(":
    lidx=0
    l.append(1)
    ridx=-1
elif sim==")":
    lidx=0
    l.append(0)
    ridx=0
    r.append(1)

for i in range(1,len(s)):
    if s[i]=="(" and s[i-1]=="(":
        l[lidx]+=1
    elif s[i]=="(" and s[i-1]==")":
        lidx+=1
        l.append(1)
    elif s[i]==")" and s[i-1]==")":
        r[ridx]+=1
    elif s[i]==")" and s[i-1]=="(":
        ridx+=1
        r.append(1)

ll=sum(l)
rr=sum(r)
ds=ll-rr

if len(l)>len(r):
    r.append(0)
elif len(l)<len(r):
    l.append(0)
xmin=100
x=0
for i in range(len(l)):
    x=x+l[i]-r[i]
    xmin=min(x,xmin)

strs="("*(-xmin) + s + ")"*(ds-xmin)
print(strs)

Submission status: Wrong Answer

Solution code:

icase=3
if icase==0:
    n=int(input())
    s=input()
elif icase==1:
    n=3
    s="())"
elif icase==2:
    n=6
    s=")))())"
elif icase==3:
    n=8
    s="))))(((("

l=[]
r=[]
sim=s[0]
if sim=="(":
    lidx=0
    l.append(1)
    ridx=-1
elif sim==")":
    lidx=0
    l.append(0)
    ridx=0
    r.append(1)

for i in range(1,len(s)):
    if s[i]=="(" and s[i-1]=="(":
        l[lidx]+=1
    elif s[i]=="(" and s[i-1]==")":
        lidx+=1
        l.append(1)
    elif s[i]==")" and s[i-1]==")":
        r[ridx]+=1
    elif s[i]==")" and s[i-1]=="(":
        ridx+=1
        r.append(1)

ll=sum(l)
rr=sum(r)
ds=ll-rr

if len(l)>len(r):
    r.append(0)
elif len(l)<len(r):
    l.append(0)
xmin=100
x=0
for i in range(len(l)):
    x=x+l[i]-r[i]
    xmin=min(x,xmin)

strs="("*(-xmin) + s + ")"*(ds-xmin)
print(strs)

Submission status: Wrong Answer

Solution code:
icase=0
if icase==0:
    n=int(input())
    s=input()
elif icase==1:
    n=3
    s="())"
elif icase==2:
    n=6
    s=")))())"
elif icase==3:
    n=8
    s="))))(((("

l=[]
r=[]
sim=s[0]
if sim=="(":
    lidx=0
    l.append(1)
    ridx=-1
elif sim==")":
    lidx=0
    l.append(0)
    ridx=0
    r.append(1)

for i in range(1,len(s)):
    if s[i]=="(" and s[i-1]=="(":
        l[lidx]+=1
    elif s[i]=="(" and s[i-1]==")":
        lidx+=1
        l.append(1)
    elif s[i]==")" and s[i-1]==")":
        r[ridx]+=1
    elif s[i]==")" and s[i-1]=="(":
        ridx+=1
        r.append(1)

ll=sum(l)
rr=sum(r)
ds=ll-rr

if len(l)>len(r):
    r.append(0)
xmin=10**9
x=0
for i in range(len(l)):
    x=x+l[i]-r[i]
    xmin=min(x,xmin)

strs="("*(-xmin) + s + ")"*(ds-xmin)
print(strs)

Submission status: Wrong Answer

Solution code:

icase=0
if icase==0:
    n=int(input())
    s=input()
elif icase==1:
    n=3
    s="())"
elif icase==2:
    n=6
    s=")))())"
elif icase==3:
    n=8
    s="))))(((("

l=[]
r=[]
sim=s[0]
if sim=="(":
    lidx=0
    l.append(1)
    ridx=-1
elif sim==")":
    lidx=0
    l.append(0)
    ridx=0
    r.append(1)

for i in range(1,len(s)):
    if s[i]=="(" and s[i-1]=="(":
        l[lidx]+=1
    elif s[i]=="(" and s[i-1]==")":
        lidx+=1
        l.append(1)
    elif s[i]==")" and s[i-1]==")":
        r[ridx]+=1
    elif s[i]==")" and s[i-1]=="(":
        ridx+=1
        r.append(1)

ll=sum(l)
rr=sum(r)
ds=ll-rr

if len(l)>len(r):
    r.append(0)
xmin=100
x=0
for i in range(len(l)):
    x=x+l[i]-r[i]
    xmin=min(x,xmin)

strs="("*(-xmin) + s + ")"*(ds-xmin)
print(strs)

Submission status: Wrong Answer

Solution code:
icase=0
if icase==0:
    n=int(input())
    s=input()
elif icase==1:
    n=3
    s="())"
elif icase==2:
    n=6
    s=")))())"
elif icase==3:
    n=8
    s="))))(((("

#l=[0]*n
#r=[0]*n
l=[]
r=[]
sim=s[0]
if sim=="(":
    lidx=0
#    l[lidx]=1
    l.append(1)
    ridx=-1
elif sim==")":
    lidx=0
#    l[lidx]=0
    l.append(0)
    ridx=0
#    r[ridx]=1
    r.append(1)

for i in range(1,len(s)):
    if s[i]=="(" and s[i-1]=="(":
        l[lidx]+=1
    elif s[i]=="(" and s[i-1]==")":
        lidx+=1
#        l[lidx]=1
        l.append(1)
    elif s[i]==")" and s[i-1]==")":
        r[ridx]+=1
    elif s[i]==")" and s[i-1]=="(":
        ridx+=1
#        r[ridx]=1
        r.append(1)
#    print(i,"l:",l,"r",r)

strs=""
nn=min(len(r),len(l))
for i in range(nn):
    lr=min(l[i],r[i])
    l[i]-=lr
    r[i]-=lr

ll=sum(l)
rr=sum(r)
strs+="("*rr+s+")"*ll
print(strs)

Submission status: Wrong Answer

Solution code:

icase=0
if icase==0:
    n=int(input())
    s=input()
elif icase==1:
    n=3
    s="())"
elif icase==2:
    n=6
    s=")))())"
elif icase==3:
    n=8
    s="))))(((("

l=[0]*n
r=[0]*n

sim=s[0]
if sim=="(":
    lidx=0
    l[lidx]=1
    ridx=-1
elif sim==")":
    lidx=0
    l[lidx]=0
    ridx=0
    r[ridx]=1

for i in range(1,len(s)):
    if s[i]=="(" and s[i-1]=="(":
        l[lidx]+=1
    elif s[i]=="(" and s[i-1]==")":
        lidx+=1
        l[lidx]=1
    elif s[i]==")" and s[i-1]==")":
        r[ridx]+=1
    elif s[i]==")" and s[i-1]=="(":
        ridx+=1
        r[ridx]=1
#    print(i,"l:",l,"r",r)

strs=""
for i in range(n):
    if l[i]==0 and r[i]==0:
        break
    lr=max(l[i],r[i])
    strs+="("*lr+")"*lr
print(strs)

Submission status: Wrong Answer

Solution code:
N=int(input())
S=input()
i=0
hidari=str()
migi=str()
a=0
while i<N:
  if S[i]==")":
    hidari+="("
    i+=1
  else:
    break
while i<N:
  if S[i]=="(":
    a+=1
  else:
    a-=1
  i+=1
if a<0:
  hidari+=abs(a)*"("
elif a>0:
  migi+=a*")"
s=hidari+S+migi


i=0
hidari=str()
migi=str()
a=0
while i<N:
  if S[i]==")":
    hidari+="("
    i+=1
  else:
    break
while i<N:
  if S[i]=="(":
    if a<0:
      a=0
    a+=1
    mina=0
  else:
    a-=1
    if a<0:
      if mina>a:
        hidari+="("
  i+=1
if a>0:
  migi+=a*")"
if hidari==migi==str():
  print("("+S+")")
  exit()
t=hidari+S+migi
if s==t:
  print(s)
elif len(s)>len(t):
  print(s)
else:
  print(t)

Submission status: Wrong Answer

Solution code:
N=int(input())
S=input()
i=0
hidari=str()
migi=str()
a=0
while i<N:
  if S[i]==")":
    hidari+="("
    i+=1
  else:
    break
while i<N:
  if S[i]=="(":
    a+=1
  else:
    a-=1
  i+=1
if a<0:
  hidari+=abs(a)*"("
elif a>0:
  migi+=a*")"
s=hidari+S+migi


i=0
hidari=str()
migi=str()
a=0
while i<N:
  if S[i]==")":
    hidari+="("
    i+=1
  else:
    break
while i<N:
  if S[i]=="(":
    if a<0:
      a=0
    a+=1
    mina=0
  else:
    a-=1
    if a<0:
      if mina>a:
        hidari+="("
  i+=1
if a>0:
  migi+=a*")"
if hidari==migi==str():
  print("("+S+")")
  exit()
t=hidari+S+migi
if s==t:
  print(s)
elif len(s)<len(t):
  print(s)
else:
  print(t)

Submission status: Wrong Answer

Solution code:
N=int(input())
S=input()
N=len(S)
i=0
hidari=str()
migi=str()
a=0
while i<N:
  if S[i]==")":
    hidari+="("
    i+=1
  else:
    break
while i<N:
  if S[i]=="(":
    if a<0:
      a=0
    a+=1
    mina=0
  else:
    a-=1
    if a<0:
      if mina>a:
        hidari+="("
  i+=1
if a>0:
  migi+=a*")"
if hidari==migi==str():
  print("("+S+")")
  exit()
print(hidari+S+migi)

Submission status: Wrong Answer

Solution code:
N=int(input())
S=input()
i=0
hidari=str()
migi=str()
a=0
while i<N:
  if S[i]==")":
    hidari+="("
    i+=1
  else:
    break
while i<N:
  if S[i]=="(":
    a+=1
  else:
    a-=1
  i+=1
if a<0:
  hidari+=abs(a)*"("
elif a>0:
  migi+=a*")"
if hidari==migi==str():
  print("("+S+")")
  exit()
print(hidari+S+migi)

Submission status: Wrong Answer

Solution code:
N=int(input())
S=input()
i=0
hidari=str()
migi=str()
a=0
while i<N:
  if S[i]==")":
    hidari+="("
    i+=1
  else:
    break
while i<N:
  if S[i]=="(":
    a+=1
  else:
    a-=1
  i+=1
if a<0:
  hidari+=abs(a)*"("
elif a>0:
  migi+=a*")"
print(hidari+S+migi)

Submission status: Wrong Answer

Solution code:
N = int(input())
S = input()
now = 0
right = 0
left = 0
add_left = 0
while now < N:
    if S[now] == '(':
        left += 1
    else:
        if left:
            left -= 1
        else:
            add_left += 1
    now += 1
for _ in range(add_left):
    print('(', end='')
print(S, end='')
for _ in range(left):
    print(')', end='')
print()
print('(((()))())')

Submission status: Wrong Answer

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

countc = 0
countj = 0
plusc= 0
for i in range(0,N,1):
    if S[i]==")":
        if countj >= countc:
            plusc+=1
        countj+=1
    else:
        countc+=1

countc = 0
countj = 0
plusj = 0
for i in range(N-1,-1,-1):
    if S[i]==")":
        countj+=1
    else:
        if countc >= countj:
            plusj+=1
        countc+=1

c = ["("]*plusc
j = [")"]*plusj
S = c+S+j

print("".join(S))

Submission status: Wrong Answer

Solution code:
n, s = int(raw_input()), raw_input()
h = {'(':+1 , ')':-1}
m = 0
bal = 0
for i in range(len(s)):
	bal += h[s[i]]
	m = min(bal,m)

print '(' *abs(m) + s + ')' * max(0,bal)

Submission status: Wrong Answer

Solution code:
n = int(input())
s = str(input())
tmp = s
ans = ''
#print(s[:-1])
while len(s)>0:
    if s[0]=='(' and s[-1]==')':
        s = s[1:]
        s = s[:-1]
    elif s[0]==')':
        ans += 'i'
        s = s[1:]
    elif s[-1]=='(':
        ans += 'a'
        s = s[:-1]

for i in range(len(ans)):
    if ans[i]=='i':
        tmp = '('+tmp
    else:
        tmp = tmp+')'

print(tmp)

Submission status: Wrong Answer

Solution code:
n = int(input())
s = str(input())
z = "N"
l = []
for i in range(n-1):
    if s[i] == ')' and s[i+1] == '(':
        l.append(i+1)
        l.append(i+1)
        z = "Y"
l.append(n)
l.insert(0,0)
a = 0
if z == "Y":
    for j in range(0,len(l),2):
        w = ""
        w += s[l[j]+a:l[j+1]+a]
        x = w.count("(")
        y = w.count(")")
        if x < y:
            s = "("*(y-x) + s
            a += (y-x)
        elif y < x:
            s = s + ")"*(x-y)
else:
    x = s[0:n].count("(")
    y = s[0:n].count(")")
    if x < y:
        s = "("*(y-x) + s
    elif y < x:
        s = s + ")"*(x-y)
print(s)

Submission status: Wrong Answer

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

if ')' in S:
  for i in range(N):
    if S[N-1-i] == ')':
      n = N-i
      break
  lc = S[:n].count('(')
  rc = S[:n].count(')')
  if rc > lc:
    S = (rc-lc) * '(' + S

s = S.index('(')
l = S[s:].count('(')
r = S[s:].count(')')
if l > r:
  S = S + (l-r) * ')'
  
print(S)

Submission status: Wrong Answer

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

if ')' in S:
  for i in range(N):
    if S[N-1-i] == ')':
      n = N-i
      break
  lc = S[:n].count('(')
  rc = S[:n].count(')')
  if rc > lc:
    S = (rc-lc) * '(' + S

s = S.index('(')
l = 0
r = 0
for i in range(s, len(S)):
  if S[i] == '(':
    l += 1
  else:
    r += 1
if l > r:
  S = S + (l-r) * ')'
  
print(S)

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict
def input(): return sys.stdin.readline().strip()

def main():
    N = int(input())
    S = input()
    height = 0
    deepest = 0
    for c in S:
        if c == '(':
            height += 1
        else:
            height -= 1
        deepest = min(deepest, height)
    print(deepest, height)
    ans = '(' * (-deepest) + S + ')' * (height - deepest)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
s = input()
ind1 = 0
ind2 = N
for i in range(N):
    if s[i] == '(':
        ind1 = i
        break

for i in range(N):
    if s[N-i-1] == ')':
        ind2 = N-i
        break

left = s[:ind1].count(')')
right = s[ind2:].count('(')

mid_left = s[ind1:ind2].count(')')
mid_right = s[ind1:ind2].count('(')

left += max(0,mid_left-mid_right)
right += max(0,mid_right-mid_left)

ans = '('*left + s + ')' * right
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
s = list(input())
d = []
x = 0

for i in range(len(s)):
    if s[i] == '(':
        x += 1
    else:
        x -= 1
    d.append(x)

ans = []
x = min(d)

for i in range(max(0,(-1*x))):
    ans.append('(')

for i in s:
    ans.append(i)

for i in range(max(d[len(d)-1]-x,0)):
    ans.append(')')

a = ''.join(ans)

print(a)

Submission status: Wrong Answer

Solution code:
import copy
N = int(input())
S = list(input())
S_ans = copy.deepcopy(S)
app = 0
q = [0]
save = 0
for i in range(N):
    if S[i] == '(':
        q.append(q[-1] + 1)
        if q[-1] == 1:
            save = i
    else:
        q.append(q[-1] - 1)
        if q[-1] == -1:
            S_ans.insert(app + save,"(")
            app += 1
            q[-1] = 0

for i in range(q[-1]):
    S_ans.append(")")
print("".join(S_ans))

Submission status: Wrong Answer

Solution code:
import copy
N = int(input())
S = list(input())
S_ans = copy.deepcopy(S)
app = 0
q = [0]
save = 0
for i in range(N):
    print(S)
    if S[i] == '(':
        q.append(q[-1] + 1)
        if q[-1] == 1:
            save = i
    else:
        q.append(q[-1] - 1)
        if q[-1] == -1:
            S_ans.insert(app + save,"(")
            app += 1
            q[-1] = 0
print(q)

for i in range(q[-1]):
    S_ans.append(")")
print("".join(S_ans))

Submission status: Wrong Answer

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

flg_l = False
if(S[0] == "("):
    flg_l = True

cnt_r = 0
cnt_l = 0

for i in range(N):
    if(S[i] == "("):
        cnt_r += 1
        flg_l = True            
    else:
        if(flg_l):
            if(cnt_r > 0):
                cnt_r -= 1
                flg_l = False
            else:
                cnt_l += 1
        else:
            cnt_l += 1
ans = ""

ans += ("("*cnt_l)+S+(")"*cnt_r)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし

N = I()
S = LS2()

a,b = 0,0
left = []
for i in range(N):
    if S[i] == '(':
        a += 1
    else:
        b += 1
    if a < b:
        a,b = 0,0
        left.append('(')

ANS = left + S + [')']*(a-b)

print(*ANS)

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.readline


def main():
    N = int(input())
    S = input().rstrip()

    ans = ""
    n_left = 0
    for s in S:
        if s == "(":
            ans = "".join((ans, "("))
            n_left += 1
        else:
            if n_left > 0:
                n_left -= 1
                ans = "".join((ans, ")"))
            else:
                ans = "".join((ans, "()"))
    ans = "".join((ans, ")" * n_left))

    print(ans)


if __name__ == "__main__":
    main()