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:
from collections import deque

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

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

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

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

N=int(input())
S=input()
stack= deque([])
ans=""

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

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

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

N=int(input())
S=input()
stack= deque([])
ans=""

for i in range(N):
  if S[i]=="(":
    stack.append(S[i])
    #print(ans)
  else:
    if stack:
      ans += stack.pop()+")"
      #print(ans)
    else:
      ans = "(" + ans + ")"
      #print(ans)
nokori=len(stack)
ans += nokori * "(" + nokori * ")"

print(ans)

Submission status: Wrong Answer

Solution code:
def solve():
    N = int(input())
    S = input()
    l,r = 0,0
    state = 'r'
    for i in range(N):
        if i == 0 and S[i] == ')': state = 'l'
        if i > 0 and S[i-1] == ')' and S[i] == '(':
            state = 'r' if state == 'l' else 'l'
            
        if S[i] == '(':
            if state == 'l':
                if l > 0:
                    l -= 1
                else:
                    r += 1
            elif state == 'r':
                r += 1
        elif S[i] == ')':
            if state == 'r':
                if r > 0:
                    r -= 1
                else:
                    l += 1
            elif state == 'l':
                l += 1
                
        # print(state,l,r)
            
    print('('*l+S+')'*r)
    
solve()

Submission status: Wrong Answer

Solution code:
N=int(input())
S=input()
L_l=[-1]*(N+1)
L_r=[-1]*(N+1)
R_l=[-1]*(N+1)
R_r=[-1]*(N+1)
n=0

while True:
  for i in range(N+1):
    L_l[i]=S[:i].count("(")
    L_r[i]=S[:i].count(")")
    R_l[i]=S[i:].count("(")
    R_r[i]=S[i:].count(")")
    if R_r[i]+L_r[i]>R_l[i]+L_l[i]:
      S = S[:i] +"(" +S[i:]
      #print(S)
      break
    if R_r[i]+L_r[i]<R_l[i]+L_l[i]:
      S = S[:i] +")" +S[i:]
      #print(S)
      break
  else:
    break

#print(L_l)
#print(L_r)
#print(R_l)
#print(R_r)
print(S)

Submission status: Wrong Answer

Solution code:
N = int(input())
S = input()
total,min_total = 0, 1
for s in S:
    total += 1 if s == '(' else -1
    if total < min_total:
        min_total = total    
print('('*-min_total+S+')'*(total-min_total) if min_total<0 else S+')'*min_total)

Submission status: Wrong Answer

Solution code:
N = int(input())
S = input()
total,min_total = 0, 1
for s in S:
    total += 1 if s == '(' else -1
    if total < min_total:
        min_total = total    
print('('*-min_total+S+')'*(total-min_total))

Submission status: Wrong Answer

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

def main():
    N = int(readline())
    S = readline().rstrip()
    res = S[:]

    if '(' in S:
        idx = S.index('(')
        cnt = 1
        for s in S[idx+1:]:
            if s == '(':
                cnt += 1
            else:
                cnt -= 1
        res += ')' * max(cnt, 0)
    
    S = res[::-1]
    idx = S.index(')')
    cnt = 1
    for s in S[idx+1:]:
        if s == ')':
            cnt += 1
        else:
            cnt -= 1
    res = '(' * max(cnt, 0) + res

    print(res)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

def main():
    N = int(readline())
    S = readline().rstrip()
    res = ''
    cnt = 0
    for s in S[::-1]:
        if s == ')':
            res += ')'
            cnt += 1
        else:
            if cnt > 0:
                res += '('
                cnt -= 1
            else:
                res += ')('

    res += '(' * max(cnt, 0)
    print(res[::-1])

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

def main():
    N = int(readline())
    S = readline().rstrip()
    res = ''
    cnt = 0
    for s in S[::-1]:
        if s == ')':
            res += ')'
            cnt += 1
        else:
            if cnt:
                res += '('
                cnt -= 1
            else:
                res += ')('

    res += '(' * max(cnt, 0)
    print(res[::-1])

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

result=""
cnt=0

#(を追加する
for ss in s:
    if ss ==")":
        if cnt>0:
            result+=ss
            cnt-=1
        else:
            result="("+result+ss
    else:
        result+=ss
        cnt+1

L=result.count("(")
R=result.count(")")

result+=")"*(L-R)

print(result)

Submission status: Wrong Answer

