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: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
from bisect import bisect_left,bisect_right
from collections import defaultdict
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    class SegmentTree:
        def __init__(self,n,segfunc,ide_ele):
            self.segfunc=segfunc
            self.ide_ele=ide_ele
            self.num=2**(n-1).bit_length()
            self.dat=[ide_ele]*2*self.num
        
        def init(self,iter):
            for i in range(len(iter)):
                self.dat[i+self.num]=iter[i]
            for i in range(self.num-1,0,-1):
                self.dat[i]=self.segfunc(self.dat[i*2],self.dat[i*2+1])
        
        def update(self,k,x):
            k+=self.num
            self.dat[k]=x
            while k:
                k//=2
                self.dat[k]=self.segfunc(self.dat[k*2],self.dat[k*2+1])
        
        def query(self,p,q):
            if q<=p:
                return self.ide_ele
            p+=self.num
            q+=self.num-1
            res=self.ide_ele
            while q-p>1:
                if p&1==1:
                    res=self.segfunc(res,self.dat[p])
                if q&1==0:
                    res=self.segfunc(res,self.dat[q])
                    q-=1
                p=(p+1)//2
                q=q//2
            if p==q:
                res=self.segfunc(res,self.dat[p])
            else:
                res=self.segfunc(self.segfunc(res,self.dat[p]),self.dat[q])
            return res
    
    N=int(input())
    S=[input() for i in range(N)]
    P=0
    M=0
    c=0
    Seg=SegmentTree(10**6+1,lambda a,b:max(a,b),-INF)
    l_PM=defaultdict(list)
    stack=defaultdict(list)
    se=set()
    for i,s in enumerate(S):
        p=0
        m=0
        for x in s:
            if x=='(':
                p+=1
            else:
                if p>0:
                    p-=1
                else:
                    m+=1
        if m==0 and p>0:
            P+=p
        elif p==0 and m>0:
            M+=m
        elif p>0 and m>0:
            c+=1
            se.add(m)
            stack[m].append(p-m)
            l_PM[p-m].append(m)
    
    for x in se:
        stack[x].sort()
        y=stack[x].pop()
        Seg.update(x,y)
    
    for _ in range(c):
        x=Seg.query(0,P+1)
        if x==-INF:
            print('No')
            exit()
        if P-x<0:
            print('No')
            exit()
        
        l_PM[x].sort()
        
        index=l_PM[x][bisect_left(l_PM[x],P)]
        if stack[index]:
            y=stack[index].pop()
            Seg.update(index,y)
        else:
            Seg.update(index,-INF)
        P+=x
    P-=M
    YesNo(P==0)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
from bisect import bisect_left,bisect_right
from collections import defaultdict
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    class SegmentTree:
        def __init__(self,n,segfunc,ide_ele):
            self.segfunc=segfunc
            self.ide_ele=ide_ele
            self.num=2**(n-1).bit_length()
            self.dat=[ide_ele]*2*self.num
        
        def init(self,iter):
            for i in range(len(iter)):
                self.dat[i+self.num]=iter[i]
            for i in range(self.num-1,0,-1):
                self.dat[i]=self.segfunc(self.dat[i*2],self.dat[i*2+1])
        
        def update(self,k,x):
            k+=self.num
            self.dat[k]=x
            while k:
                k//=2
                self.dat[k]=self.segfunc(self.dat[k*2],self.dat[k*2+1])
        
        def query(self,p,q):
            if q<=p:
                return self.ide_ele
            p+=self.num
            q+=self.num-1
            res=self.ide_ele
            while q-p>1:
                if p&1==1:
                    res=self.segfunc(res,self.dat[p])
                if q&1==0:
                    res=self.segfunc(res,self.dat[q])
                    q-=1
                p=(p+1)//2
                q=q//2
            if p==q:
                res=self.segfunc(res,self.dat[p])
            else:
                res=self.segfunc(self.segfunc(res,self.dat[p]),self.dat[q])
            return res
    
    N=int(input())
    S=[input() for i in range(N)]
    P=0
    M=0
    c=0
    Seg=SegmentTree(2*10**5+1,lambda a,b:max(a,b),-INF)
    l_PM=defaultdict(list)
    stack=defaultdict(list)
    se=set()
    for i,s in enumerate(S):
        p=0
        m=0
        for x in s:
            if x=='(':
                p+=1
            else:
                if p>0:
                    p-=1
                else:
                    m+=1
        if m==0 and p>0:
            P+=p
        elif p==0 and m>0:
            M+=m
        elif p>0 and m>0:
            c+=1
            se.add(m)
            stack[m].append(p-m)
            l_PM[p-m].append(m)
    
    for x in se:
        stack[x].sort()
        y=stack[x].pop()
        Seg.update(x,y)
    
    for _ in range(c):
        x=Seg.query(0,P+1)
        if x==-INF:
            print('No')
            exit()
        if P-x<0:
            print('No')
            exit()
        
        l_PM[x].sort()
        
        index=l_PM[x][bisect_left(l_PM[x],P)]
        if stack[index]:
            y=stack[index].pop()
            Seg.update(index,y)
        else:
            Seg.update(index,-INF)
        P+=x
    P-=M
    YesNo(P==0)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
