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=input()
kf=0
kn=kp=0
ans=""
for i in range(n):
  if s[i]=="(":
    if kf==0:
      kn+=1
    else:
      ans="("*max(0,kp-kn)+ans+"("*(max(kn,kp)-max(0,kp-kn))+")"*max(kn,kp)
      kn=1
      kp=0
      kf=0
  else:
    if kf==1:
      kp+=1
    else:
      kp=1
      kf=1
ans="("*max(0,kp-kn)+ans+"("*(max(kn,kp)-max(0,kp-kn))+")"*max(kn,kp)
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations
    #from itertools import accumulate, product
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    #from operator import itemgetter

    #mod = 1000000007


    N = int(input())
    S = input()
    t = S
    while 1:
        a = len(t)
        s = t.split('()')
        s = ''.join(s)
        if len(s)==a:
            break
        t = s
    left = s.count(')')
    right = s.count('(')
    print('('*left + S + ')'*right)

    # N = int(input())
    # S = list(input())
    # res = 0
    # for i in S:
    #     if i == ')':
    #         res += 1
    #     else:
    #         break
    # add = S[res:].count('(')-S[res:].count(')')
    # if add>=0:
    #     for _ in range(add):
    #         S.append(')')
    #     print('('*res+''.join(S))
    # else:
    #     print('('*(res-add)+''.join(S))




if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations
    #from itertools import accumulate, product
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    #from operator import itemgetter

    #mod = 1000000007

    N = int(input())
    S = list(input())
    res = 0
    for i in S:
        if i == ')':
            res += 1
        else:
            break
    add = S[res:].count('(')-S[res:].count(')')
    if add>=0:
        for _ in range(add):
            S.append(')')
        print('('*res+''.join(S))
    else:
        print('('*(res-add)+''.join(S))




if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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

def main():
    mod=10**9+7
    N=I()
    S=input()
    
    st=0
    a=""
    b=""
    for i in range(N):
        s=S[i]
        if st==0 and s==")":
            a+="("
        elif s=="(":
            st+=1
        else:
            st-=1
    b+=")"*st
    print(a+S+b)

main()

Submission status: Wrong Answer

Solution code:
N = int(input())
X = input()
counter = []
prev = "("
count = 0
for i, x in enumerate(X):
  if prev != x:
    prev = x
    counter.append(count)
    count = 0
  if x == "(":
    count += 1
  else:
    count -= 1
counter.append(count)
if len(counter) % 2 == 1:
  counter.append(0)
#print(counter)
result = ""
for i in range(0, len(counter), 2):
  result += "(" * max(list(map(abs,counter[i:i+2])))
  result += ")" * max(list(map(abs,counter[i:i+2])))
print(result)

Submission status: Wrong Answer

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

count1 = 0
count2 = 0
flag = False

for index, s in enumerate(S):
  if s == '(':
    flag = True
    count1 += 1

  if flag and s == ')':
    count2 += 1

  if not flag:
    continue

if count1 > count2:
  S += ')' * (count1 - count2)

count1 = 0
count2 = 0
flag = False

for index, s in enumerate(S[::-1]):
  if s == ')':
    flag = True
    count1 += 1

  if flag and s == '(':
    count2 += 1

  if not flag:
    continue

if count1 > count2:
  S = '(' * (count1 - count2) + S

print(S)

Submission status: Wrong Answer

Solution code:
N = int(input())
S = input()
def compute_counter(S):
    Counter = [0 for i in range(N)]
    for i in range(N):
        if i == 0:
            if S[i] == '(':
                Counter[i] = 1
            else:
                Counter[i] = -1
        else:
            if S[i] == '(':
                Counter[i] = Counter[i-1]+1
            else:
                Counter[i] = Counter[i-1]-1
    return Counter
c = compute_counter(S)
x = min(c)
d = c[-1]
S = '('*(-x) + S + ')'*(d-x) 
print(S)

Submission status: Wrong Answer

Solution code:
from collections import deque
n=int(input())
s=deque(input())

