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 sys
sys.setrecursionlimit(10**6)
if sys.platform in (['ios','darwin','win32']):
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return [int(s) for s in input().split()]

def main():
	N = INT()
	S = input().rstrip()
	S = [s for s in S]

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

	divider = -1
	for i in range(N-1):
		if S[i] == ')' and S[i+1] == '(':
			divider = i+1

	# print(center, divider)
	supplement = 0
	for c in center:
		c += supplement
		divider += supplement
		if divider == -1:
			left = S[:c].count('(')
			right = S[c:].count(')')
		elif divider < c:
			left = S[:c].count('(') - S[:c].count(')')
			right = S[c:].count(')')
		elif divider > c:
			left = S[:c].count('(')
			right = S[c:divider].count(')')
		# print(c, divider, left, right)
		while left != right:
			if left < right:
				S.insert(0, '(')
				left += 1
				supplement += 1
			else:
				S.append(')')
				right += 1

	l, r = 0, 0
	for s in S:
		if s == '(': l += 1
		if s == ')': r += 1
	if l<r:
		for _ in range(r-l):
			S.insert(0, '(')
	elif l>r:
		for _ in range(l-r):
			S.append(')')
	
	print(''.join(S))

if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
# if sys.platform in (['ios','darwin','win32']):
# 	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return [int(s) for s in input().split()]

def main():
	N = INT()
	S = input().rstrip()
	S = [s for s in S]

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

	divider = -1
	for i in range(N-1):
		if S[i] == ')' and S[i+1] == '(':
			divider = i+1

	# print(center, divider)
	supplement = 0
	for c in center:
		c += supplement
		divider += supplement
		if divider == -1:
			left = S[:c].count('(')
			right = S[c:].count(')')
		elif divider < c:
			left = S[divider:c].count('(')
			right = S[c:].count(')')
		elif divider > c:
			left = S[:c].count('(')
			right = S[c:divider].count(')')
		# print(c, divider, left, right)
		while left != right:
			if left < right:
				S.insert(0, '(')
				left += 1
				supplement += 1
			else:
				if c > divider:
					S.append(')')
				else:
					S.insert(c+1,')')
				right += 1
				supplement += 1

	l, r = 0, 0
	for s in S:
		if s == '(': l += 1
		if s == ')': r += 1
	if l<r:
		for _ in range(r-l):
			S.insert(0, '(')
	elif l>r:
		for _ in range(l-r):
			S.append(')')
	
	print(''.join(S))

if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
# if sys.platform in (['ios','darwin','win32']):
# 	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return [int(s) for s in input().split()]

def main():
	N = INT()
	S = input().rstrip()
	S = [s for s in S]

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

	divider = -1
	for i in range(N-1):
		if S[i] == ')' and S[i+1] == '(':
			divider = i+1

	supplement = 0
	for c in center:
		c += supplement
		divider += supplement
		if divider == -1:
			left = S[:c].count('(')
			right = S[c:].count(')')
		elif divider < c:
			left = S[divider:c].count('(')
			right = S[c:].count(')')
		elif divider > c:
			left = S[:c].count('(')
			right = S[c:divider].count(')')
		while left != right:
			if left < right:
				S.insert(0, '(')
				left += 1
				supplement += 1
			else:
				S.append(')')
				right += 1

	l, r = 0, 0
	for s in S:
		if s == '(': l += 1
		if s == ')': r += 1
	if l<r:
		for _ in range(r-l):
			S.insert(0, '(')
	elif l>r:
		for _ in range(l-r):
			S.append(')')
	
	print(''.join(S))

if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
if sys.platform in (['ios','darwin','win32']):
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return [int(s) for s in input().split()]