from bisect import bisect_left,bisect_right
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    class SegmentTree:
        def __init__(self,n,segfunc,ide_ele):
            self.segfunc=segfunc
            self.ide_ele=ide_ele
            self.num=2**(n-1).bit_length()
            self.dat=[ide_ele]*2*self.num
        
        def init(self,iter):
            for i in range(len(iter)):
                self.dat[i+self.num]=iter[i]
            for i in range(self.num-1,0,-1):
                self.dat[i]=self.segfunc(self.dat[i*2],self.dat[i*2+1])
        
        def update(self,k,x):
            k+=self.num
            self.dat[k]=x
            while k:
                k//=2
                self.dat[k]=self.segfunc(self.dat[k*2],self.dat[k*2+1])
        
        def query(self,p,q):
            if q<=p:
                return self.ide_ele
            p+=self.num
            q+=self.num-1
            res=self.ide_ele
            while q-p>1:
                if p&1==1:
                    res=self.segfunc(res,self.dat[p])
                if q&1==0:
                    res=self.segfunc(res,self.dat[q])
                    q-=1
                p=(p+1)//2
                q=q//2
            if p==q:
                res=self.segfunc(res,self.dat[p])
            else:
                res=self.segfunc(self.segfunc(res,self.dat[p]),self.dat[q])
            return res
    
    N=int(input())
    S=[input() for i in range(N)]
    P=0
    M=0
    c=0
    Seg=SegmentTree(2*10**5+1,lambda a,b:max(a,b),-INF)
    l_PM=[[] for _ in range(2*10**5+1)]
    stack=[[] for _ in range(2*10**5+1)]
    se=set()
    for i,s in enumerate(S):
        p=0
        m=0
        for x in s:
            if x=='(':
                p+=1
            else:
                if p>0:
                    p-=1
                else:
                    m+=1
        if m==0 and p>0:
            P+=p
        elif p==0 and m>0:
            M+=m
        elif p>0 and m>0:
            c+=1
            se.add(m)
            stack[m].append(p-m)
            l_PM[p-m].append(m)
    
    for x in se:
        stack[x].sort()
        y=stack[x].pop()
        Seg.update(x,y)
    
    for _ in range(c):
        x=Seg.query(0,P+1)
        if x==-INF:
            print('No')
            exit()
        if P-x<0:
            print('No')
            exit()
        
        l_PM[x].sort()
        
        index=l_PM[x][bisect_left(l_PM[x],P)]
        if stack[index]:
            y=stack[index].pop()
            Seg.update(index,y)
        else:
            Seg.update(index,-INF)
        P+=x
    P-=M
    YesNo(P==0)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