Solution code:
N = int(input())
S = input()
l = S.count("(")
r = S.count(")")
ans = "("*max(r-l, 0) + S + ")"*max(l-r, 0)
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
N = int(input())
S = input()
SS = [1 if S[i]=='(' else -1 for i in range(N)]
SSS = list(accumulate(SS))
m = max(0,-min(SSS))
M = max(SSS)
print('('*m+S+')'*(M+m))

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
N = int(input())
S = input()
SS = [1 if S[i]=='(' else -1 for i in range(N)]
SSS = list(accumulate(SS))
m = -min(SSS)
print('('*m+S+')'*(SSS[-1]+m))

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
N = int(input())
S = input()
SS = [1 if S[i]=='(' else -1 for i in range(N)]
SSS = list(accumulate(SS))
m = -min(SSS)
M = max(SSS)

print('('*m+S+')'*(M-m))

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
N = int(input())
S = input()
SS = [1 if S[i]=='(' else -1 for i in range(N)]
SSS = list(accumulate(SS))
m = -min(SSS)

print('('*m+S+')'*(m+SSS[-1]))

Submission status: Wrong Answer

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

print('('*max(0,r-l)+S+')'*max(0,l-r))

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    s = list(input())
    from collections import deque
    q=deque()
    buf = ''
    cnt = 0
    for i in s:
        if cnt == 0:
            buf = i
            cnt += 1
        elif i == buf:
            cnt += 1
        else:
            q.append('('*cnt)
            q.append(')'*cnt)
            cnt = 0
            buf = ''
    q.append('('*cnt)
    q.append(')'*cnt)
    print(*list(q), sep='')


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    s = list(input())
    from collections import deque
    q=deque()
    buf = ''
    cnt = 0
    for i in s[::-1]:
        if cnt == 0:
            buf = i
            cnt += 1
        elif i == buf:
            cnt += 1
        else:
            q.appendleft(')'*cnt)
            q.appendleft('('*cnt)
            cnt = 0
            buf = ''
    q.appendleft(')'*cnt)
    q.appendleft('('*cnt)
    print(*list(q), sep='')


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:


n = int(input())

s = input()

now =0
right = 0
for i in range(n):
    if(s[n-1-i]=='('):
        now+=1
    else:
        now-=1
    if(right<now):
        right=now
left=0
for i in range(n):
    if(s[i]=='('):
        now-=1
    else:
        now+=1
    if(left<now):
        left=now

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

Submission status: Wrong Answer

Solution code:
import collections
n = int(input())
t = input()
s = list(t)

c = collections.Counter(s)
if c[")"] > c["("]:
    for i in range(c[")"]-c["("]):
        print("(",end="")
    print(t)
elif c["("] > c[")"]:
    print(t,end="")
    for i in range(c["("]-c[")"]):
        print(")",end="")
else:
    print(t)

Submission status: Wrong Answer

Solution code:
n = int(input())
s = input()
s_ = s.replace('()', '')
x = s_.count('(')
y = s_.count(')')
print('('*y+s+')'*x)

Submission status: Wrong Answer

Solution code:
n = int(input())
s = input()
s = list(s.replace(')(', ') (').split())
ans = ''
for c in s:
    x = c.count('(')
    y = c.count(')')
    ans += '('*max(x,y) + ')'*max(x,y)
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
s = input()
d = 0
x = n
for si in s:
    if si == "(":
        d += 1
    else:
        d -= 1
    x = min(d, x)
print("(" * -x + s + ")" * (d - x))

Submission status: Wrong Answer

Solution code:
def main():
    input()
    s = input()
    l, r = 0, 0
    for si in s[::-1]:
        if si == ")":
            break
        r += 1
    for si in s[:-r] if r > 0 else s:
        if si == ")":
            l += 1
        else:
            l -= 1
    print("(" * l + s + ")" * r)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from fractions import gcd
from math import factorial, sqrt, ceil
from functools import lru_cache, reduce
INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)

# UnionFind
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# ワーシャルフロイド (任意の2頂点の対に対して最短経路を求める)
# 計算量n^3 (nは頂点の数)
def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d


# ダイクストラ
def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

# 素因数分解
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# 2数の最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# リストの要素の最小公倍数
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

# リストの要素の最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)

# 素数判定
def is_prime(n):
    if n <= 1:
        return False
    p = 2
    while True:
        if p ** 2 > n:
            break
        if n % p == 0:
            return False
        p += 1
    return True


# limit以下の素数を列挙
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P

# 同じものを含む順列
def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        # set（集合）型で重複を削除、ソート
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret


# ここから書き始める
n = int(input())
s = input()
left = 0 # 左に付け足す「(」の数
cnt1 = 0 # 左から見ていったときの「(」の数
cnt2 = 0 # 右から見ていった時の「)」の数
for i in range(n):
    if i != 0 and s[i] == "(" and s[i - 1] == ")":
        left += max(0, cnt2 - cnt1)
        cnt2 = 0
        cnt1 = 1
    elif s[i] == "(":
        cnt1 += 1
    else:
        cnt2 += 1
left += max(0, cnt2 - cnt1)
s = left * "(" + s
right = 0 # 右に付け足す「)」の数
cnt3 = 0 # 左から見ていったときの「)」の数
cnt4 = 0 # 右から見ていった時の「(」の数
for i in reversed(range(n + left)):
    if i != n + left - 1 and s[i] == ")" and s[i + 1] == "(":
        right = max(0, cnt4 - cnt3)
        cnt4 = 0
        cnt3 += 1
    elif s[i] == ")":
        cnt3 += 1
    else:
        cnt4 += 1
right += max(0, cnt4 - cnt3)
ans = s + ")" * right
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from fractions import gcd
from math import factorial, sqrt, ceil
from functools import lru_cache, reduce
INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)

# UnionFind
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# ワーシャルフロイド (任意の2頂点の対に対して最短経路を求める)
# 計算量n^3 (nは頂点の数)
def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d


# ダイクストラ
def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

# 素因数分解
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# 2数の最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# リストの要素の最小公倍数
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

# リストの要素の最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)

# 素数判定
def is_prime(n):
    if n <= 1:
        return False
    p = 2
    while True:
        if p ** 2 > n:
            break
        if n % p == 0:
            return False
        p += 1
    return True


# limit以下の素数を列挙
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P

# 同じものを含む順列
def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        # set（集合）型で重複を削除、ソート
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret


# ここから書き始める
n = int(input())
s = input()
left = 0 # 左に付け足す「(」の数
cnt1 = 0 # 左から見ていったときの「(」の数
cnt2 = 0 # 右から見ていった時の「)」の数
for i in range(n):
    if i != 0 and s[i] == "(" and s[i - 1] == ")":
        left += max(0, cnt2 - cnt1)
        cnt2 = 0
        cnt1 = 1
    elif s[i] == "(":
        cnt1 += 1
    else:
        cnt2 += 1
left += max(0, cnt2 - cnt1)
right = 0 # 右に付け足す「)」の数
cnt3 = 0 # 左から見ていったときの「)」の数
cnt4 = 0 # 右から見ていった時の「(」の数
for i in reversed(range(n)):
    if i != n - 1 and s[i] == ")" and s[i + 1] == "(":
        right = max(0, cnt4 - cnt3)
        cnt4 = 0
        cnt3 += 1
    elif s[i] == ")":
        cnt3 += 1
    else:
        cnt4 += 1
right += max(0, cnt4 - cnt3)
ans = "(" * left + s + ")" * right
print(ans)

Submission status: Wrong Answer

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

d = [0] * (N + 1)
for i in range(N):
    d[i + 1] = d[i] + int(S[i] == "(") - int(S[i] == ")")

a = d[-1]
b = min(d)

print("(" * -a + S + ")" * (b - a))

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    N = int(input())
    S = input().replace(")(", ") (").split()
    cnt = 0
    ans = ""
    for s in S:
        left = 0
        right = 0
        for i in range(len(s)):
            if s[i] == "(":
                left += 1
            else:
                right += 1

        if left < right:
            cnt += right - left
            ans += "(" * left + ")" * right
        else:
            ans += "(" * left + ")" * left

    ans = cnt * "(" + ans
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
si = input()
s = list(si)[::-1]
ln = 0
rn = 0
l = ""
r = ""
for i in range(n):
    if s[i] == ')':
        ln += 1
        rn -= 1
    else:
        rn += 1
    
    if ln == 0 and rn > 0:
        l += ")"
        rn -= 1

r = "(" * (rn*-1)
print(r + si + l)

Submission status: Wrong Answer

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

f = s[0]
l = [1] if f == "(" else [0, 1]
for i in range(1, n):
    if s[i] == f:
        l[len(l)-1] += 1
    else:
        l.append(1)
        f = s[i]

if len(l) % 2 == 1:
    l.append(0)