cnt1,cnt2=0,0
for i in range(n):
    if s[i]==')':
        cnt1+=1
    else:
        break
        
for i in range(n-1,-1,-1):
    if s[i]=='(':
        cnt2+=1
    else:
        break
        
s.appendleft('('*cnt1)
s.append(')'*cnt2)

cnt3=s.count(')')+cnt2
cnt4=s.count('(')+cnt1

if cnt3>cnt4:
    s.appendleft('('*(cnt3-cnt4))
else:
    s.append(')'*(cnt4-cnt3))
  
print(''.join(list(s)))

Submission status: Wrong Answer

Solution code:
def main():
    length = int(input())
    string = input()
    answer = string.replace("()", "")
    print("(" * answer.count(")") + string + ")" * answer.count("("))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

def main():
    N = int(input())
    S = str(input())
    left,right = [],[]
    now = "("
    count = 0
    for s in S:
        if now == s:
            count += 1
        else:
            if now == "(":
                left.append(count)
            else:
                right.append(count)
            now = s
            count = 1
        
    if now == "(":
        left.append(count)
    else:
        right.append(count)
    if S[-1] == "(":
        right.append(0)
    r,l = 0,0
    for i,j in zip(right,left):
        if i >= j:
            r += i-j
        else:
            l += j-i
        
    print("("*r+S+")"*l)
  
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

def main():
    N = int(input())
    S = str(input())
    left,right = [],[]
    now = "("
    count = 0
    for s in S:
        if now == s:
            count += 1
        else:
            if now == "(":
                left.append(count)
            else:
                right.append(count)
            now = s
            count = 1
        
    if now == "(":
        left.append(count)
    else:
        right.append(count)
    if S[-1] == "(":
        right.append(0)
    r,l = 0,0
    for i,j in zip(right,left):
        if i >= j:
            r += i-j
        else:
            l = j-i
        
    print("("*r+S+")"*l)
  
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

RLE = []
now_char = S[0]
now_cnt = 1
for i in range(1, N):
    if now_char == S[i]:
        now_cnt += 1
    else:
        RLE.append([now_char, now_cnt])
        now_char = S[i]
        now_cnt = 1
RLE.append([now_char, now_cnt])


n = len(RLE)
ans = ""
left_cnt = 0
right_cnt = 0

for i in range(n):
    now_char = RLE[i][0]
    now_cnt = RLE[i][1]
    if now_char == "(":
        left_cnt += now_cnt
    else:
        right_cnt += now_cnt
        if right_cnt >= left_cnt:
            ans += "(" * (right_cnt - left_cnt)
            right_cnt = 0
            left_cnt = 0
        else:
            right_cnt = 0
            left_cnt -= right_cnt

ans += S
if left_cnt > 0:
    ans += ")" * left_cnt

print(ans)

Submission status: Wrong Answer

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

RLE = []
now_char = S[0]
now_cnt = 1
for i in range(1, N):
    if now_char == S[i]:
        now_cnt += 1
    else:
        RLE.append([now_char, now_cnt])
        now_char = S[i]
        now_cnt = 1
RLE.append([now_char, now_cnt])


n = len(RLE)
ans = ""
left_cnt = 0
right_cnt = 0

for i in range(n):
    now_char = RLE[i][0]
    now_cnt = RLE[i][1]
    if now_char == "(":
        left_cnt += now_cnt
    else:
        right_cnt += now_cnt
        if right_cnt > left_cnt:
            ans += "(" * (right_cnt - left_cnt)
            right_cnt = 0
            left_cnt = 0
        else:
            right_cnt = 0
            left_cnt -= right_cnt

ans += S
if left_cnt > 0:
    ans += ")" * left_cnt

print(ans)

Submission status: Wrong Answer

Solution code:
n, s = int(input()), input()
t = []
if s[0]==")": t.append(0)
prev = s[0]
cnt = 0
for i in s:
    if prev==i: cnt+=1
    else:
        t.append(cnt)
        cnt = 1
    prev = i
t.append(cnt)
if len(t)%2: t.append(0)