n = int(input())
cnt = 0
decrement = 0
profit = []
loss = []

for _ in range(n):
    s = input()
    min_p = 0
    end_p = 0
    point = 0
    for c in s:
        if c == '(':
            point += 1
        elif c == ')':
            point -= 1
            if point < min_p:
                min_p = point
    else:
        end_p = point
    if 0 <= min_p:
        cnt += end_p
    else:
        if min_p == end_p:
            decrement += end_p
        else:
            if 0 <= end_p:
                profit.append((min_p, end_p))
            else:
                loss.append((min_p, end_p))


profit.sort(reverse=True)
while profit:
    min_p, end_p = profit.pop()
    if cnt+min_p < 0:
        print('No')
        exit()
    cnt += end_p


loss.sort()
while loss:
    min_p, end_p = profit.pop()
    if cnt+min_p < 0:
        print('No')
        exit()
    cnt += end_p

print('Yes' if cnt+decrement == 0 else 'No')

Submission status: Runtime Error

Solution code:
from itertools import *
n,*s=open(0).read().split()
u=[[min([0,accumulate(t,lambda a,b: a+(1 if b=="(" else -1))]),2*t.count("(")-len(t)] for t in s]
m=0
for c,d in chain(sorted([x for x in u if x[1]>=0])[::-1],sorted([x for x in u if x[1]<0],key=lambda z:z[0]-z[1])):
    if m+c<0:print("No");break
    m+=d
else:print("No" if m else "Yes")

Submission status: Runtime Error

Solution code:
from sys import exit
from itertools import accumulate,chain
n,*s=open(0).read().split()
t=[2*i.count("(")-len(i) for i in s]
if sum(t)!=0:
    print("No");exit()
st=[[min(accumulate(s_,lambda a,b: a+(1 if b=="(" else -1),initial=0)),t_] for s_,t_ in zip(s,t)]
now=0
for c in chain(sorted([x for x in st if x[1]>=0])[::-1],sorted([x for x in st if x[1]<0],lambda z:z[1]-z[0])[::-1]):
    if now+c[0]<0:
        print("No");exit()
    now+=c[1]
print("Yes")

Submission status: Runtime Error

Solution code:
from sys import exit
from itertools import accumulate,chain
n,*s=open(0).read().split()
t=[2*i.count("(")-len(i) for i in s]
if sum(t)!=0:
    print("No");exit()
st=[[min(accumulate(s_,lambda a,b: a+(1 if b=="(" else -1),initial=0)),t_] for s_,t_ in zip(s,t)]
now=0
for c in chain(sorted([x if x[1]>=0 for x in st])[::-1],sorted([x if x[1]<0 for x in st],lambda z:z[1]-z[0])[::-1]):
    if now+c[0]<0:
        print("No");exit()
    now+=c[1]
print("Yes")

Submission status: Runtime Error

Solution code:
print 'No'

Submission status: Runtime Error

Solution code:
from sys import exit
from itertools import accumulate
n=int(input())
s=[input() for i in range(n)]
t=[2*(i.count("("))-len(i) for i in s]
#pypyではinitialだめ
st=[[t[i],min(accumulate(s[i],lambda a,b: a+(1 if b=="(" else -1),initial=0))] for i in range(n)]

now2=sum(map(lambda x:x[0],filter(lambda x:x[1]>=0,st)))
v=list(filter(lambda x:x[1]<0 and x[0]>=0,st))
w=list(filter(lambda x:x[1]<0 and x[0]<0,st))
v.sort(reverse=True,key=lambda z:z[1])
w.sort(key=lambda z:z[0]-z[1],reverse=True)

for sub in chain(v,w):
    if now2+sub[1]<0:
        print("No");exit()
    now2+=sub[0]
print("Yes")

Submission status: Runtime Error

Solution code:
def pdebut(s):
	o = 0
	for c in s:
		if c=='(':o+=1
		else: o-=1
		if o<0 : return False
	return o>=0
	