def main():
	N = INT()
	S = input().rstrip()
	S = [s for s in S]

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

	divider = 0
	for i in range(N-1):
		if S[i] == ')' and S[i+1] == '(':
			divider = i+1

	if divider:
		for c in center:
			left = S[divider:c].count('(')
			right = S[c:divider].count(')')
			while left != right:
				if left < right:
					S.insert(0, '(')
					left += 1
				else:
					S.append(')')
					right += 1
		l, r = 0, 0
		for s in S:
			if s == '(': l += 1
			if s == ')': r += 1
		if l<r:
			for _ in range(r-l):
				S.insert(0, '(')
		elif l>r:
			for _ in range(l-r):
				S.append(')')
	else:
		for c in center:
			left = S[:c].count('(')
			right = S[c:].count(')')
			while left != right:
				if left < right:
					S.insert(0, '(')
					left += 1
				else:
					S.append(')')
					right += 1
	
	print(''.join(S))

if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
# 始めカッコの個数を先に確定させる
# ある特定の時点で")"の方が多いなら、あとから"("が出て来ても遅い
ans = -1  # これの最小値になった絶対値分を文頭につける
N = int(input())
S = input()
hazimekakko = 0
owarikakko = 0
for i in range(N):
    if S[i] == "(":
        hazimekakko += 1
    else:
        owarikakko += 1
    ans = max(ans, owarikakko-hazimekakko)

S = abs(ans)*"(" + S

for i in range(len(S)):
    if S[i] == "(":
        hazimekakko += 1
    else:
        owarikakko += 1

S = S + (hazimekakko-owarikakko)*")"
print(S)

Submission status: Wrong Answer

Solution code:
from collections import Counter
N = int(input())
S = input()

tmp = S[0]
for i in range(1, N):
    if S[i-1] == ")" and S[i] == "(":
        tmp += " "
    tmp += S[i]

string_split = tmp.split()
hazimekakko = 0
owarikakko = 0
for s in string_split:
    count = Counter(s)
    if count["("] > count[")"]:
        owarikakko += count["("] - count[")"]
        hazimekakko += count[")"] - count["("]
    else:
        owarikakko += count["("] - count[")"]
        hazimekakko += count[")"] - count["("]

print(hazimekakko*"(" + S + owarikakko*")")

# どんどんたまっていたったけど、最後に逆転したときに余分に追加することがある
# 10
# (((()())))
# ((((((()()))))))

Submission status: Wrong Answer

Solution code:
from collections import Counter
N = int(input())
S = input()

tmp = S[0]
for i in range(1, N):
    if S[i-1] == ")" and S[i] == "(":
        tmp += " "
    tmp += S[i]

string_split = tmp.split()
hazimekakko = 0
owarikakko = 0
for s in string_split:
    count = Counter(s)
    if count["("] > count[")"]:
        owarikakko += count["("] - count[")"]
    else:
        hazimekakko += count[")"] - count["("]

print(hazimekakko*"(" + S + owarikakko*")")

Submission status: Wrong Answer

Solution code:
from collections import Counter
N = int(input())
S = input()
print(S)
exit()

Submission status: Wrong Answer

Solution code:
from collections import Counter
N = int(input())
S = input()
tmp = S[0]
for i in range(1, N):
    if S[i-1] == ")" and S[i] == "(":
        tmp += " "
    tmp += S[i]

string_split = tmp.split()
hazimekakko = 0
owarikakko = 0
for s in string_split:
    count = Counter(s)
    if count["("] > count[")"]:
        owarikakko += count["("] - count[")"]
    else:
        hazimekakko += count[")"] - count["("]

print(hazimekakko*"(" + S + owarikakko*")")

Submission status: Wrong Answer

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

d = S.replace('()','')

l = d.count('(')
r = d.count(')')

z = '('*r + S + ')'*l

print(z)

Submission status: Wrong Answer

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

d = S.replace('()','')

l = d.count('(')
r = d.count(')')

z = '('*l + S + ')'*r

print(z)

Submission status: Wrong Answer

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

d = S.replace('()','')

l = d.count('(')
r = d.count(')')

z = '('*l + d + ')'*r

print(z)

Submission status: Wrong Answer