tt = t.copy()
for i in range(0, len(tt), 2):
    if tt[i]>tt[i+1]:
        tt[i] -= tt[i+1]
        tt[i+1] = 0
    else:
        tt[i+1] -= tt[i]
        tt[i] = 0

print("("*sum(tt[1::2]) + s + ")"*sum(tt[::2]))

Submission status: Wrong Answer

Solution code:
N = int(input())
S = input()
s = S
l=0
r=0
tmp=0
for i in range(N):
    #始めて(が出てくるインデックス
    if S[i]=="(":
        tmp=i
        r=1
        break
    else:
        l += 1
#tmp=N-1の場合は別でやる必要あり
for i in range(tmp+1,N):
    if S[i]=="(":
        r+=1
    else:
        if r>0:
            r-=1
        else:
            l+=1

if r>0:
    for _ in range(r):
        s = s + ")"

if l>0:
    for _ in range(l):
        s = "(" + s

print(s)

Submission status: Wrong Answer

Solution code:
import numpy  as np
n=int(input())
x=np.array(list(input()))

word=[('(','('),('(',')'),(')',')'),(')','(')]

if x[-1]=='(':
  cnt_1=1
  cnt_2=0

else:
  cnt_1=0
  cnt_2=1

ind=n
for i in range(n-2,-1,-1):
    if (x[i],x[i+1])==word[0]:
      cnt_1+=1
    elif (x[i],x[i+1])==word[1]:
      cnt_1+=1
      ind=i+1
    elif (x[i],x[i+1])==word[2]:
      cnt_2+=1
    else:
      #print(cnt_1,cnt_2)
      if cnt_1>cnt_2:
        x=np.insert(x,ind,[')']*(cnt_1-cnt_2))
      else:
        x=np.insert(x,ind,['(']*(cnt_2-cnt_1))
      cnt_1=0
      cnt_2=1
if x[0]==')':
  ind=0
#print(cnt_1,cnt_2)  
if cnt_1>cnt_2:
   x=np.insert(x,ind,[')']*(cnt_1-cnt_2))
else:
   x=np.insert(x,ind,['(']*(cnt_2-cnt_1))
print(''.join(x))

Submission status: Wrong Answer

Solution code:
import numpy  as np
n=int(input())
x=np.array(list(input()))

word=[('(','('),('(',')'),(')',')'),(')','(')]

if x[-1]=='(':
  cnt_1=1
  cnt_2=0

else:
  cnt_1=0
  cnt_2=1

ind=n
for i in range(n-2,-1,-1):
    if (x[i],x[i+1])==word[0]:
      cnt_1+=1
    elif (x[i],x[i+1])==word[1]:
      cnt_1+=1
      ind=i
    elif (x[i],x[i+1])==word[2]:
      cnt_2+=1
    else:
      #print(cnt_1,cnt_2)
      if cnt_1>cnt_2:
        x=np.insert(x,ind,[')']*(cnt_1-cnt_2))
      else:
        x=np.insert(x,ind,['(']*(cnt_2-cnt_1))
      cnt_1=0
      cnt_2=1
if x[0]==')':
  ind=0
#print(cnt_1,cnt_2)  
if cnt_1>cnt_2:
   x=np.insert(x,ind,[')']*(cnt_1-cnt_2))
else:
   x=np.insert(x,ind,['(']*(cnt_2-cnt_1))
print(''.join(x))

Submission status: Wrong Answer

Solution code:
n = int(input())
s = input()
l = s.rfind(')')

cntl, cntr = 0, 0
flag = 0
for i in range(l + 1):
    if s[i] == '(':
        cntl += 1
    else:
        cntr += 1

if cntl <= cntr:
    s1 = '(' * (max((cntr - cntl), 0))
    print(s1, end='')
else:
    s2 = ')' * (max((cntl - cntr), 0))
    flag = 1

print(s, end='')
r1 = ')' * (max((n - l - 1), 0))
print(r1, end='')

if flag:
    print(s2)

Submission status: Wrong Answer