def pfin(s):
	c = 0
	for o in s[::-1]:
		if o==')':
			c+=1
		else:c-=1
		if c<0: return False
	return c>=0
	
def valuer(s):
	o = 0
	for c in s:
		if c=='(':o+=1
		else: o-=1
	return o
	
n = int(input())
val = [0]*(n+1)
tab = []
debut = []
fin = []
milieu = []
for i in range(n):
	s = input()
	tab.append(s)
	if pdebut(s):
		debut+=[i]
	elif pfin(s):
		fin+=[i]
	else:
		val[i] = valuer(s)
		milieu+=[i]

# ~ def cle(x):
	# ~ return -x[1]		
# ~ couples = [[i,val[i]] for i in milieu]
# ~ couples.sort(key = cle)

S = "".join(tab[i] for i in debut)
S+="".join(tab[c[0]] for c in couples)
S+= "".join(tab[i] for i in fin)

# ~ print("debut",debut)
# ~ print("milieu",milieu)
# ~ print("fin",fin)

# ~ print(S)

def Bon(s):
	o = 0
	for c in s:
		if c=='(':o+=1
		else: o-=1
		if o<0 : return False
	return o==0
print("Yes" if Bon(S) else "No")

Submission status: Runtime Error

Solution code:
def main():
  N = int(input())
  Sp = []
  Sm = []
  total = 0
  for i in range(N):
    l = input()
    u = 0
    h = 0
    um = 0
    for j in range(len(l)):
      if l[j] == '(':
        h += 1
      else:
        h -= 1
      u = min(u, h)
    if h == 0:
      um = min(um, u)
    elif h > 0:
      Sp.append([u, h])
    else:
      Sm.append([u-h, -h])
    total += h
  if total != 0:
    print('No')
    exit()
  Sp.sort(key=lambda, x:x[0])
  p = check(Sp)
  if p < 0 or p < -um:
    print('No')
    exit()
  Sm.sort(key=lambda, x:x[0])
  m = check(Sm)
  if m < 0:
    print('No')
    exit()
  print('Yes')

def check(S):
  h = 0
  for i in range(len(S)):
    if h + S[i][0] < 0:
      return -1
    else:
      h += S[i][1]
  return h

if __name__ == '__main__':
  main()

Submission status: Runtime Error

Solution code:
import sys
from functools import reduce
n=int(input())
s=[input() for i in range(n)]
t=[2*(i.count("("))-len(i) for i in s]
if sum(t)!=0:
    print("No")
    sys.exit()
st=[[t[i]] for i in range(n)]

for i in range(n):
    now,mi=0,0
    for j in s[i]:
        if j=="(":
            now+=1
        else:
            now-=1
        mi=min(mi,now)
    st[i].append(mi)

now2=reduce(lambda a,b:a[0]+b[0],filter(lambda x:x[1]>=0,st))
v,w=list(filter(lambda x:x[1]<0 and x[0]>=0,st)),list(filter(lambda x:x[1]<0 and x[0]<0,st))
v.sort(reverse=True,key=lambda z:z[1])
w.sort(key=lambda z:z[0]-z[1],reverse=True)

for vsub in v:
    if now2+vsub[1]<0:
        print("No")
        sys.exit()
    now2+=vsub[0]
for wsub in w:
    if now2+wsub[1]<0:
        print("No")
        sys.exit()
    now2+=wsub[0]
print("Yes")

Submission status: Runtime Error

Solution code:
import sys
n=int(input())
s=[input() for i in range(n)]
t=[2*(i.count("("))-len(i) for i in s]
if sum(t)!=0:
    print("No")
    sys.exit()
st=[[t[i]] for i in range(n)]

for i in range(n):
    now,mi=0,0
    for j in s[i]:
        if j=="(":
            now+=1
        else:
            now-=1
        mi=min(mi,now)
    st[i].append(mi)