Solution code:
# ABC146 D - Insertion
n=int(input())
s=input()
ss=s
l_cnt=0
r_cnt=0
if s.count('()')>0:
    # ss=ss.replace('()','')
    while ss.count('()')>0:
        ss=ss.replace('()','')
    l_cnt=ss.count('(')
    r_cnt=ss.count(')')
    if l_cnt>r_cnt:
        s+=')'*(l_cnt-r_cnt)
    elif l_cnt==r_cnt:
        s+=')'*l_cnt
        s='('*r_cnt+s
        # pass
        # s+=')'*l_cnt
        # s='('*r_cnt+s
    elif l_cnt<r_cnt:
        s='('*(r_cnt-l_cnt)+s
    print(s)
else:
    l_cnt=s.count('(')
    r_cnt=s.count(')')
    s+=')'*l_cnt
    s='('*r_cnt+s
    print(s)

Submission status: Wrong Answer

Solution code:
# ABC146 D - Insertion
n=int(input())
s=input()
ss=s
l_cnt=0
r_cnt=0
if s.count('()')>0:
    # ss=ss.replace('()','')
    l_cnt=ss.count('(')
    r_cnt=ss.count(')')
    if l_cnt>r_cnt:
        s+=')'*(l_cnt-r_cnt)
    elif l_cnt==r_cnt:
        pass
        # s+=')'*l_cnt
        # s='('*r_cnt+s
    elif l_cnt<r_cnt:
        s='('*(r_cnt-l_cnt)+s
    print(s)
else:
    l_cnt=s.count('(')
    r_cnt=s.count(')')
    s+=')'*l_cnt
    s='('*r_cnt+s
    print(s)

Submission status: Wrong Answer

Solution code:
# ABC146 D - Insertion
n=int(input())
s=input()
ss=s
l_cnt=0
r_cnt=0
if s.count('()')>0:
    ss=ss.replace('()','')
    l_cnt=ss.count('(')
    r_cnt=ss.count(')')
    if l_cnt>r_cnt:
        s+=')'*(l_cnt-r_cnt)
    elif l_cnt==r_cnt:
        s+=')'*l_cnt
        s='('*r_cnt+s
    elif l_cnt<r_cnt:
        s='('*(r_cnt-l_cnt)+s
    print(s)
else:
    l_cnt=s.count('(')
    r_cnt=s.count(')')
    s+=')'*l_cnt
    s='('*r_cnt+s
    print(s)

Submission status: Wrong Answer

Solution code:
# ABC146 D - Insertion
n=int(input())
s=input()
ss=s
l_cnt=0
r_cnt=0
if s.count('()')>0:
    ss=ss.replace('()','')
    l_cnt=ss.count('(')
    r_cnt=ss.count(')')
    if l_cnt>r_cnt:
        s+=')'*(l_cnt-r_cnt)
    elif l_cnt==r_cnt:
        pass
    elif l_cnt<r_cnt:
        s='('*(r_cnt-l_cnt)+s
    print(s)
else:
    l_cnt=s.count('(')
    r_cnt=s.count(')')
    s+=')'*l_cnt
    s='('*r_cnt+s
    print(s)

Submission status: Wrong Answer

Solution code:
# ABC146 D - Insertion
n=int(input())
s=input()

L=[]
R=[]
flg='l'
l_cnt=0
r_cnt=0
for i,ss in enumerate(s):
    if ss=='(':
        if flg=='r':
            R.append(r_cnt)
            r_cnt=0
        flg='l'
        l_cnt+=1
    elif ss==')':
        if flg=='l':
            L.append(l_cnt)
            l_cnt=0
        flg='r'
        r_cnt+=1
    
    if i==n-1:
        if flg=='r':
            R.append(r_cnt)
        elif flg=='l':
            L.append(l_cnt)
            R.append(0)

LR=[]
ans=''
for l,r in zip(L,R):
    LR.append(max(l,r))
for lr in LR:
    ans+='('*lr
    ans+=')'*lr

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
s = input()
c1 = 0
c2 = 0
c = 0
for i in s:
    if i == '(':
        c1 += 1
    else:
        c2 += 1
        if c1 < c2:
            c += 1
print('('*c + s + ')'*(c+c1-c2))

Submission status: Wrong Answer

