Problem:


Score : 600 points

Problem Statement

A bracket sequence is a string that is one of the following:

An empty string;

The concatenation of (, A, and ) in this order, for some bracket sequence A ;

The concatenation of A and B in this order, for some non-empty bracket sequences A and B /

Given are N strings S_i. Can a bracket sequence be formed by concatenating all the N strings in some order?

Constraints

1 \leq N \leq 10^6

The total length of the strings S_i is at most 10^6.

S_i is a non-empty string consisting of ( and ).

Input

Input is given from Standard Input in the following format:

N
S_1
:
S_N

Output

If a bracket sequence can be formed by concatenating all the N strings in some order, print Yes; otherwise, print No.

Sample Input 1

2
)
(()

Sample Output 1

Yes

Concatenating (() and ) in this order forms a bracket sequence.

Sample Input 2

2
)(
()

Sample Output 2

No

Sample Input 3

4
((()))
((((((
))))))
()()()

Sample Output 3

Yes

Sample Input 4

3
(((
)
)

Sample Output 4

No



Sample input:
2
)
(()


Sample output:
Yes

Submission status: Wrong Answer

Solution code:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()
N=int(input())
S=[input() for i in range(N)]
llst=[]
lr=[]
rlst=[]
for n in range(N):
    l=0
    r=0
    for i in range(len(S[n])):
        if S[n][i]=="(":
            l+=1
        else:
            if l>0:
                l-=1
            else:
                r+=1
    #print(l,r)
    if l and not r:
        llst.append(l)
    elif not l and r:
        rlst.append(r)
    elif l or r:
        lr.append([l,r])
llst=sum(llst)
rlst=sum(rlst)

if not llst and not rlst and not lr:
    print("Yes")
    exit()
stack=[]
idleR=10**7
if lr:
    L,R=lr[0]
    stack=[[L,R]]
    for n in range(1,len(lr)):
        #print(stack)
        L,R=lr[n]
        visited=set()
        nstack=[]
        while stack:
            l,r=stack.pop()
            for xl,xr in [[l+L-R,r],[l,r+R-L]]:
                if xl>=0 and xr>=0:
                    X=xl+idleR*xr
                    if not X in visited:
                        visited.add(X)
                        nstack.append([xl,xr])
if not stack:
    if llst-rlst==0:
        print("Yes")
    else:
        print("No")
    exit()

for l,r in stack:
    break
    if l<=rlst:

        L=rlst-l
        l=0
    else:
        continue
    if r<=llst:

        R=llst-r
        r=0
    else:
        continue

    if L-R==0:
        print("Yes")
        exit()
    else:
        continue
print("No")

Submission status: Wrong Answer

Solution code:
#!python3

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

# input
N = int(input())
S = [input() for _ in range(N)]


def main():
    pl, ml = [], []
    for i in range(N):
        l = 0
        b = 0
        for s in S[i]:
            if s == "(":
                l += 1
            else:
                l -= 1
                b = min(b, l)
        if l > 0:
            pl.append((b, l))
        else:
            ml.append((l, b))
    pl = sorted(pl)[::-1]
    ml = sorted(ml)[::-1]

    x = 0
    for b, l in pl:
        if x + b < 0:
            print("No")
            return
        x += l
    for l, b in ml:
        if x + b < 0:
            print("No")
            return
        x += l
    if x == 0:
        print("Yes")
    else:
        print("No")


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import heapq
import sys

#input = sys.stdin.readline

def main():
    N = int(input())

    data = [0]*N
    for i in range(N):
        S = list(str(input()))
        s = 0
        m = 0
        for j in range(len(S)):
            if S[j] == "(":
                s += 1
            else:
                s -= 1
                m = min(m,s)
        data[i] = (-m,-s)


    heapq.heapify(data)
    x = 0
    valid = []
    heapq.heapify(valid)

    det = 0

###
#print("data",data)
#print("valid",valid)
#print(x)
###

    while data or valid:
        while data and x - data[0][0] >= 0:
            y = heapq.heappop(data)
            heapq.heappush(valid,(y[1],y[0]))
    
        while valid and x >= 0:
            z = heapq.heappop(valid)
            if x - z[0] >= 0:
                x -= z[0]
            else:
                heapq.heappush(valid,z)
    
        if data and x - data[0][0] < 0:
            det = -1
            break

    if det == 0 and x == 0:
        print("Yes")
    else:
        print("No")

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#from collections import defaultdict, deque
#import itertools
#import numpy as np
#import re

def main():
    N = int(input())
    SS = []
    for _ in range(N):
        SS.append(input())
    S = []
    for s in SS:
        while '()' in s:
            s = s.replace('()', '')
        S.append(s)
    #print(S)
    S = [s for s in S if s != '']
    S_op = []
    S_cl = []
    S_both = []
    for s in S:
        if not ')' in s:
            S_op.append(len(s))
        elif not '(' in s:
            S_cl.append(len(s))
        else:
            pos = s.find('(')
            S_both.append((pos, len(s)-pos))

    print('Yes')


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()
N=int(input())
S=[input() for i in range(N)]
llst=[]
lr=[]
rlst=[]
for n in range(N):
    l=0
    r=0
    for i in range(len(S[n])):
        if S[n][i]=="(":
            l+=1
        else:
            if l>0:
                l-=1
            else:
                r+=1
    #print(l,r)
    if l and not r:
        llst.append(l)
    elif not l and r:
        rlst.append(r)
    elif l or r:
        lr.append([l,r])
llst=sum(llst)
rlst=sum(rlst)

if not llst and not rlst and not lr:
    print("Yes")
    exit()
stack=[]
idleR=10**7
if lr:
    L,R=lr[0]
    stack=[[L,R]]
    for n in range(1,len(lr)):
        #print(stack)
        L,R=lr[n]
        visited=set()
        nstack=[]
        while stack:
            l,r=stack.pop()
            for xl,xr in [[l+L-R,r],[l,r+R-L]]:
                if xl>=0 and xr>=0:
                    X=xl+idleR*xr
                    if not X in visited:
                        visited.add(X)
                        nstack.append([xl,xr])
if not stack:
    if llst-rlst==0:
        print("Yes")
    else:
        print("No")
    exit()

for l,r in stack:
    if l<=rlst:

        L=rlst-l
        l=0
    else:
        continue
    if r<=llst:

        R=llst-r
        r=0
    else:
        continue

    if L-R==0:
        print("Yes")
        exit()
    else:
        continue
print("No")

Submission status: Wrong Answer

Solution code:
n = int(input())
cnt_list = [0,0]*n
l_zero = []
r_zero = []
allsum = 0

for i in range(n):
    ss = input()
    l = len(ss)
    right = 0
    left=0
    for j in range(l):
        if ss[j]=='(': left+=1
        elif left>0: left-=1
        else: right+=1
    cnt_list = [left,right]
    if left==0: l_zero.append(i)
    if right==0: r_zero.append(i)
    allsum += left-right


if l_zero ==[] or r_zero==[]:
    print('No')
    exit()
if len(l_zero)==1 and len(l_zero)==1 and l_zero[0]==r_zero[0]:
    print('No')
    exit()

if allsum==0:
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    a = [input() for i in range(n)]
    s = []
    for i in range(n):
        p = 0
        m = 0
        for j in a[i]:
            if j == "(":
                p += 1
            else:
                p -= 1
            if p < m:
                m = p
        s.append((m,p))
    s.sort(reverse = True)
    q = []
    k = 0
    i = 0
    while q or (i < n):
        while i < n and s[i][0]+k >= 0:
            heappush(q,-s[i][1])
            i += 1
        if not q:
            print("No")
            return
        k -= heappop(q)
        if k < 0:
            print("No")
            return
    if q or k != 0 or i < n:
        print("No")
    else:
        print("Yes")
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
n = int(input())
sco = [] #高低差,min値
ssum = 0

for i in range(n):
    s = input()
    sa = 0
    ms = 0
    for i in range(len(s)):
        if s[i] == "(":
            sa += 1
        else:
            sa -= 1
        if ms > sa:
            ms = sa
    sco.append([ms,sa])
    ssum += sa

if not ssum == 0:
    print("No")
    exit()

sco.sort(reverse = True)
now = 0
for i in range(n):
    if sco[i][0] + now < 0:
        print("No")
        exit()
    elif now + sco[i][1] < 0:
        print("No")
        exit()
    else:
        now += sco[i][1]

print("Yes")

Submission status: Wrong Answer

Solution code:
import sys

N = int(input())

S = []
for i in range(N):
    s = input()
    r, m = 0, 0
    for c in s:
        r += 1 if c == '(' else -1
        m = min(m, r)
    S.append((-m, r-m))

S.sort()


if S[0][0] > 0:
    print("No")
    sys.exit()

if S[-1][1] > 0:
    print("No")
    sys.exit()

x = 0
for s in S:
    x -= s[0]
    if x < 0:
        print("No")
        sys.exit()
    
    x += s[1]

if x == 0:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    a = [input() for i in range(n)]
    s = []
    for i in range(n):
        p = 0
        m = 0
        for j in a[i]:
            if j == "(":
                p += 1
            else:
                p -= 1
            if p < m:
                m = p
        s.append((m,p))
    if sum([p for (m,p) in s]) != 0:
        print("No")
        return
    s.sort(reverse = True)
    q = []
    k = 0
    i = 0
    while q or (i < n):
        while i < n and s[i][0]+k >= 0:
            heappush(q,-s[i][1])
            i += 1
        if not q:
            print("No")
            return
        k -= heappop(q)
    if q or i < n:
        print("No")
    else:
        print("Yes")
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
#!python3

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

# input
N = int(input())
S = [input() for _ in range(N)]


def main():
    pl, ml = [], []
    for i in range(N):
        l = 0
        b = 0
        for s in S[i]:
            if s == "(":
                l += 1
            else:
                l -= 1
                b = min(b, l)
        if l > 0:
            pl.append((b, l))
        else:
            ml.append((l, b))
    pl = sorted(pl)[::-1]
    ml.sort()

    x = 0
    for b, l in pl:
        if x + b < 0:
            print("No")
            return
        x += l
    for l, b in ml:
        if x + b < 0:
            print("No")
            return
        x += l
    if x == 0:
        print("Yes")
    else:
        print("No")


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    S = [input() for _ in [0]*n]
    s2 = []
    s3 = []
    for s in S:
        temp = [0, 0]
        m = 0
        now = 0
        for i in s:
            if i == "(":
                now += 1
            else:
                now -= 1
            m = min(m, now)
        temp[0] = m
        temp[1] = (s.count("(")-s.count(")"))
        if temp[1] >= 0:
            s2.append(temp)
        else:
            s3.append(temp)
    s2.sort(key=lambda x: (-x[0]))
    s3.sort(key=lambda x: (x[1]))
    cnt = 0
    # print(s2)
    # print(s3)
    for i, j in s2:
        if cnt+i < 0:
            print("No")
            return
        cnt += j
    for i, j in s3:
        if cnt+i < 0:
            print("No")
            return
        cnt += j
    if cnt != 0:
        print("No")
        return
    print("Yes")


main()

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    S = [input() for _ in range(N)]
    work = []
    for s in S:
        temp = [0, 0]
        flag = None
        state = False
        hoge = 0
        for c in s:
            if c == "(":
                if state:
                    state = False
                    if hoge > 0:
                        temp[0] += hoge
                    else:
                        temp[1] += hoge
                    hoge = 0
                flag = True
                hoge += 1
            else:
                if flag == True:
                    flag = False
                    state = True
                    hoge -= 1
                else:
                    flag = False
                    if state:
                        hoge -= 1
                    else:
                        temp[1] += 1
        temp[0] += hoge
        work.append(temp)
    a, b = 0, 0
    for l, r in work:
        a += l
        b += r
        if l == 0 and r == 0:
            N -= 1
    if a != 0 and b != 0 and N < 3:
        print("No")
    elif a == b and N > 1:
        print("Yes")
    else:
        print("No")
main()

Submission status: Wrong Answer

Solution code:
N=int(input())
l = '('
r = ')'
S = {l:0,r:0}
for _ in range(N):
  s = {l:0,r:0}
  for v in input():
    if v == r:
      if s[l]>0:s[l]-=1
      else: s[r]+=1
    else:
      s[l]+=1
  if min(S[l],s[r]) > min(S[r],s[l]):
    if S[l] >= s[r]:
      S[l]-=s[r]
      S[l]+=s[l]
    else:
      s[r] -= S[l]
      S[r] += s[r]
      S[l] = s[l]
  else:
    if S[r] >= s[l]:
      S[r] -= s[l]
      S[r] += s[r]
    else:
      s[l] -= S[r]
      S[l] += s[l]
      S[r] = s[r]
#print(S)
if S[r]==0 and S[l] == 0:
  print('Yes')
else:
  print('No')

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    a = [input() for i in range(n)]
    s = []
    for i in range(n):
        p = 0
        m = 0
        for j in a[i]:
            if j == "(":
                p += 1
            else:
                p -= 1
            if p < m:
                m = p
        s.append((m,p))
    s.sort(reverse = True)
    q = []
    k = 0
    i = 0
    while q or (i < n):
        while i < n and s[i][0]+k >= 0:
            heappush(q,-s[i][1])
            i += 1
        if not q:
            print("No")
            return
        k -= heappop(q)
    if k != 0 or i < n:
        print("No")
    else:
        print("Yes")
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
n = int(input())
start = 0
end = 0
left = 0
double = []
right = 0
for i in range(n):
    s = str(input())
    kienaileft = 0
    kienairight = 0
    for j in range(len(s)):
        if s[j] == ")":
            kienaileft += 1
        else:
            break
    for j in range(len(s)):
        if s[-(j+1)] == "(":
            kienairight += 1
        else:
            break
    nowleft = 0
    nowright = 0
    for j in range(kienaileft,len(s)-kienairight):
        if s[j] == ")":
            nowleft += 1
        else:
            nowright += 1
    num = min(nowleft,nowright)
    kienaileft += nowleft -num
    kienairight += nowright -num
    if kienaileft != 0:
        if kienairight != 0:
            double.append([kienaileft,kienairight])
        else:
            left += kienaileft
    else:
        if kienairight != 0:
            right += kienairight
  # print(left,double,right)
if left + sum([double[i][0] for i in range(len(double))]) != sum([double[i][1] for i in range(len(double))]) + right:
    print("No")
    exit()
if len(double) != 0:
    if not left or not right:
        print("No")
        exit()
else:
    if left == right:
        print("Yes")
        exit()
double.sort(reverse=True)
now = left

for b,a in double:
    if now < a:
        print("No")
        exit()
    now += (b-a)
print("Yes")

Submission status: Wrong Answer

Solution code:
N = int(input())

S = [input() for _ in range(N)]
for i in range(N):
    while S[i] != S[i].replace("()",""):
        S[i] = S[i].replace("()","")
ls = [[0,0] for _ in range(N)]
for i in range(N):
    for s in S[i]:
        if s == "(":
            ls[i][0] += 1
        if s == ")":
            ls[i][1] += 1

ls.sort(key=lambda x: x[0],reverse=True)
ls.sort(key=lambda x: x[1])
if ls[0][1] > 0 or ls[-1][0] > 0:
    print('No')
    exit()
else:
    sum = 0
    for i in range(len(ls)-1):
        sum += ls[i][0]-ls[i+1][1]
        if sum < 0:
            print('No')
            exit()
    if sum == 0:
        print("Yes")
    else:
        print("No")

Submission status: Wrong Answer

Solution code:
# coding: utf-8
N=int(input())
S=[]
for i in range(N):
    S.append(list(input()))
nL=0
nR=0
SLR=[]

for i in range(N):
    s=S[i]
    l=0
    r=0
    for j in range(len(s)):
        if s[j]==")":
            nL+=1
            if r==0:
                l+=1
            else:
                r-=1
        else:
            nR+=1
            r+=1
    SLR.append([l,r])

RR=0
LL=0
L=0
R=0

for i in range(N):
    if SLR[i][0]==0:
        RR+=SLR[i][1]
    elif SLR[i][1]==0:
        LL+=SLR[i][0]
    else:
        L1=L+max(0,SLR[i][0]-R)
        R1=max(0,R-SLR[i][0])+SLR[i][1]
        L2=SLR[i][0]+max(0,L-SLR[i][1])
        R2=R+max(0,SLR[i][1]-L)
        
        if L1+R1<=L2+R2:
            L=L1
            R=R1
        else:
            L=L2
            R=R2

if nR==nL and RR>=L and LL>R:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
from bisect import bisect
N = int(input())
S = [input() for _ in range(N)]

def count(s):
    n = len(s)
    n1 = 0
    n2 = 0
    for i in range(n):
        if s[i]=='(':
            n2 += 1
        else:
            if n2 > 0:
                n2 -= 1
            else:
                n1 += 1
    return n1,n2

l = []
for i in range(N):
    n1,n2 = count(S[i])
    if n1+n2!=0:
        l.append([n1,n2])

l.sort(key=lambda x:x[1]-x[0])
l.sort(key=lambda x:x[0])

N = len(l)
N0 = 2**(N-1).bit_length()
INF = 2**31-1
data = [[INF,INF]]*(4*N0)

def update(k, x):
    k += N0-1
    data[k] = x
    while k >= 0:
        k = (k - 1) // 2
        data[k] = min(data[2*k+1], data[2*k+2])


def query(l, r):
    L = l + N0; R = r + N0
    s = [INF,INF]
    while L < R:
        if R & 1:
            R -= 1
            s = min(s, data[R-1])

        if L & 1:
            s = min(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s

for i in range(N):    
    a,b = l[i]
    l[i] = a
    update(i, [a-b,i])

ans = True
n = 0
for i in range(N):
    i = bisect(l,n)-1
    c,i = query(0,i+1)
    if c == INF:
        ans = False
        break
    a = l[i]
    if n < a:
        ans = False
        break
    update(i,[INF,i])
    n -= c
if n!=0:
    ans = False
if ans:
    ans = 'Yes'
else:
    ans = 'No'
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
S = [input() for _ in range(N)]

def calc(T):
    now = 0
    ret = 0
    for s in T:
        if s == '(':
            now += 1
        elif s == ')':
            now -= 1
        ret = min(ret, now)
    return ret

H = []
P = []
L = []

for s in S:
    less = -calc(s)
    if less == 0:
        H.append(s)
    else:
        l = s.count('(')
        r = len(s) - l
        if l >= r:
            P.append((less, s))
        else:
            L.append((-less, s))

P.sort(key=lambda a: a[0])
L.sort(key=lambda a: a[0])
P = [s for _, s in P]
L = [s for _, s in L]
ans = ''.join(H) + ''.join(P) + ''.join(L)

l = ans.count('(')
r = len(ans) - l

if l != r or calc(ans) < 0:
    print('No')
else:
    print('Yes')

Submission status: Wrong Answer

Solution code:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()
N=int(input())
S=[input() for i in range(N)]
llst=[]
lr=[]
rlst=[]
for n in range(N):
    l=0
    r=0
    for i in range(len(S[n])):
        if S[n][i]=="(":
            l+=1
        else:
            if l>0:
                l-=1
            else:
                r+=1
    #print(l,r)
    if l and not r:
        llst.append(l)
    elif not l and r:
        rlst.append(r)
    elif l or r:
        lr.append([l,r])
llst=sum(llst)
rlst=sum(rlst)

if not llst and not rlst and not lr:
    print("Yes")
    exit()
stack=[]
idleR=10**7
if lr:
    L,R=lr[0]
    stack=[[L,R]]
    for n in range(1,len(lr)):
        #print(stack)
        L,R=lr[n]
        visited=set()
        nstack=[]
        while stack:
            l,r=stack.pop()
            for xl,xr in [[l+L-R,r],[l,r+R-L]]:
                if xl>=0 and xr>=0:
                    X=xl+idleR*xr
                    if not X in visited:
                        visited.add(X)
                        nstack.append([xl,xr])
if not stack:
    if llst-rlst==0:
        print("Yes")
    else:
        print("No")
    exit()

for l,r in stack:
    if l<=rlst:

        rlst-=l
        l=0
    else:
        continue
    if r<=llst:

        llst-=r
        r=0
    else:
        continue

    if llst-rlst==0:
        print("Yes")
        exit()
    else:
        continue
print("No")

Submission status: Wrong Answer

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

N = int(input())
S = [input().rstrip() for _ in range(N)]

def calc(T):
    now = 0
    ret = 0
    for s in T:
        if s == '(':
            now += 1
        elif s == ')':
            now -= 1
        ret = min(ret, now)
    return ret

H = []
P = []
L = []

for s in S:
    less = -calc(s)
    if less == 0:
        H.append(s)
    else:
        l = s.count('(')
        r = len(s) - l
        if l >= r:
            P.append((less, s))
        else:
            L.append((-less, s))

P.sort(key=lambda a: a[0])
L.sort(key=lambda a: a[0])
P = [s for _, s in P]
L = [s for _, s in L]
ans = ''.join(H) + ''.join(P) + ''.join(L)

l = ans.count('(')
r = len(ans) - l

if l != r or calc(ans) < 0:
    print('No')
else:
    print('Yes')

Submission status: Wrong Answer

Solution code:
n = int(input())
start = 0
end = 0
left = 0
double = []
right = 0
for i in range(n):
    s = str(input())
    kienaileft = 0
    kienairight = 0
    for j in range(len(s)):
        if s[j] == ")":
            kienaileft += 1
        else:
            break
    for j in range(len(s)):
        if s[-(j+1)] == "(":
            kienairight += 1
        else:
            break
    nowleft = 0
    nowright = 0
    for j in range(kienaileft,len(s)-kienairight):
        if s[j] == ")":
            nowleft += 1
        else:
            nowright += 1
    num = min(nowleft,nowright)
    kienaileft += nowleft -num
    kienairight += nowright -num
    if kienaileft != 0:
        if kienairight != 0:
            double.append([kienaileft,kienairight])
        else:
            left += kienaileft
    else:
        if kienairight != 0:
            right += kienairight
  # print(left,double,right)
if left + sum([double[i][0] for i in range(len(double))]) != sum([double[i][1] for i in range(len(double))]) + right:
    print("No")
    exit()
if len(double) != 0:
    if not left or not right:
        print("No")
        exit()
else:
    if left == right:
        print("Yes")
        exit()
double.sort(key=lambda x:x[1],reverse=True)
double.sort()
double.sort(key=lambda x:x[0]-x[1])
now = left

for b,a in double:
    if now < a:
        print("No")
        exit()
    now += (b-a)
print("Yes")

Submission status: Wrong Answer

Solution code:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()
N=int(input())
S=[input() for i in range(N)]
llst=[]
lr=[]
rlst=[]
for n in range(N):
    l=0
    r=0
    for i in range(len(S[n])):
        if S[n][i]=="(":
            l+=1
        else:
            if l>0:
                l-=1
            else:
                r+=1
    #print(l,r)
    if l and not r:
        llst.append(l)
    elif not l and r:
        rlst.append(r)
    elif l or r:
        lr.append([l,r])
llst=sum(llst)
rlst=sum(rlst)

if not llst and not rlst and not lr:
    print("Yes")
    exit()
stack=[]
idleR=10**7
if lr:
    L,R=lr[0]
    stack=[[L,R]]
    for n in range(1,len(lr)):
        #print(stack)
        L,R=lr[n]
        visited=set()
        nstack=[]
        while stack:
            l,r=stack.pop()
            for xl,xr in [[l+L-R,r],[l,r+R-L]]:
                if xl>=0 and xr>=0:
                    X=xl+idleR*xr
                    if not X in visited:
                        visited.add(X)
                        nstack.append([xl,xr])
if not stack:
    if llst-rlst==0:
        print("Yes")
    else:
        print("No")
    exit()

for l,r in stack:
    if l<=rlst:

        rlst-=l
        l=0
    else:
        continue
    if r<=llst:

        llst-=r
        r=0
    else:
        continue

    if llst-rlst==0:
        print("Yes")
        exit()
    else:
        print("No")
        exit()
print("No")

Submission status: Wrong Answer

Solution code:
n = int(input())
start = 0
end = 0
left = 0
double = []
right = 0
for i in range(n):
    s = str(input())
    kienaileft = 0
    kienairight = 0
    for j in range(len(s)):
        if s[j] == ")":
            kienaileft += 1
        else:
            break
    for j in range(len(s)):
        if s[-(j+1)] == "(":
            kienairight += 1
        else:
            break
    nowleft = 0
    nowright = 0
    for j in range(kienaileft,len(s)-kienairight):
        if s[j] == ")":
            nowleft += 1
        else:
            nowright += 1
    num = min(nowleft,nowright)
    kienaileft += nowleft -num
    kienairight += nowright -num
    if kienaileft != 0:
        if kienairight != 0:
            double.append([kienaileft,kienairight])
        else:
            left += kienaileft
    else:
        if kienairight != 0:
            right += kienairight
  # print(left,double,right)
if left + sum([double[i][0] for i in range(len(double))]) != sum([double[i][1] for i in range(len(double))]) + right:
    print("No")
    exit()
if len(double) != 0:
    if not left or not right:
        print("No")
        exit()
else:
    if left == right:
        print("Yes")
        exit()
double.sort(key=lambda x:x[1],reverse=True)
double.sort()
double.sort(key=lambda x:x[0]-x[1])
now = left
print(left,double,right)
for b,a in double:
    if now < a:
        print("No")
        exit()
    now += (b-a)
print("Yes")

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    S = [input() for _ in range(N)]
    work = []
    for s in S:
        temp = [0, 0]
        flag = None
        state = False
        hoge = 0
        for c in s:
            if c == "(":
                if state:
                    state = False
                    if hoge > 0:
                        temp[0] += hoge
                    else:
                        temp[1] += hoge
                    hoge = 0
                flag = True
                hoge += 1
            else:
                if flag == True:
                    flag = False
                    state = True
                    hoge -= 1
                else:
                    flag = False
                    if state:
                        hoge -= 1
                    else:
                        temp[1] += 1
        temp[0] += hoge
        work.append(temp)
    a, b = 0, 0
    for l, r in work:
        a += l
        b += r
        if l == 0 and r == 0:
            N -= 1
    if a == b and N > 1:
        print("Yes")
    else:
        print("No")
main()

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict
from itertools import combinations, permutations, combinations_with_replacement
from itertools import accumulate
from math import ceil, sqrt, pi

INF = 10 ** 18

N = int(input())
S = [input() for _ in range(N)]

T = []
for s in S:
    a, b = 0, 0
    for ss in s:
        if ss == ")":
            if a:
                a -= 1
            else:
                b += 1
        else:
            a += 1
    T.append([a, b])
#print(T)

ta, tb = 0, 0
for t1, t2 in T:
    ta += t1
    tb += t2
#print(ta, tb)

if ta != tb:
    print("No")
    exit()

A = []
B = []
C = []

for i in range(N):
    if T[i][1] == 0:
        A.append(T[i])
    else:
        if T[i][0] >= T[i][1]:
            B.append(T[i])
        else:
            C.append(T[i] + [T[i][1] - T[i][0]])
#print(A, B, C)
B.sort(key = lambda x: x[1])
C.sort(key = lambda x: x[2])

cnt = 0
for a in A:
    cnt += a[0]
#print(cnt)

for b in B:
    cnt -= b[1]
    if cnt < 0:
        print("No")
        exit()
    cnt += b[0]

for c in C:
    cnt -= c[1]
    if cnt < 0:
        print("No")
        exit()
    cnt += c[0]

print("Yes")