#st.sort(reverse=True,key=lambda z:z[1])
u,v,w=list(filter(lambda x:x[1]>=0,st)),list(filter(lambda x:x[1]<0 and x[0]>=0,st)),list(filter(lambda x:x[1]<0 and x[0]<0,st))
v.sort(reverse=True)
v.sort(reverse=True,key=lambda z:z[1])
w.sort(reverse=True)
w.sort(key=lambda z:z[1])
lu=len(u)
lv=len(v)
now2=0
for i in range(n):
    if i<lu:
        now2+=u[i][0]
    elif i<lu+lv:
        if now2+v[i-lu][1]<0:
            print("No")
            break
        now2+=v[i-lu][0]
    else:
        #いや、間違ってるのここなんかーーい
        if now2+w[i-lu-lv][1]<0:
            k
            print("No")
            break
        now2+=w[i-lu-lv][0]
else:
    print("Yes")

Submission status: Runtime Error

Solution code:
import sys
n=int(input())
s=[input() for i in range(n)]
t=[2*(i.count("("))-len(i) for i in s]
if sum(t)!=0:
    print("No")
    sys.exit()
st=[[t[i]] for i in range(n)]

for i in range(n):
    now,mi=0,0
    for j in s[i]:
        if j=="(":
            now+=1
        else:
            now-=1
        mi=min(mi,now)
    st[i].append(mi)
#st.sort(reverse=True,key=lambda z:z[1])
u,v,w=list(filter(lambda x:x[1]>=0,st)),list(filter(lambda x:x[1]<0 and x[0]>=0,st)),list(filter(lambda x:x[1]<0 and x[0]<0,st))
v.sort(reverse=True)
v.sort(reverse=True,key=lambda z:z[1])
w.sort(reverse=True)
w.sort(reverse=True,key=lambda z:z[1])
lu=len(u)
lv=len(v)
now2=0
for i in range(n):
    if i<lu:
        now2+=u[i][0]
    elif i<lu+lv:
        if now2+v[i-lu][1]<0:
            print("No")
            break
        now2+=v[i-lu][0]
    else:
        if now2+w[i-lu-lv][1]<0:
            k
            print("No")
            break
        now2+=w[i-lu-lv][0]
else:
    print("Yes")

Submission status: Runtime Error

Solution code:
import sys
readline = sys.stdin.readline().strip


def solve():
    N = int(input())
    brackets_generator = (readline() for _ in range(N))

    grads_positive = list()
    grads_negative = list()

    total = 0
    for brackets in brackets_generator:

        elevation, bottom = 0, 0

        for bk in brackets:

            elevation += 1 if bk == '(' else -1
            bottom = min(bottom, elevation)

        if elevation >= 0:
            grads_positive.append((bottom, elevation))
        elif elevation < 0:
            grads_negative.append((bottom - elevation, -elevation))

        total += elevation

    if total != 0:
        return False

    grads_positive.sort(reverse=True)
    grads_negative.sort(reverse=True)

    def is_good(grads):
        elevation, bottom = 0, 0
        for grad in grads:
            bottom = elevation + grad[0]
            if bottom < 0:
                return False
            elevation += grad[1]

        return True

    if is_good(grads_positive) and is_good(grads_negative):
        return True
    else:
        return False


def main():
    ok = solve()
    if ok:
        print('Yes')
    else:
        print('No')


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
# **************************************************************************** #
#                                                                              #
#                                            __   __ .____  .__  __.  ____     #
#    F-bracketSequencing.py                 |  | |  ||  _ \ |  \/  | /    |    #
#                                           |  | |  || |_| || \  / ||  ,--'    #
#    By: ayahyao <y.anas1997@gmail.com>     |  | |  ||  __/ | |\/| ||  |       #
#                                           |  `-'  || |    | |  | ||  `--.    #
#    Created: 2020/05/10 18:38 by Anas       \_____/ |_|    |_|  |_| \____|    #
#    Updated: 2020/05/10 18:40 by Anas                                         #
#                                                                              #
# **************************************************************************** #