Solution code:
n = int(input())
s = input()
ok_index = []
front = 0
back = 0
for i in range(n - 1):
    if s[i:i + 2] == '()':
        ok_index.append(i)
        ok_index.append(i + 1)
for i in range(n):
    if i in ok_index:
        continue
    if s[i] == ')':
        front += 1
    else:
        back += 1
ans = ''
for i in range(front):
    ans += '('
ans += s
for i in range(back):
    ans += ')'
print(ans)

Submission status: Wrong Answer

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

    L,R = "(",")"
    first_L,first_R = -1,-1
    last_L,last_R = -1,-1
    cnt_L,cnt_R = 0,0
    for i in range(len(S)):
        if S[i]==L:
            last_L = i
            if first_L==-1:
                first_L=i
            cnt_L += 1


        else:
            last_R=i
            if first_R==-1:
                first_R=i
            cnt_R += 1

    if cnt_L == 0:
        S  = "("*cnt_R + S
        print(S)
    elif cnt_R == 0:
        S  = S + ")"*cnt_L
        print(S)

    else:
        cnt = 0
        for i in range(first_L,N):
            if S[i]==")":
                cnt +=1
        right_sub = ")"*max((cnt_L-cnt),0)
        cnt = 0
        for i in range(0,last_R+1):
            if S[i]=="(":
                cnt +=1
        left_sub = "("*max(0,(cnt_R-cnt))
        print(left_sub+S+right_sub)
        


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

    L,R = "(",")"
    first_L,first_R = -1,-1
    last_L,last_R = -1,-1
    cnt_L,cnt_R = 0,0
    for i in range(len(S)):
        if S[i]==L:
            last_L = i
            if first_L==-1:
                first_L=i
            cnt_L += 1


        else:
            last_R=i
            if first_R==-1:
                first_R=i
            cnt_R += 1

    if cnt_L == 0:
        S  = "("*cnt_R + S
        print(S)
    elif cnt_R == 0:
        S  = S + ")"*cnt_L
        print(S)

    else:
        cnt = 0
        for i in range(first_L,N):
            if S[i]==")":
                cnt +=1
        right_sub = ")"*(cnt_L-cnt)
        cnt = 0
        for i in range(0,last_R+1):
            if S[i]=="(":
                cnt +=1
        left_sub = "("*(cnt_R-cnt)
        print(left_sub+S+right_sub)
        


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

    L,R = "(",")"
    first_L,first_R = -1,-1
    last_L,last_R = -1,-1
    cnt_L,cnt_R = 0,0
    for i in range(len(S)):
        if S[i]==L:
            last_L=i
            if first_L==-1:
                first_L=i
            cnt_L += 1
        else:
            last_R=i
            if first_R==-1:
                first_L=i
            cnt_R += 1

    if cnt_L == 0:
        S  = "("*cnt_R + S
        print(S)
    elif cnt_R == 0:
        S  = S + ")"*cnt_L
        print(S)
    else:
        cnt = 0
        for i in range(first_L,last_L+1):
            if S[i]==")":
                cnt +=1
        right_sub = ")"*(cnt_L-cnt)
        cnt = 0
        for i in range(first_R,last_R+1):
            if S[i]=="(":
                cnt +=1
        left_sub = "("*(cnt_R-cnt)
        print(left_sub+S+right_sub)
        


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline
 
##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)
 
##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力
 
# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと
 
##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順
 
# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順
 
def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
 
def main():
    N = inputInt()
    S = input()
    S = S[:-1]
    
    ans = ""
    cnt = 0
    for i in S:
        if i == ")":
            if cnt == 0:
                ans += "()"
            else:
                cnt -= 1
                ans += ")"
        else:
            cnt += 1
            ans += "("
            
    if cnt > 0:
        for i in range(cnt):
            ans += ")"
    
    print(ans)
    
if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
def groupby(a):
    a2=[[a[0],1]]
    for i in range(1,len(a)):
        if a2[-1][0]==a[i]:
            a2[-1][1]+=1
        else:
            a2.append([a[i],1])
    return a2