Solution code:
n = int(input())
s = input()
l = s.rfind(')')

cntl, cntr = 0, 0
s2 = 0
flag = 0
for i in range(l + 1):
    if s[i] == '(':
        cntl += 1
    else:
        cntr += 1

if cntl <= cntr:
    s1 = '(' * (max((cntr - cntl), 0))
    print(s1, end='')
else:
    s2 = ')' * (max((cntl - cntr), 0))
    flag = 1

print(s, end='')
r1 = ')' * (max((n - l - 1), 0))
print(r1, end='')

if flag:
    print(s2)

Submission status: Wrong Answer

Solution code:
n = int(input())
s = input()
l = s.rfind(')')

cntl, cntr = 0, 0
s2 = 0
flag = 0
for i in range(l+1):
    if s[i] == '(':
        cntl += 1
    else:
        cntr += 1

if cntl <= cntr:
    s1 = '(' * (max((cntr - cntl), 0))
    print(s1, end='')
else:
    s2 = ')' * (max((cntl - cntr), 0))
    flag = 1

print(s, end='')
r1 = ')' * (max((n - l - 1), 0))
print(r1)

if flag:
    print(s2)

Submission status: Wrong Answer

Solution code:
def test(length):
    l,r = 0,0
    # print(length, '-')
    for i in range(0,len(length), 2):
        if length[i] > length[i+1]:
            l = length[i] - length[i+1]
        elif length[i] < length[i+1]:
            r = length[i+1] - length[i]
            # print(l,r)
            if l >= r:
                l -= r
            else:
                return False
        # print(l,r)
    return True if l == 0 else False


def run_length(data, init=''):
    length = [] if data[0] == ')' else [0]
    tmp = init
    cnt = 0
    for c in data:
        if tmp != c:
            length.append(cnt)
            cnt = 0
        tmp = c
        cnt += 1
    length.append(cnt)
    if data[-1] == '(':
        length.append(0)
    return length


n = int(input())
s = input()

length = run_length(s, '')
if test(length):
    print(s)
    exit()
# print(length)
length.append(0)
length.append(0)
for i in range(0,len(length) - 2, 2):
    if length[i] > length[i+1]:
        length[-1] += length[i] - length[i+1]
    elif length[i] < length[i+1]:
        length[0] += length[i+1] - length[i]
ans = []
for i in range(0,len(length), 2):
    ans.append('('*length[i])
    ans.append(')'*length[i+1])
print(''.join(ans))

Submission status: Wrong Answer

Solution code:
def test(length):
    l,r = 0,0
    # print(length, '-')
    for i in range(0,len(length), 2):
        if length[i] > length[i+1]:
            l = length[i] - length[i+1]
        elif length[i] < length[i+1]:
            r = length[i+1] - length[i]
            # print(l,r)
            if l >= r:
                l -= r
            else:
                return False
        # print(l,r)
    return True if l == 0 else False


def run_length(data, init=''):
    length = [] if data[0] == ')' else [0]
    tmp = init
    cnt = 0
    for c in data:
        if tmp != c:
            length.append(cnt)
            cnt = 0
        tmp = c
        cnt += 1
    length.append(cnt)
    if data[-1] == '(':
        length.append(0)
    return length


n = int(input())
s = input()

length = run_length(s, '')
if test(length):
    print(s)
    exit()
# print(length)
for i in range(0,len(length), 2):
    if length[i] > length[i+1]:
        length[i+1] = length[i]
    elif length[i] < length[i+1]:
        length[0] += length[i+1] - length[i]
ans = []
for i in range(0,len(length), 2):
    ans.append('('*length[i])
    ans.append(')'*length[i+1])
print(''.join(ans))

Submission status: Wrong Answer

Solution code:
def test(s):
    l,r = 0,0
    for i in range(0,len(s), 2):
        if length[i] > length[i+1]:
            l = length[i] - length[i+1]
        elif length[i] < length[i+1]:
            r = length[i+1] - length[i]
            if l >= r:
                l -= r
            else:
                return False

    return True