def     process(tab, beginning, end):
    total = beginning
    for i in tab:
        if (i[1] > total or total + i[0] < 0):
            return ("No")
        total += i[0]
    if (total == end):
        return ("Yes")
    return ("No")

def     parsing(N):
    beginning, ending = 0,0
    clean = 0
    total = 0
    tab = []

    for i in range(N):
        s = input()
        before, after = 0, 0
        for j in s:
            if (j == '('):
                after += 1
            elif (j == ')'):
                if (after > 0):
                    after -= 1
                else:
                    before += 1
        if (before == 0 and after > 0):
            beginning += after
        elif (after == 0 and before > 0):
            ending += before
        elif (before > 0 or after > 0):
            tab.append((after - before, before, after))
        else:
            clean += 1
        total += before - after
    tab = sorted(tab)[::-1]
    return tab, total, beginning, ending


N  = int(input())
tab, total, beginning, ending = parsing(N)
if (total == 0 and N == 1):
    res = "Yes"
elif ((total != 0) or ((min(beginning, ending) == 0 and clean == 0) 
                 or (max(beginning, ending) == 0 and clean == 1))):
    res = "No"
else:
    res = process(tab, beginning, ending)
print(res)

Submission status: Runtime Error

Solution code:
# **************************************************************************** #
#                                                                              #
#                                            __   __ .____  .__  __.  ____     #
#    F-bracketSequencing.py                 |  | |  ||  _ \ |  \/  | /    |    #
#                                           |  | |  || |_| || \  / ||  ,--'    #
#    By: ayahyao <y.anas1997@gmail.com>     |  | |  ||  __/ | |\/| ||  |       #
#                                           |  `-'  || |    | |  | ||  `--.    #
#    Created: 2020/05/10 18:38 by Anas       \_____/ |_|    |_|  |_| \____|    #
#    Updated: 2020/05/10 18:38 by Anas                                         #
#                                                                              #
# **************************************************************************** #

def     process(tab, beginning, end):
    total = beginning
    for i in tab:
        if (i[1] > total or total + i[0] < 0):
            return ("No")
        total += i[0]
    if (total == end):
        return ("Yes")
    return ("No")

def     parsing():
    beginning, ending = 0
    clean = 0
    total = 0
    tab = []

    N  = int(input())
    for i in range(N):
        s = input()
        before, after = 0, 0
        for j in s:
            if (j == '('):
                after += 1
            elif (j == ')'):
                if (after > 0):
                    after -= 1
                else:
                    before += 1
        if (before == 0 and after > 0):
            beginning += after
        elif (after == 0 and before > 0):
            ending += before
        elif (before > 0 or after > 0):
            tab.append((after - before, before, after))
        else:
            clean += 1
        total += before - after
    tab = sorted(tab)[::-1]
    return tab, total, beginning, ending


tab, total, beginning, ending = parsing()
if (total == 0 and N == 1):
    res = "Yes"
elif ((total != 0) or ((min(beginning, ending) == 0 and clean == 0) 
                 or (max(beginning, ending) == 0 and clean == 1))):
    res = "No"
else:
    res = process(tab, beginning, ending)
print(res)

Submission status: Runtime Error

Solution code:
N = int(input())
LR = [[0]*2 for i in range(N)]
for i in range(N):
    S = input()
    M = len(S)
    t = 0
    Life = 0
    R = 0
    while t<M:
        if S[t]=="(":
            Life += 1
        elif S[t]==")":
            if Life>=1:
                Life += -1
            else:
                R+=1
        t+=1
    LR[i][0] = Life #L
    LR[i][1] = R    # R

LP = 0
RP = 0
X = []
for i in range(N):
    L = LR[i][0]
    R = LR[i][1]
    if (L==0)and(R==0):
        continue
    elif L==0:
        RP += R
    elif R==0:
        LP += L
    else:
        X.append([L,R,L-R])

X.sort(key=lambda x:x[2],reverse=True)