n=int(input())
s=input()
t=groupby(s)
c=s.count("(")-s.count(")")
if c>0:
    s=s+c*")"
    if t[0][0]==")":
        s=("("*t[0][1])+s+(")"*t[0][1])
elif c<0:
    s=(-c)*"("+s
    if t[-1][0]=="(":
        s=("("*t[-1][1])+s+(")"*t[-1][1])
else:
    if t[0][0]==")":
        s=("("*t[0][1])+s+(")"*t[0][1])
    if t[-1][0]=="(":
        s=("("*t[-1][1])+s+(")"*t[-1][1])

print(s)

Submission status: Wrong Answer

Solution code:
def groupby(a):
    a2=[[a[0],1]]
    for i in range(1,len(a)):
        if a2[-1][0]==a[i]:
            a2[-1][1]+=1
        else:
            a2.append([a[i],1])
    return a2

n=int(input())
s=input()
t=groupby(s)
c=s.count("(")-s.count(")")
if c>0:
    s=s+c*")"
else:
    s=(-c)*"("+s
if t[0][0]==")":
    s=("("*t[0][1])+s+(")"*t[0][1])
if t[-1][0]=="(":
    s=("("*t[-1][1])+s+(")"*t[-1][1])
print(s)

Submission status: Wrong Answer

Solution code:
def groupby(a):
    a2=[[a[0],1]]
    for i in range(1,len(a)):
        if a2[-1][0]==a[i]:
            a2[-1][1]+=1
        else:
            a2.append([a[i],1])
    return a2

n=int(input())
s=input()
t=groupby(s)
if t[-1][0]=="(":
    s=s+(")"*t[-1][1])
c=s.count("(")-s.count(")")
if c>0:
    print(s+c*")")
else:
    print((-c)*"("+s)

Submission status: Wrong Answer

Solution code:
def groupby(a):
    a2=[[a[0],1]]
    for i in range(1,len(a)):
        if a2[-1][0]==a[i]:
            a2[-1][1]+=1
        else:
            a2.append([a[i],1])
    return a2

n=int(input())
s=input()
t=groupby(s)
if t[0][0]==")":
    s=("("*t[0][1])+s
c=s.count("(")-s.count(")")
if c>0:
    print(s+c*")")
else:
    print((-c)*"("+s)

Submission status: Wrong Answer

Solution code:
def groupby(a):
    a2=[[a[0],1]]
    for i in range(1,len(a)):
        if a2[-1][0]==a[i]:
            a2[-1][1]+=1
        else:
            a2.append([a[i],1])
    return a2

n=int(input())
s=input()
c=s.count("(")-s.count(")")
if c>0:
    s=s+c*")"
else:
    s=(-c)*"("+s
t=groupby(s)
if t[0][0]==")":
    s=("("*t[0][1])+s
if t[-1][0]=="(":
    s=s+(")"*t[-1][1])
c=s.count("(")-s.count(")")
if c>0:
    print(s+c*")")
else:
    print((-c)*"("+s)

Submission status: Wrong Answer

Solution code:
def groupby(a):
    a2=[[a[0],1]]
    for i in range(1,len(a)):
        if a2[-1][0]==a[i]:
            a2[-1][1]+=1
        else:
            a2.append([a[i],1])
    return a2

n=int(input())
s=input()
t=groupby(s)
if t[0][0]==")":
    s=("("*t[0][1])+s
if t[-1][0]=="(":
    s=s+(")"*t[-1][1])
c=s.count("(")-s.count(")")
if c>0:
    print(s+c*")")
else:
    print((-c)*"("+s)

Submission status: Wrong Answer

Solution code:
def groupby(a):
    a2=[[a[0],1]]
    for i in range(1,len(a)):
        if a2[-1][0]==a[i]:
            a2[-1][1]+=1
        else:
            a2.append([a[i],1])
    return a2

n=int(input())
s=input()
t=groupby(s)
l=len(t)
if t[0][0]==")":
    s=("("*t[0][1])+s
if t[-1][0]=="(":
    s=s+(")"*t[-1][1])