def run_length(data, init=''):
    length = [] if data[0] == ')' else [0]
    tmp = init
    cnt = 0
    for c in data:
        if tmp != c:
            length.append(cnt)
            cnt = 0
        tmp = c
        cnt += 1
    length.append(cnt)
    if data[-1] == '(':
        length.append(0)
    return length


n = int(input())
s = input()

length = run_length(s, '')
# print(length)
for i in range(0,len(length), 2):
    if length[i] > length[i+1]:
        length[i+1] = length[i]
    elif length[i] < length[i+1]:
        length[0] += length[i+1] - length[i]
if test(length):
    print(s)
    exit()
ans = []
for i in range(0,len(length), 2):
    ans.append('('*length[i])
    ans.append(')'*length[i+1])
print(''.join(ans))

Submission status: Wrong Answer

Solution code:

def run_length(data, init=''):
    length = [] if data[0] == ')' else [0]
    tmp = init
    cnt = 0
    for c in data:
        if tmp != c:
            length.append(cnt)
            cnt = 0
        tmp = c
        cnt += 1
    length.append(cnt)
    if data[-1] == '(':
        length.append(0)
    return length


n = int(input())
s = input()
length = run_length(s, '')
# print(length)
for i in range(0,len(length), 2):
    if length[i] > length[i+1]:
        length[i+1] = length[i]
    elif length[i] < length[i+1]:
        length[0] += length[i+1] - length[i]
ans = []
for i in range(0,len(length), 2):
    ans.append('('*length[i])
    ans.append(')'*length[i+1])
print(''.join(ans))

Submission status: Wrong Answer

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

replaced = S.replace('()', '')
ans = ''
ans += '(' * list(replaced).count(')')
ans += S
ans += ')' * list(replaced).count('(')

print(ans)

Submission status: Wrong Answer

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

l = 0
r = 0

for i in range(N):
    if S[i] == "(":
        r += 1
    elif S[i] == ")":
        l += 1

print("(" * l + S + ")" * r)

Submission status: Wrong Answer

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

# 足りない（）の数を求めてみる
left = 0  # (
right = 0 # )
l_count = 0
for i in range(N):
    if S[i] == "(":
        right += 1
    elif S[i] == ")" and right > 0:
        right -= 1
    else:
        l_count += 1

r_count = 0
for i in range(N-1,-1,-1):
    if S[i] == ")":
        left += 1
    elif S[i] == "(" and left > 0:
        left += 1
    else:
        r_count += 1

left = "".join(["(" for _ in range(l_count)])
right = "".join([")" for _ in range(r_count)])

print(left+S+right)

Submission status: Wrong Answer

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

L,R=0,0
l,r=0,0

for i in S:
    if "(":l +=1
    else:l -=1;L=min(L,l)

for i in S[::-1]:
    if ")":r +=1
    else:r -=1;R=min(R,r)

print("("*-L+S+")"*-R)

Submission status: Wrong Answer

Solution code:
n=int(input())
s=input()
S=s.split("()")
L,R=0,0
for i in S:
    for j in i:
        if j==")":L +=1
        else:R +=1

print("("*L+s+")"*R)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
N=int(input())
S=list(input())
c=0
L=[0]*N
L[0]=1 if S[0]=='(' else -1
for i in range(1,N):
    if S[i]=='(':
        L[i]=L[i-1]+1
    else:
        L[i]=L[i-1]-1
        
if L[N-1]<0:
    S.insert(0,'('*abs(L[N-1]))
elif L[N-1]>0:
    S.append(')'*L[N-1])

print(''.join(S))

Submission status: Wrong Answer

Solution code:
# coding: utf-8
N=int(input())
S=list(input())

l=0
r=0
pl=0
pr=0


for i in range(N):
    if S[i]==")":
        r+=1
        if l<r:
            pl+=1
        else:
            pr-=1
    else:
        l+=1
        pr+=1

sl=["(" for i in range(pl)]
sr=[")" for i in range(pr)]

ans=sl + S + sr