Life = LP
if Life==0:
    if (RP==0)and(len(X)==0):
        print("Yes")
    else:
        print("No")
else:
    flag = 1
    for i in range(len(X)):
        Life += -1*X[i][1]
        if (Life<0)and(X[1]-X[2]<0):
            flag=0
        Life += X[i][0]
    if flag==0:
        print("No")
    elif Life==RP:
        print("Yes")
    else:
        print("No")

Submission status: Runtime Error

Solution code:
N = int(input())
from collections import deque
L = deque([])
R = deque([])

for i in range(N):
  S = input()
  l = [0]*len(S)
  if S[0]=='(':
    l[0]=1
  else:
    l[0]=-1
  for j in range(1,len(S)):
    if S[j]=='(':
      l[j] = l[j-1] + 1
    else:
      l[j] = l[j-1] - 1
      
  if l[-1] < 0:
    R.append([min(l)-l[-1],-l[-1]])
  else:
    L.append([min(l),l[-1]])
    
R = sorted(R, key = lambda x:x[0], reverse = True)
L = sorted(L, key = lambda x:x[0])

now = 0
judge = True
for r in R:
  if now+r[0]<0:
    judge = False
    break
  else:
    now += r[1]
    
for l in L:
  if now + l[0]<0:
    judge = False
    break
  else:
    now += r[1]
    
if now!=0:
  judge = False
  
if judge:
  print('Yes')
else:
  print('No')

Submission status: Runtime Error

Solution code:
n = int(input())
s_num = [0 for _ in range(n)]
s_num_min = [0 for _ in range(n)]
for i in range(n):
    kakko_in = input()
    for s_in in kakko_in:
        if s_in == '(':
            s_num[i] += 1
        else:
            s_num[i] -= 1
        if s_num[i] < s_num_min[i]:
            s_num_min[i] = s_num[i]

if sum(s_num) != 0:
    print("No")
else:
    now_sum = 0
    now_min_sum = 0
    s_num_index = s_num.argsort()[::-1]
    # print(s_num_index)
    # print(s_num_min_index)
    yet = [1 for _ in range(n)]
    i = 0
    flag = 0
    while i < n:
        index = s_num_index[i]
        if now_sum + s_num_min[index] >= 0:
            flag = 0
            now_sum += s_num[index]
            i += 1
        else:
            flag = 1
            break
        # elif i < n-1:
        #     if flag:
        #         break
        #     temp = s_num_index[i+1]
        #     s_num_index[i] = temp
        #     s_num_index[i+1] = index
        #     flag = 1
    if flag:
        print("No")
    else:
        print("Yes")

Submission status: Runtime Error

Solution code:
N = int(input())
Up = []
Down = []
for _ in range(N):
    S = input()
    L = [0]
    for __ in range(len(S)):
        if S[__] == '(':
            L.append(L[-1] + 1)
        else:
            L.append(L[-1] - 1)
        las = L[-1]
        mi = min(L)
    if las >= 0:
        Up.append((mi, las))
    else:
        Down.append((mi, las))

Up.sort(reverse=True)
Down.sort()

now = 0
for i, j in Up:
    if now + i < 0:
        print('No')
        exit()
    else:
        now += j
for i, j in Down:
    if now + i < 0:
        print('No')
        exit()
    else:
        now += j
if now == 0:
    print('Yes')
else:
    print('No')
N = int(input())
Up = []
Down = []
for _ in range(N):
    S = input()
    L = [0]
    for __ in range(len(S)):
        if S[__] == '(':
            L.append(L[-1] + 1)
        else:
            L.append(L[-1] - 1)
        las = L[-1]
        mi = min(L)
    if las >= 0:
        Up.append((mi, las))
    else:
        Down.append((mi, las))

Up.sort(reverse=True)
Down.sort()

now = 0
for i, j in Up:
    if now + i < 0:
        print('No')
        exit()
    else:
        now += j
for i, j in Down:
    if now + i < 0:
        print('No')
        exit()
    else:
        now += j