l=len(s)
c=0
for i in range(l):
    if s[i]=="(":
        c+=1
    else:
        c-=1
if c>0:
    print(s+c*")")
else:
    print((-c)*"("+s)

Submission status: Wrong Answer

Solution code:
def groupby(a):
    a2=[[a[0],1]]
    for i in range(1,len(a)):
        if a2[-1][0]==a[i]:
            a2[-1][1]+=1
        else:
            a2.append([a[i],1])
    return a2

n=int(input())
s=input()
t=groupby(s)
l=len(t)
if t[0][0]==")":
    s=("("*t[0][1])+s
if t[-1][0]=="(":
    s=s+(")"*t[-1][1])
t=groupby(s)
l=len(t)
ans=""
for i in range(l//2):
    m=max(t[2*i][1],t[2*i+1][1])
    ans+=(m*"("+m*")")
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
n = int(input())
s = input()
cnt = 0
for _s in s[::-1]:
    if _s == ")":
        break
    else:
        cnt += 1
s += ")" * cnt
cnt = 0
for _s in s:
    if _s == "(":
        break
    else:
        cnt += 1
s = "(" * cnt + s
ct = Counter(s)

if ct.get("(") is None:
    ct["("] = 0
if ct.get(")") is None:
    ct[")"] = 0
if ct[")"] > ct["("]:
    s = "(" * (ct[")"] - ct["("]) + s
else:
    s = s + ")" * (ct["("] - ct[")"])
print(s)

Submission status: Wrong Answer

Solution code:
from collections import Counter
n = int(input())
s = input()
ct = Counter(s)
if ct.get("(") is None:
    ct["("] = 0
if ct.get(")") is None:
    ct[")"] = 0
_max = max(ct["("], ct[")"])
print("()" * _max)

Submission status: Wrong Answer

Solution code:
# D - Insertion

N = int(input())
S = input().split("()")

ans = []
for x in S:
    tmp = x
    for _ in range(x.count(")")):
        tmp = "(" + tmp
    for _ in range(x.count("(")):
        tmp += ")"
    ans.append(tmp)

print("()".join(ans))

Submission status: Wrong Answer

Solution code:
N = int(input())
S = input()
ary = []
if S[0] == '(':
    ary.append(1)
else:
    ary.append(0)
    ary.append(1)
for i in range(1, N):
    if S[i-1] == S[i]:
        ary[-1] += 1
    else:
        ary.append(1)
if len(ary) % 2:
    ary.append(0)
c = [0, 0]
for i in range(0, len(ary), 2):
    c[0] += ary[i]
    c[1] += ary[i+1]
    if c[0] < c[1]:
        ary[0] += c[1]-c[0]
        c[0] = c[1]
    elif c[0] > c[1]:
        ary[-1] += c[0]-c[1]
        c[1] = c[0]
ans = ''
for i, n in enumerate(ary):
    if i % 2 == 0:
        ans += '('*n
    else:
        ans += ')'*n
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
s=input()+"1"
a=0
b=[]
for i in range(n):
    if s[i]==s[i+1]:
        a+=1
    else:
        b.append(a+1)
        a=0
if s[-2]=='(':
    b.append(0)
if s[0]==')':
    b.insert(0,0)
for i in range(len(b)//2):    
    c=max(b[2*i],b[2*i+1])
    print('('*c,end=')'*c)

Submission status: Wrong Answer

Solution code:
n=int(input())
s=input()+"1"
a=0
b=[]
for i in range(n):
    if s[i]==s[i+1]:
        a+=1
    else:
        b.append(a+1)
        a=0
if s[-2]=='(':
    b.append(0)
if s[0]==')':
    b.insert(0,0)
print(b)
for i in range(len(b)//2):    
    c=max(b[2*i],b[2*i+1])
    print('('*c,end=')'*c)

Submission status: Wrong Answer

Solution code:
N = int(input())
S = input()
s = 0
mi = 0
for i in range(N):
    s += 1 if S[i] == "(" else -1
    mi = min(mi, s)
if s > 0:
    print(-mi * "(" + S + ")" * s)
else:
    print("(" * max(-s, -mi) + S + ")" * (max(-s, -mi) + s))

Submission status: Wrong Answer

Solution code:
N=int(input())
S=input()
sl=list(S)
change=[0]
for i in range(1,N):
  if (sl[i-1]==')')and(sl[i]=='('):
    change.append(i)

change.append(N)
r_add=0
l_add=0
for i in range(len(change)-1):
  A=sl[change[i]:change[i+1]]
  r=0
  l=0
  for a in A:
    if a=='(':
      l+=1
    else:
      r+=1
      
  if r==l:
    continue
  elif r>l:
    l_add+=r-l
    r_add=max(0,r_add-(r-l))
  else:
    r_add+=l-r
      
print('('*l_add+S+')'*r_add)

Submission status: Wrong Answer

Solution code:
N=int(input())
S=input()
sl=list(S)
change=[0]
for i in range(1,N):
  if (sl[i-1]==')')and(sl[i]=='('):
    change.append(i)

change.append(N)
r_add=0
l_add=0
for i in range(len(change)-1):
  A=sl[change[i]:change[i+1]]
  r=0
  l=0
  for a in A:
    if a=='(':
      l+=1
    else:
      r+=1
      
  if r==l:
    continue
  elif r>l:
    l_add+=r-l
    r_add-=r-l
  else:
    r_add+=l-r
    l_add-=l-r
      
print('('*l_add+S+')'*r_add)

Submission status: Wrong Answer

Solution code:
N=int(input())
S=input()
sl=list(S)
change=[0]
for i in range(1,N):
  if (sl[i-1]==')')and(sl[i]=='('):
    change.append(i)

change.append(N)
r_add=0
l_add=0
for i in range(len(change)-1):
  A=sl[change[i]:change[i+1]]
  r=0
  l=0
  for a in A:
    if a=='(':
      l+=1
    else:
      r+=1
      
  if r==l:
    continue
  elif r>l:
    l_add+=r-l
  else:
    r_add+=l-r
      
print('('*l_add+S+')'*r_add)

Submission status: Wrong Answer

Solution code:
N=int(input())
S=input()
sl=list(S)
change=[0]
ans=''
for i in range(1,N):
  if (sl[i-1]==')')and(sl[i]=='('):
    change.append(i)

change.append(N)
for i in range(len(change)-1):
  A=sl[change[i]:change[i+1]]
  r=0
  l=0
  for a in A:
    if a=='(':
      l+=1
    else:
      r+=1
      
  if r==l:
    ans+=''.join(A)
  elif r>l:
    ans+='('*(r-l)+''.join(A)
  else:
    ans+=''.join(A)+')'*(l-r)
      
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
S=input()
sl=list(S)
rev_sl=reversed(sl)
l_add=0
r_add=0
l=0
r=0
for s in sl:
  if s=='(':
    l+=1
    
  else:
    r+=1
    if l<r:
      l_add+=1
    
r=0
l=0
for s in rev_sl:
  if s==')':
    r+=1
  else:
    l+=1
    if r<l:
      r_add+=1
      
print('('*l_add + S + ')'*r_add)

Submission status: Wrong Answer

Solution code:
S=input()
sl=list(S)
rev_sl=reversed(sl)
l_add=0
r_add=0
l=0
r=0
for s in sl:
  if s=='(':
    l+=1
    
  else:
    r+=1
    if l<r:
      l_add+=1
    
r=0
l=0
for s in rev_sl:
  if s==')':
    r+=1
  else:
    l+=1
    if r<l:
      r_add+=1
      
print('('*l_add + S + ')'*r_add)

Submission status: Wrong Answer

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

r = 0
l = 0

for i in range(N):
    if S[i] == '(':
        r += 1
    elif S[i] == ')':
        l += 1
    if 0 < l and 0 < r:
        if S[i-1] == '(' and S[i] == ')':
            l -= 1
            r -= 1

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

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    S = input()
    left = 0
    right = 0
    left_i = 0
    right_i = N - 1
    while right_i - left_i >= 0:
        if S[left_i] == ")":
            left += 1
            left_i += 1
            continue
        if S[right_i] == "(":
            right += 1
            right_i -= 1
            continue
        if S[left_i] == "(" and S[left_i + 1] == ")":
            left_i += 2
            continue
        if S[right_i-1] == "(" and S[right_i] == ")":
            right_i -= 2
            continue
        if S[left_i] == "(" and S[right_i] == ")":
            left_i += 1
            right_i -= 1
            continue
        if left_i == right_i:
            if S[left_i] == "(":
                right += 1
            else:
                left += 1
            break
    print("("*left + S + ")"*right)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    S = input()
    left = 0
    right = 0
    left_i = 0
    right_i = N - 1
    while right_i - left_i > 0:
        if S[left_i] == ")":
            left += 1
            left_i += 1
        if S[right_i] == "(":
            right += 1
            right_i -= 1
        if S[left_i] == "(" and S[right_i] == ")":
            left_i += 1
            right_i -= 1
        if left_i == right_i:
            if S[left_i] == "(":
                right += 1
            else:
                left += 1
            break
    print("("*left + S + ")"*right)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    S = input()
    ended = 0
    left = 0
    right = 0
    if N == 1:
        return print("()")
    for i in range(N-1):
        if S[i] == "(" and S[i+1] == ")":
            ended += 1
        if S[i] == "(":
            left += 1
        else:
            right += 1
    if S[-1] == "(":
        left += 1
    else:
        right += 1
    left -= ended
    right -= ended
    print("("*right + S + ")"*left)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from sys import stdin
n = int(stdin.readline().rstrip())
s = stdin.readline().rstrip()
sn = ""
point = 0
for i in range(n-1):
    if s[i] == ")" and s[i+1] == "(":
        sn += ")"
        point -= 1
        if point < 0:
            b =  "("*(point*(-1))
            sn  = b + sn
            point = 0
        elif point > 0:
            b = ")"*point
            sn += b
            point = 0
    else:
        if s[i] == ")":
            sn += ")"
            point -= 1
        else:
            sn += "("
            point += 1
sn += s[-1]
if s[-1] == ")":
    point -= 1
else:
    point += 1
if point > 0:
    sn += ")"*point
else:
    sn = "("*(point*(-1)) + sn

print(sn)

Submission status: Wrong Answer

Solution code:
N = int(input())
S = input()
tmp = 0
for i in reversed(range(N)):
    if S[i] == ")":
        tmp = i
        break
left = ""
for i in range(N-tmp-1):
    left += ")"

migi_kakko = 0
hidari_kakko = 0
for i in range(tmp+1):
    if S[i] == ")":
        migi_kakko += 1
    else:
        hidari_kakko += 1

right = ""
for i in range(migi_kakko-hidari_kakko):
    right += "("
for i in range(hidari_kakko-migi_kakko):
    left += ")"

ans = ""
ans += right
ans += S
ans += left
print(ans)

Submission status: Wrong Answer

Solution code:
from sys import stdin
n = int(stdin.readline().rstrip())
s = stdin.readline().rstrip()
sn = ""
point = 0
for i in s:
    if i == "(":
        point += 1
        sn += "("
    else:
        point -= 1
        sn += ")"
    if point == 2:
        sn += ")"
        point -= 1
    elif point == -2:
        sn = "(" + sn
        point += 1

if point == -1:
    sn = "(" + sn
elif point == 1:
    sn += ")"

print(sn)

Submission status: Wrong Answer

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

m = S.count("(")
if m > N-m:
    for _ in range(2*m-N):
        S.append(")")
    print("".join(S))
elif m < N-m:
    T = ["("]*(N-2*m)
    S = T + S
    print("".join(S))
else:
    cnt = 0
    for i in range(N//2):
        if S[i] == ")":
            cnt += 1
    if cnt > N//2-cnt:
        T1 = ["("]*(2*cnt-N//2)
        T2 = [")"]*(2*cnt-N//2)
        S = T1 + S + T2
    print("".join(S))