print("".join(ans))

Submission status: Wrong Answer

Solution code:
N = int(input())

S = input()

l = 0
r = 0
for s in S:
  if s == "(":
    r += 1
  else:
    if l:
      r -= 1
    else:
      l += 1
print("("*l + S + ")"*r)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
n = int(input())
s = input()
reverse = [] # これに右端から詰めていく
stack_right = 0 # 未処理の)がたまっている数
stack_left = 0 #未処理の(がたまっている数
for i in range(n):
    if s[n-1-i] == ")":
        stack_right += 1
        reverse.append(")"*stack_left)
        reverse.append("("*stack_left)
        reverse.append(")")
        stack_left = 0 #全て精算したので0に戻す
    else: #(が出てきた場合はstack_lenによって分岐
        if stack_right > 0:
            stack_right -=1
            reverse.append("(")
        else:
            stack_left += 1
reverse.append("("*stack_right)
reverse.append(")"*stack_left)
reverse.append("("*stack_left)
ans = reverse[::-1]
print("".join(ans))

Submission status: Wrong Answer

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

l = S.count("(")
r = S.count(")")
S

cnt = 0
for i in range(N):
    if S[i] == "(":
        break
    cnt += 1
l += cnt
S = "(" * cnt + S

cnt = 0
for i in range(r+l)[::-1]:
    if S[i] == ")":
        break
    cnt += 1
r += cnt
S = S + ")" * cnt
                
if l >= r:
    S = S + ")" * (l - r)
else:
    S = "(" * (r - l) + S
    
print(S)

Submission status: Wrong Answer

Solution code:
from itertools import groupby

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

l = [[i, len(list(j))] for i, j in groupby(S)] + [[0, 0]]

ans = ""
s = 0
if l[0][0] == ")":
    ans += "(" * l[0][1] + ")" * l[0][1]
    s = 1

for i in range(s,len(l)-1)[::2]:
    m = max(l[i][1], l[i+1][1])
    ans += "(" * m + ")" * m
    
print(ans)

Submission status: Wrong Answer

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

cr = 0
cl = 0

for i in range(N):
  if i == "(":
    cr += 1
  else:
    if cr > 0:
      cr -= 1
    else :
      cl += 1
      
print("("*cl+S+")"*cr)

Submission status: Wrong Answer

Solution code:
import re

N = int(input())
S = list(str(input()))

migi = 0
hidari = 0
arr = []
cnt = 0

for i in S:
  if i == "(":
    if migi == 1 and hidari > 0:
      arr.append(cnt)
      hidari -= 1
    if migi == 1 and hidari == 0:
      migi = 0
    hidari += 1
  else:
    migi = 1
    if hidari > 0:
      hidari -= 1
      
  cnt += 1
if hidari > 0:
  for i in range(hidari):
    arr.append(len(S)+i)

cnt = 0
for i in range(len(arr)):
  S.insert(arr[i]+cnt, ")")
  cnt += 1

#########

migi = 0
hidari = 0
arr = []

le = len(S)
cnt = le-1
for i in range(len(S)):
  if S[le-1-i] == ")":
    if migi == 1 and hidari > 0:
      arr.append(cnt)
      hidari -= 1
    if migi == 1 and hidari == 0:
      migi = 0
    hidari += 1
  else:
    migi = 1
    if hidari > 0:
      hidari -= 1
      
  cnt -= 1
if hidari > 0:
  for i in range(hidari):
    arr.append(0)

cnt = 0
for i in range(len(arr)):
  S.insert(arr[i]+cnt, "(")
  cnt += 1

STR = ""
for i in S:
  STR = STR + i
print(STR)

Submission status: Wrong Answer

Solution code:
N = int(input())
S = input()
A = []
a = 0
l = r = 0
for s in S:
    if s == '(':
        if a >= 0:
            a += 1
        else:
            l -= a
            a = 1
    else:
        # s == ')'
        a -= 1
if a != 0:
    r = a

# print(l, r)

print('('*l + S + ')' * r)

Submission status: Wrong Answer

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