if now == 0:
    print('Yes')
else:
    print('No')

Submission status: Runtime Error

Solution code:
import bisect
import pdb
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))



########################################
import math

class SegmentTree:
    def __init__(self, n, a=None):
        """初期化
        num : nより大きい最小の2のべき乗
        """
        self.num = 2**(int(math.log2(n))+1)
        self.seg = [0] * (2*self.num-1)
        if a is not None:
            for i,item in enumerate(a):
                self.update(i,item)
        
    def update(self,i,x):
        """update(i,x):Aiをxに更新する
        """
        k = i + self.num - 1
        while k >= 0:
            if x>self.seg[k]:
                self.seg[k] = x
                k = (k-1)//2
            else:
                break
                
    def query(self,a,b,k=0,l=0,r=None,index=False):
        """query(a,b,0,0,num):[a,b)の最大値
        index==Trueのときインデックスも返す
        """
        if r is None:
            r = self.num

        if r <= a or b <= l:
            return (-float("inf"), None) if index else -float("inf")
        elif a <= l and r <= b:
            return (self.seg[k], self._index(k)) if index else self.seg[k]
        else:
            return max(self.query(a,b,2*k+1,l,(l+r)//2, index=index),self.query(a,b,2*k+2,(l+r)//2,r, index=index))
    
    def _index(self, k):
        if k>=self.num:
            return k - (self.num-1)
        else:
            if self.seg[2*k+1]>=self.seg[2*k+2]:
                return self._index(2*k+1)
            else:
                return self._index(2*k+2)


    ######################################################


n = int(input())
minsum = [None] * n # (min, sum)
for i in range(n):
    tmp = list(map(int, " ".join(input()).replace("(", "1").replace(")", "-1").split()))
    c = 0
    m = 0
    for item in tmp:
        c += item
        m = min(c, m)
    minsum[i] = (m, sum(tmp))
minsum.sort()


seg = SegmentTree(n, [item[1] for item in minsum])

if sum(item[1] for item in minsum)!=0:
    print("No")
else:
    c = 0
    for i in range(n):
        ind = bisect.bisect_right(minsum, (-c, -10**9))
        if ind==n:
            print("No")
            break
        s, ind2 = seg.query(ind, n, index=True)
        c += s
        seg.update(ind2, -10**9)
    else:
        print("Yes")

Submission status: Runtime Error

Solution code:

n = 0
s = []

def format_input(filename = None):
	global n
	global s
	if filename == None:
		n = int(input())
		s = [str(input()) for i in range(n)]

	elif filename == '__random__':
		from random import randint as rng
		from random import choices
		n = rng(1, 10**6)
		l = [rng(0, 10**6 - n) for i in range(n)]
		l.append(0)
		l.sort()
		s = [''.join(choices('()', k = l[i+1] - l[i] + 1)) for i in range(n)]
		print(n)
		[print(i) for i in s]

def semi_blacket(s):
	low, deff = [0] * 2
	if len(s) == 0:
		return low, deff

	l, d = semi_blacket(s[1:])
	if s[0] == '(':
		if l < 0:
			low = l + 1
		deff = d + 1
	else:
		low = l - 1
		deff = d - 1

	return low, deff

def get_answer():
	answer = 'Yes'
	ascend = []
	descend = []
	for i in range(n):
		low, deff = semi_blacket(s[i])
		if deff < 0:
			descend.append([low-deff, -deff])
		else:
			ascend.append([low, deff])

	ascend.sort()
	descend.sort()

	l_height = 0
	while len(ascend) > 0:
		low, deff = ascend.pop()
		if l_height + low < 0:
			answer = 'No'
		l_height += deff

	r_height = 0
	while len(descend) > 0:
		low, deff = descend.pop()
		if r_height + low < 0:
			answer = 'No'
		r_height += deff

	if l_height != r_height:
		answer = 'No'

	return answer

if __name__ == '__main__':
	format_input()

	ans = get_answer()
	print(ans)