for i in range(len(l) // 2):
    m = max(l[2 * i], l[2 * i + 1])
    l[2*i], l[2*i+1] = m, m

ans = ""
f = 0
for i in l:
    ans += ["(", ")"][f] * i
    f ^= 1

print(ans)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    N = int(input())
    S = input().replace(")(", ") (").split()
    left = ""
    right = ""
    for s in S:
        i = s.count("(")
        j = s.count(")")
        if i >= j:
            left += "(" * i + ")" * j
            right = ")" * (i - j) + right
        else:
            left += "(" * i + ")" * j
            left = "(" * (j - i) + left

    ans = left + right
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    N = int(input())
    S = input().replace(")(", ") (").split()
    left = ""
    right = ""
    for s in S:
        i = s.count("(")
        j = s.count(")")
        if i >= j:
            left += "(" * i + ")" * j
            right += ")" * (i - j)
        else:
            left += "(" * i + ")" * j
            left = "(" * (j - i) + left

    ans = left + right
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    N = int(input())
    S = input().replace(")(", ") (").split()
    left = ""
    right = ""
    for s in S:
        i = s.count("(")
        j = s.count(")")
        if i >= j:
            left += "(" * i + ")" * j
            right = right + ")" * (i - j)
        else:
            left += "(" * i + ")" * j
            left = "(" * (j - i) + left

    ans = left + right
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque
n=int(input())
s=deque(list(input()))
a=[]
b=[]
x=[]
while len(s)>0 :
    c=s.popleft()
    if c=='(':
        a.append(c)
    elif len(a)>0:
        b.append('()')
        a.pop()
    else:
        b.append(c)
        x.append('(')
print(''.join(x)+''.join(b)+''.join(a)+')'*len(a))

Submission status: Wrong Answer

Solution code:
N = int(input())
S = input()
from collections import deque
q = deque([])

l = []
cnt = 0
for i in range(N-1):
    if S[i] == '(':
        cnt += 1
        if S[i+1] == ')':
            l.append(['a', cnt])
            cnt = 0
        elif S[i+1] == '(' and i+1 == N-1:
            l.append(['a', cnt+1])
            cnt = 0
    elif S[i] == ')':
        cnt += 1
        if S[i+1] == '(':
            l.append(['b', cnt])
            cnt = 0
        elif S[i+1] == ')' and i+1 == N-1:
            l.append(['b', cnt+1])
            cnt = 0

a = 0
b = 0
for i in range(len(l)):
    k, c = l[i]
    if k == 'a':
        q.append('('*c)
        a += c
    if k == 'b':
        q.append(')'*c)
        b += c
        if a < b:
            q.appendleft('('*(b-a))
            a += (b-a)
if a > b:
    q.append(')'*(a-b))

print(*q, sep='')

Submission status: Wrong Answer

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

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
list = list(input())
check = [False] * len(list)

i = 0
while(i):
    if list[i] == ')' and i > 0 and list[i-1] == "(":
        check[i] = True
        check[i - 1] = True

    i += 1
    if len(list) <= i: break

count = {
    '(': 0,
    ')': 0
}

for b, v in zip(check, list):
    if not b:
        count[v] += 1

print("(" * count[')'] + "".join(list) + ")" * count["("])

Submission status: Wrong Answer

Solution code:
N=int(input())
A=input()
def check_l(A):
    for i in range(1,len(A)+1):
        if not i==len(A):
            if A[-i]=="(":
                pass
            else:
                return i
                break
        elif i==len(A):
            if A[-i]=="(":
                return 0
            else:
                return i
                break
def check_t(A):
    for i in range(0,len(A)):
        if not i==len(A)-1:
            if A[i]==")":
                pass
            else:
                return i
                break
        elif i==len(A)-1:
            if A[i]==")":
                a=len(A)
                return a
            else:
                return i
def all(A,C):

    if check_l(A)==0:
        for i in range(N):
            A=A+")"
            C=C+")"
    elif not check_l(A)==0:
        for i in range(check_l(A)-1):
            A=A+")"
            C=C+")"

    if check_t==len(A):
        for i in range(N):
            A="("+A
            C="("+C
    else:
        for i in range(check_t(A)):
            A="("+A
            C="("+C

    for i in range(len(A)):
        if "()" in A:
            A=A.replace("()","")
        else:
            break
    return [A,C]

X=[A,A]

for i in range(N):
    if X[0]=="":
        print(X[1])
        break
    else:
        X=all(X[0],X[1])

Submission status: Wrong Answer

Solution code:
N=int(input())
A=input()
def check_l(A):
    for i in range(1,len(A)+1):
        if not i==len(A):
            if A[-i]=="(":
                pass
            else:
                return i
        elif i==len(A):
            if A[-i]=="(":
                return 0
            else:
                return i
def check_t(A):
    for i in range(0,len(A)):
        if not i==len(A)-1:
            if A[i]==")":
                pass
            else:
                return i
        elif i==len(A)-1:
            if A[i]==")":
                a=len(A)
                return a
            else:
                return i
def all(A,C):
    if check_l(A)==0:
        for i in range(N):
            A=A+")"
    elif not check_l(A)==0:
        for i in range(check_l(A)-1):
            A=A+")"
            C=C+")"

    if check_t==len(A):
        for i in range(N):
            A="("+A
    else:
        for i in range(check_t(A)):
            A="("+A
            C="("+C

    for i in range(len(A)):
        if "()" in A:
            A=A.replace("()","")
        else:
            break
    return [A,C]

X=[A,A]

for i in range(N):
    if X[0]=="":
        print(X[1])
        break
    else:
        [X[0],X[1]]=all(X[0],X[1])

Submission status: Wrong Answer

Solution code:
N=int(input())
A=input()
def check_l(A):
    for i in range(1,len(A)+1):
        if not i==len(A):
            if A[-i]=="(":
                pass
            else:
                return i
        elif i==len(A):
            if A[-i]=="(":
                return 0
            else:
                return i
def check_t(A):
    for i in range(0,len(A)):
        if not i==len(A)-1:
            if A[i]==")":
                pass
            else:
                return i
        elif i==len(A)-1:
            if A[i]==")":
                a=len(A)
                return a
            else:
                return i
def all(A,C):
    if check_l(A)==0:
        for i in range(N):
            A=A+")"
        print(A)
        exit()
    elif not check_l(A)==0:
        for i in range(check_l(A)-1):
            A=A+")"
            C=C+")"

    if check_t==len(A):
        for i in range(N):
            A="("+A
        print(A)
        exit()
    else:
        for i in range(check_t(A)):
            A="("+A
            C="("+C

    for i in range(len(A)):
        if "()" in A:
            A=A.replace("()","")
        else:
            break
    return [A,C]

X=[A,A]

for i in range(N):
    if X[0]=="":
        print(X[1])
        break
    else:
        [X[0],X[1]]=all(X[0],X[1])

Submission status: Wrong Answer

Solution code:
n=int(input())
s=[str(x) for x in input()]
t=[]
start=0
for i in range(n-1):
    if s[i]==')' and s[i+1]=='(':
        t.append(s[start:i+1])
        start=i+1
t.append(s[start:n])

ans=[]
plus=0
minus=0
for i in range(len(t)):
    sub=t[i].count(')')-t[i].count('(')
    if sub>0:
        plus += sub
    elif sub<0:
        minus += -sub
    ans += [x for x in t[i]]
for i in range(plus):
    ans.insert(0,'(')
for i in range(minus):
    ans.insert(len(ans),')')
print(''.join(ans))

Submission status: Wrong Answer

Solution code:
n = int(input())
s = str(input())
t = []
for i in range(n):
    t.append(s[i])
r = t
blocked = 0
sop = n-1
scl = 0
while scl < sop:
    while(1):
        if sop < scl or s[sop] == ")":
            break
        else:
            sop -= 1
    while(1):
        if sop < scl or s[scl] == "(":
            break
        else:
            scl += 1
    if scl < sop:
        sop -= 1
        scl += 1
        blocked += 1
print("("*(t.count(")")-blocked),end="")
print("".join(t),end="")
print(")"*(t.count("(")-blocked))

Submission status: Wrong Answer

Solution code:
n = int(input())
s = str(input())
t = []
for i in range(n):
    t.append(s[i])
r = t
blocked = 0
sop = n-1
scl = 0
while scl <= sop:
    while(1):
        if sop < scl or s[sop] == ")":
            break
        else:
            sop -= 1
    while(1):
        if sop < scl or s[scl] == "(":
            break
        else:
            scl += 1
    if scl < sop:
        sop -= 1
        scl += 1
        blocked += 1
print("("*(t.count(")")-blocked),end="")
print("".join(t),end="")
print(")"*(t.count("(")-blocked))

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(input())
    s = input()

    R = s.count(")")
    L = s.count("(")
    cnt_R = 0
    cnt_L = 0
    for i in range(n):
        if cnt_R == R:
            break

        if s[i] == ")":
            cnt_R += 1
        else:
            cnt_L += 1

    insert_L = max(0, R - cnt_L)

    cnt_R = 0
    cnt_L = 0
    for i in reversed(range(n)):
        if cnt_L == L:
            break

        if s[i] == ")":
            cnt_R += 1
        else:
            cnt_L += 1

    insert_R = max(0, L - cnt_R)

    res = "(" * insert_L + s + ")" * insert_R
    print(res)


if __name__ == '__main__':
    resolve()