flag = False

r_left_blaket = 0
l_right_blaket = 0
l_left_blaket = 0

for i in range(n-1, -1, -1):
    if flag is True:
        if s[i] == '(':
            l_left_blaket += 1
        else:
            l_right_blaket += 1

    else:
        if s[i] == '(':
            r_left_blaket += 1
        else:
            l_right_blaket += 1
            flag = True

if l_right_blaket >= l_left_blaket:
    s = '(' * (l_right_blaket-l_left_blaket) + s
    s = s + ')' * r_left_blaket
else:
    s = s + ')' * ((l_left_blaket-l_right_blaket) + r_left_blaket)

print(s)

Submission status: Wrong Answer

Solution code:
import collections

n = int(input())
s = input()


d = collections.deque()
condition = 0
l_num = 0
t = []
for i in range(n):
    if condition == 0:
        if s[i] == '(':
            d.append('(')
            condition = 1
            l_num += 1
        else:
            t.append('()')
    elif condition == 1:
        if s[i] == '(':
            l_num += 1
        else:
            t.append('()')
            l_num -= 1
            if l_num > 0:
                condition = 1
            else:
                condition = 0

if condition == 1:
    t.append('()'*l_num)

for i in t:
    print(i, end='')

Submission status: Wrong Answer

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

tmp = []
ans = ""

for i in s:
    if i == "(":
        tmp.append("(")
    else:
        if len(tmp) == 0:
            ans = "(" + ans + ")"
        else:
            ans += tmp.pop() + ")"
print(ans + "".join(tmp) + ")" * len(tmp))

Submission status: Wrong Answer

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

tmp = []
ans = ""
for i in s:
    if i == "(":
        tmp.append("(")
    else:
        if len(tmp) == 0:
            ans = "(" + ans + ")"
        else:
            ans += tmp.pop() + ")"
print(ans)

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, atan, degrees
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect
import numpy as np

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
S = input()

T = S.replace("()", "")

l = 0
r = 0
for x in T:
	if x == ")":
		l += 1
	else:
		r += 1
print("("*l + S + ")"*r)

Submission status: Wrong Answer

Solution code:
N = int(input())
S = input()
l, r = [0], [0]

if S[0] == '(':
    l[-1] += 1
else:
    r[-1] += 1

for i in range(N-1):
    if S[i] == ')' and S[i+1] == '(':
        l.append(1)
        r.append(0)
    if S[i+1] == '(':
        l[-1] += 1
    else:
        r[-1] += 1
# print(l, r)

ans = ''
for i in range(len(l)):
    nm = max(l[i], r[i])
    ans += '(' * nm
    ans += ')' * nm
print(ans)

Submission status: Wrong Answer

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

d = []
o = c = 0
for i in range(N):
    if S[i] == '(':
        o += 1
    else:
        c += 1
    d.append(o - c)
x = min(d)
print('(' * -x + S + ')' * (d[-1] - x))

Submission status: Wrong Answer

Solution code:
def two_int():
    N, K = map(int, input().split())
    return N,K

def one_int():
    return int(input())

def one_str():
    return input()

def many_int():
    return list(map(int, input().split()))
# import sys
# input = sys.stdin.readline

N=one_int()
S=one_str()

try:
    first_start_index=S.index("(")
except:
    first_start_index=0

count=0
for i in range(first_start_index, N):
    if S[i]=="(":
        count += 1
    else:
        count -= 1

#count　がプラス   => その分閉じカッコが後ろにつく
#count  がマイナス => その分開始カッコが銭湯に付く
ans=S
if count >0:
    ans+= ")"*count
else:
    ans = "("*int(abs(count)) +ans

ans = first_start_index*"(" + ans

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
S = input()
tmp = S[-1]
index = 0
ans = ''
cnt1 = 0
cnt2 = 0
for i in range(N):
    if S[i] == ')':
        cnt1 += 1


for i in reversed(range(N)):
    if S[i] == ')':
        break
    if S[i] == '(':
        cnt2 += 1

S = '(' * (cnt1 - S.count('(') + cnt2) + S
S += ')' * cnt2

print(S)

Submission status: Wrong Answer

Solution code:
n = int(input())
s = list(input())
validation = [False for _ in range(n)]

pair = -1
searching_pair = False
for i in range(n):
    if not searching_pair and "(" == s[i]:
        pair = i
        searching_pair = True
    elif searching_pair and ")" == s[i]:
        validation[pair] = True
        validation[i] = True
        searching_pair = False

ans = "".join(s)
for i in range(n):
    if not validation[i]:
        if "(" == s[i]:
            ans = ans + ")"
        else:
            ans = "(" + ans

print(ans)

Submission status: Wrong Answer

Solution code:

def count(S,i):
    temp=S[:i]
    return temp.count('(')-temp.count(')')

def calc_x(S):
    n=len(S)
    d=[]
    for i in range(1,n+1):
        d.append(count(S,i))
    return min(d)

if __name__ == '__main__':
    N=int(input())
    S=input()
    x=calc_x(S)
    d_s=count(S,N)

    S="("*(-x)+S+")"*(d_s-x)
    print(S)

Submission status: Wrong Answer

Solution code:

def count(S,i):
    temp=S[:i]
    return temp.count('(')-temp.count(')')

def calc_x(S):
    n=len(S)
    d=[]
    for i in range(1,n+1):
        d.append(count(S,i))
    return min(d)

if __name__ == '__main__':
    N=int(input())
    S=list(input())
    x=calc_x(S)
    d_s=count(S,N)

    for i in range(-x):
        S.insert(0,"(")
    for j in range(d_s-x):
        S.append(")")
    print("".join(S))

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right
N = int(input())
S = input()
dp = [[0 for _ in range(2)] for _ in range(N)]
if S[0] == "(":
    dp[0][0] = 1
else:
    dp[0][1] = 1
for i in range(1, N):
    dp[i][0] = dp[i-1][0]
    dp[i][1] = dp[i-1][1]
    if S[i] == "(":
        dp[i][0] += 1
    else:
        dp[i][1] += 1

for i in range(N):
    if dp[i][0] < dp[i][1]:
        for j in range(N):
            dp[j][0] += 1
    else:
        if i == 0:
            if dp[-1][0] > dp[-1][1]:
                dp[-1][1] += 1
        else:
            if dp[-1][0] - dp[i-1][0] > dp[-1][1] - dp[i-1][1]:
                dp[-1][1] += (dp[-1][0] - dp[i-1][0]) - (dp[-1][1] - dp[i-1][1])

ans = ""
for i in range(N):
    if i == 0:
        ans += "("*dp[i][0] + ")"*dp[i][1]
    else:
        ans += "("*(dp[i][0]-dp[i-1][0]) + ")"*(dp[i][1] - dp[i-1][1])
print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right
N = int(input())
S = input()
dp = [[0 for _ in range(2)] for _ in range(N)]
if S[0] == "(":
    dp[0][0] = 1
else:
    dp[0][1] = 1
for i in range(1, N):
    dp[i][0] = dp[i-1][0]
    dp[i][1] = dp[i-1][1]
    if S[i] == "(":
        dp[i][0] += 1
    else:
        dp[i][1] += 1


print(dp)
for i in range(N):
    if dp[i][0] < dp[i][1]:
        for j in range(N):
            dp[j][0] += 1
    else:
        if i == 0:
            if dp[-1][0] > dp[-1][1]:
                dp[-1][1] += 1
        else:
            if dp[-1][0] - dp[i-1][0] > dp[-1][1] - dp[i-1][1]:
                dp[-1][1] += (dp[-1][0] - dp[i-1][0]) - (dp[-1][1] - dp[i-1][1])

ans = ""
for i in range(N):
    if i == 0:
        ans += "("*dp[i][0] + ")"*dp[i][1]
    else:
        ans += "("*(dp[i][0]-dp[i-1][0]) + ")"*(dp[i][1] - dp[i-1][1])
print(ans)