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:

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:
		deff, low = ascend.pop()
		if l_height + low < 0:
			answer = 'No'
		l_height += deff

	r_height = 0
	while len(descend) > 0:
		deff, low = 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)

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):
	deff, low = [0] * 2
	if len(s) == 0:
		return deff, low

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

	return deff, low

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

	ascend.sort()
	descend.sort()

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

	r_height = 0
	while len(descend) > 0:
		deff, low = 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)

Submission status: Runtime Error

Solution code:
import sys

#input = raw_input
input = sys.stdin.readline
n, k = map(int, input().split(" "))
 
a_list = [int(a)-1 for a in  input().split(" ")]
uses = [-1] * n
path = [-1] * n
path[0] = 0
uses[0] = 0
 
count = 0
cur = 0
end = False
for i in range(n):
    count += 1
    cur = a_list[cur]
    if k == count:
        end = True
        break
 
    if uses[cur] != -1:
        break
    uses[cur] = count
    path[count] = cur
 
if end:
    out = cur+1
else:
    shuuki = count - uses[cur]
 
    shift = uses[cur]
    k1 = (k - shift) % shuuki + shift
    out = path[k1] + 1
 
print(out)

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):
        """初期化
        num : nより大きい最小の2のべき乗
        """
        self.num = 2**(int(math.log2(n))+1)
        self.seg = [0] * (2*self.num-1)
        
    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)

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:
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 lr:
    if llst-rlst==0:
        print("Yes")
    else:
        print("No")
    exit()

idleR=10**8
stack=[]
def main(n,xl,xr):
    X=xl+idleR*xr
    if  not dp[n][X]:
        dp[n][X]=1
        stack.append([n,xl,xr])
#L,R=lr[0]
dp=[defaultdict(int) for i in range(len(lr))]
main(-1,0,0)
#stack=[[0,L,R]]
while stack:
    n,l,r=stack.pop()
    if n+1<len(lr):
        L,R=lr[n+1]

        if L-r>=0:
            main(n+1,l+L-r,R)
        else:
            main(n+1,l,R-(L-r))

        if R-l>=0:
            main(n+1,L,r+R-l)
        else:
            main(n+1,L-(R-l),r)

    else:
        R=rlst-l
        L=llst-r
        if L==R and L>=0 and R>=0:
            print("Yes")
            exit()


print(Unko)
print("No")

Submission status: Runtime Error

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 lr:
    if llst-rlst==0:
        print("Yes")
    else:
        print("No")
    exit()
print(unko)
idleR=10**7
stack=[]
def main(n,xl,xr):
    X=xl+idleR*xr
    if  not dp[n][X]:
        dp[n][X]=1
        stack.append([n,xl,xr])
#L,R=lr[0]
dp=[defaultdict(int) for i in range(len(lr))]
main(-1,0,0)
#stack=[[0,L,R]]
while stack:
    n,l,r=stack.pop()
    if n+1<len(lr):
        L,R=lr[n+1]


        if L-r>=0:
            main(n+1,l+L-r,R)
        else:
            main(n+1,l,R-(L-r))

        if R-l>=0:
            main(n+1,L,r+R-l)
        else:
            main(n+1,L-(R-l),r)





    else:
        if l<=rlst:
            R=rlst-l
        else:
            continue
        if r<=llst:
            L=llst-r
        else:
            continue
        if L==R:
            print("Yes")
            exit()



print("No")

Submission status: Runtime Error

Solution code:
import sys
import heapq
hpush = heapq.heappush
hpop = heapq.heappop
from bisect import bisect_right as br
input = sys.stdin.readline
N = int(input())
ls = [0] * N
rs = [0] * N
t = []
tt = []
for x in range(N):
  S = list(input())[: -1]
  for i in range(len(S)):
    if S[i] == "(": rs[x] += 1
    if S[i] == ")":
      if rs[x]: rs[x] -= 1
      else: ls[x] += 1
  t.append((ls[x], rs[x]))
  tt.append(ls[x])
t.sort()
tt.sort()
if sum(ls) != sum(rs):
  print("No")
  exit(0)
if sum(ls) == 0:
  print("Yes")
  exit(0)
l = 0
for i in range(N):
  if ls[i] == 0 and (rs[i] > 0): l |= 1
  if rs[i] == 0 and (ls[i] > 0): l |= 2
if l < 3:
  print("No")
  exit(0)
l = 0
c = 0
cc = 0
h = []
while cc < N:
  r = br(tt, l)
  i = c
  while i < r:
    hpush(h, t[i][0] - t[i][1])
    i += 1
  c = i
  l += -hpop(h)
  cc += 1
  if l < 0:
    print("No")
    exit(0)
print("Yes")

Submission status: Runtime Error

Solution code:
import sys
n = int(input())
ss =[]
for _ in range(n):
    ss.apend(input())
cnt_p = []
cnt_m = []
for i in range(n):
    left = 0
    right = 0
    for s in ss[i]:
        if(s == '('):
            left += 1
        elif(s == ')'):
            if(left > 0):
                left -= 1
            else:
                right += 1
    if(left-right > 0):
        cnt_p.append((right,left))
    else:
        cnt_m.append((right,left))
 
 
cnt_p = sorted(cnt_p, key=lambda x: (x[0]))
cnt_m = sorted(cnt_m, key=lambda x: (x[1]*-1))
cnt = cnt_p + cnt_m
num = 0
for right,left in cnt:
    num -= right
    if(num < 0):
        print('No')
        sys.exit()
    num += left
if(num==0):
    print('Yes')
else:
    print('No')

Submission status: Runtime Error

Solution code:
def get(s):
    l=0
    k=len(s)
    i=0
    while i<k and s[i]==")":
        i+=1
    l=i
    if i==k:
        return l,0
    x=0
    for j in range(i,k):
        if s[j]=="(":
            x+=1
        else:
            x-=1
        if x<0:
            l+=1
            x=0
    return l,x
dic={}
n=int(input())
dic1={}
for i in range(n):
    s=input()
    l,r=get(s)
    if l==0 and r==0:
        continue
    while 1:
        if r in dic:
            if dic[r]:
                r=dic[r].pop()
            else:
                dic[l].append(r)
                break
        else:
            dic[l]=[r]
            break
k=0
for i in dic.values():
    k+=len(i)
if k==1:
    print("Yes")
else:
    print("No")

Submission status: Runtime Error

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 lr:
    if llst-rlst==0:
        print("Yes")
    else:
        print("No")
    exit()

idleR=10**7

def main(n,xl,xr):
    X=xl+idleR*xr
    if  not dp[n][X]:
        dp[n][X]=1
        stack.append([n,xl,xr])
L,R=lr[0]
dp=[defaultdict(int) for i in range(len(lr))]
main(0,L,R)
stack=[[0,L,R]]
while stack:
    n,l,r=stack.pop()
    if n+1<len(lr):
        L,R=lr[n+1]


        if L-r>=0:
            main(n+1,L-r+l,R)
        else:
            main(n+1,l,R-(L-r))

        if R-l>=0:
            main(n+1,L,r+R-l)
        else:
            main(n+1,L-(R-l),r)





    else:
        if l<=rlst:
            L=rlst-l
        else:
            continue
        if r<=llst:
            R=llst-r
        else:
            continue
        if L-R==0:
            print("Yes")
            exit()



print("No")

Submission status: Runtime Error

Solution code:
import sys
n=int(input())
lrp=[]
lrm=[]
def g(s):
    i = 0
    l = [0]
    for j in s:
        if j =="(":
            i += 1
        else:
            i -= 1
        l.append(i)
    return min(l),max(l)
for _ in range(n):
    s = input()
    l = s.count("(")
    r = len(s) - l
    mi,ma =g(s)
    if l>r:
        lrp.append((l,r))
    else:
        lrm.append((l,r))
    lr.append((mi,ma,l,r))
    
lrp.sort(key=lambda x:x[0])
lrm.sort(key=lambda x:-x[1])
lr=lrp+lrm
cnt = 0
for l,r in lr:
    cnt -= r
    if cnt >=0:
        cnt += l
    else:
        print("No")
        sys.exit()
if cnt !=0:
    print("No")
else:
    print("Yes")

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
s = [input() for _ in range(n)]
x = []
for i in range(n):
    cnt = 0
    for j in range(len(s[i])):
        if s[i][j] == '(':
            cnt += 1
        else:
            cnt -= 1
    x.append((cnt, s[i]))
x.sort(reverse=True)
x = deque(x)
tmp = deque()
stack = []
flag = False
while x:
    _, v = x.popleft()
    if v[0] == '(':
        flag = True
    if not flag:
        tmp.append(v)
    else:
        while tmp:
            _, u = tmp.popleft()
            for i in u:
                if i == '(':
                    stack.append('(')
                else:
                    if stack:
                        stack.pop()
                    else:
                        print('No')
                        quit()
        for i in v:
            if i == '(':
                stack.append('(')
            else:
                if stack:
                    stack.pop()
                else:
                    print('No')
                    quit()
if stack:
    print('No')
else:
    print('Yes')

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 Bit:
        def __init__(self, n):
            self.size = n
            self.tree = [0] * (n + 1)
    
        def sum(self, i):
            s = -(10 ** 18)  # -INF
            while i > 0:
                s = max(s, self.tree[i])
                i -= i & -i
            return s
    
        def add(self, i, x):
            while i <= self.size:
                self.tree[i] = max(x, self.tree[i])
                i += i & -i
    
    N=int(input())
    S=[input() for i in range(N)]
    P=0
    M=0
    c=0
    b=Bit(2*10**5+1)
    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()
        b.add(x,y)
    
    for _ in range(c):
        x=b.sum(P)
        if x==-INF:
            print('No')
            exit()
        if P-x<0:
            print('No')
            exit()
        
        l_PM[x].sort()
        
        index=bisect_right(l_PM,P)
        b.add(index,0)
        if stack[index]:
            y=stack[index].pop()
            b.add(index,y)
        P+=x
    P-=M
    YesNo(P==0)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n = int(input())
l = 0
r = 0
cntl = 0
cntr = 0
fl = 0
fr = 0
exl = 0
exr = 0
only_r = 0
only_l = 0
maxl = 0
maxr = 0
exlr = []
for i in range(n):
    s = input()
    templ = 0
    tempr = 0
    temp_exl = 0
    temp_exr = 0
    fl = 0
    fr = 0
    for i in s:
        if i == "(":
            tempr += 1
        elif i == ")":
            tempr -= 1
            if tempr < 0:
                tempr = 0
                templ += 1
                fl = 1
    temp_exl += templ
    if tempr > 0:
        temp_exr += tempr
        fr = 1
    if fl == 1 and fr == 0:
        only_l += temp_exl
    elif fr == 1 and fl == 0:
        only_r += temp_exr
    elif temp_exl + temp_exr > 0:
        exl += temp_exl
        exr += temp_exr
        exlr.append([temp_exl-temp_exr, temp_exl,temp_exr])
    # maxl = max(maxl,temp_exl)
    # maxr = max(maxr,temp_exr)
# print (exr,exl,only_r,only_l)
a = only_r
b = 0
exlr.sort()
exlr.sort(key=lambda x: x[1])

# print(exlr)
for i in range(len(exlr)):
    if exlr[i][1] <= a:
        a -= i[0]
        exlr[i] = [0,0,0]
for i in exlr:
    a -= i[1]
    if a<0:
        print("No")
        exit()
    a += i[2]
if exl+only_l == exr+only_r and exl-exr == only_r-only_l and only_l > 0 and only_r > 0:
    print("Yes")
elif exr+exl+only_l+only_r == 0:
    print("Yes")
else:
    print("No")

Submission status: Runtime Error

Solution code:
from copy import deepcopy
def abc():
    a=int(input())
    s=[]
    for i in range(a):
        s.append(input())
    return s
def isduplicate(li, n, t):
    """
    从li的位置n到位置t-1，有没有和li[t]相等的数字
    """
    while n < t:
        if li[n] == li[t]:
            return True
        n += 1
    return False


def swap(li, i, j):
    if i == j:
        return
    temp = li[j]
    li[j] = li[i]
    li[i] = temp


def permutation(li, size, n, result):
    """
    [n,size]位置的数字全排
    :param li:字符串数组
    :param size: 字符串长度
    :param n: 要交换的位置
    :param result: 保留结果
    :return:
    """

    if n == size - 1:
        result.append(deepcopy(li))
        return
    for i in list(range(n, size)):  # 分别把(size-n)个数字固定到位置n
        if isduplicate(li, n, i):  # 如果位置n出现过数字li[i]，跳过
            continue
        swap(li, i, n)  # 把s[n]和s[i]交换，把s[i]固定到位置n
        permutation(li, size, n + 1, result)  # [n+1,size-1]位置的数字全排
        swap(li, i, n)  # 把s[n]和s[i]交换回来
    
def check(s1):
    s=""
    for i in range(len(s1)):
        s+=s1[i]
    arr=[]
    
    for c in s:
        if c=="(":
            arr.append(c)
        elif c==")":
            if arr and arr[-1]=="(":
                arr.pop()
            else:
                return False
    return not arr
  
    
s=abc()
size=len(s)
n=0
result=[]
permutation(s, size, n, result)
for i in result:
 p=check(i)
 if(p!=False):
    print("Yes")
    break
if(p==False):
    print("No")

Submission status: Runtime Error

Solution code:
import sys
n=int(input())
lr=[]
def g(s):
    i = 0
    l = [0]
    for j in s:
        if j =="(":
            i += 1
        else:
            i -= 1
        l.append(i)
    return min(l),max(l)
for _ in range(n):
    s = input()
    l = s.count("(")
    r = len(s) - l
    l_sum += l
    r_sum += r
    mi,ma =g(s)
    lr.append((mi,ma,l,r))
    
cnt = 0
for mi,ma,l,r in lr:
    #print(cnt)
    if cnt+mi>=0:
        cnt += (l-r)
    else:
        print("No")
        sys.exit()
if cnt !=0:
    print("No")
else:
    print("Yes")

Submission status: Runtime Error

Solution code:
n = int(input())
l = 0
r = 0
cntl = 0
cntr = 0
fl = 0
fr = 0
exl = 0
exr = 0
only_r = 0
only_l = 0
maxl = 0
maxr = 0
exlr = [0,0,0]
for i in range(n):
    s = input()
    templ = 0
    tempr = 0
    temp_exl = 0
    temp_exr = 0
    fl = 0
    fr = 0
    for i in s:
        if i == "(":
            tempr += 1
        elif i == ")":
            tempr -= 1
            if tempr < 0:
                tempr = 0
                templ += 1
                fl = 1
    temp_exl += templ
    if tempr > 0:
        temp_exr += tempr
        fr = 1
    if fl == 1 and fr == 0:
        only_l += temp_exl
    elif fr == 1 and fl == 0:
        only_r += temp_exr
    elif temp_exl + temp_exr > 0:
        exl += temp_exl
        exr += temp_exr
        exlr.append([temp_exl-temp_exr, temp_exl,temp_exr])
    # maxl = max(maxl,temp_exl)
    # maxr = max(maxr,temp_exr)
# print (exr,exl,only_r,only_l)
a = only_r
b = 0
exlr.sort()
exlr = sorted(exlr, key=lambda x: x[1])

# print(exlr)
for i in range(len(exlr)):
    if exlr[i][1] <= a:
        a -= i[0]
        exlr[i] = [0,0,0]
for i in exlr:
    a -= i[1]
    if a<0:
        print("No")
        exit()
    a += i[2]
if exl+only_l == exr+only_r and exl-exr == only_r-only_l and only_l > 0 and only_r > 0:
    print("Yes")
elif exr+exl+only_l+only_r == 0:
    print("Yes")
else:
    print("No")

Submission status: Runtime Error

Solution code:
n = int(input())
l = 0
r = 0
cntl = 0
cntr = 0
fl = 0
fr = 0
exl = 0
exr = 0
only_r = 0
only_l = 0
maxl = 0
maxr = 0
exlr = []
for i in range(n):
    s = input()
    templ = 0
    tempr = 0
    temp_exl = 0
    temp_exr = 0
    fl = 0
    fr = 0
    for i in s:
        if i == "(":
            tempr += 1
        elif i == ")":
            tempr -= 1
            if tempr < 0:
                tempr = 0
                templ += 1
                fl = 1
    temp_exl += templ
    if tempr > 0:
        temp_exr += tempr
        fr = 1
    if fl == 1 and fr == 0:
        only_l += temp_exl
    elif fr == 1 and fl == 0:
        only_r += temp_exr
    elif temp_exl + temp_exr > 0:
        exl += temp_exl
        exr += temp_exr
        exlr.append([temp_exl-temp_exr, temp_exl,temp_exr])
    # maxl = max(maxl,temp_exl)
    # maxr = max(maxr,temp_exr)
# print (exr,exl,only_r,only_l)
a = only_r
b = 0
exlr.sort()
exlr = sorted(exlr, key=lambda x: x[1])

# print(exlr)
for i in range(len(exlr)):
    if exlr[i][1] <= a:
        a -= i[0]
        exlr[i] = [0,0,0]
for i in exlr:
    a -= i[1]
    if a<0:
        print("No")
        exit()
    a += i[2]
if exl+only_l == exr+only_r and exl-exr == only_r-only_l and only_l > 0 and only_r > 0:
    print("Yes")
elif exr+exl+only_l+only_r == 0:
    print("Yes")
else:
    print("No")

Submission status: Runtime Error

Solution code:
from collections import deque,defaultdict
import bisect
N = int(input())
S = [input() for i in range(N)]

class SegmentTree:
    def __init__(self,data,op,default):
        N = len(data)
        self.N = N
        self.op = op
        self.default = default
        self.l = 2**((N-1).bit_length())
        self.data = [default]*self.l + data + [default]*(self.l-N)
        for i in range(self.l-1,0,-1):
            self.data[i] = op(self.data[2*i], self.data[2*i+1])

    def set(self,i,val):
        i += self.l
        self.data[i] = val
        i = i//2
        while i > 0:
            self.data[i] = self.op(self.data[2*i], self.data[2*i+1])
            i = i//2

    def get(self,i,j):
        i += self.l
        j += self.l
        s = self.default 
        while j-i > 0:
            if i & 1:
                s = self.op(s,self.data[i])
                i += 1
            if j & 1:
                s = self.op(s,self.data[j-1])
                j -= 1
            i = i//2
            j = j//2
        return s

def bend(s):
    res = 0
    k = 0
    for th in s:
        if th == '(':
            k += 1
        else:
            k -= 1
        res = min(k,res)
    return res

LmR = defaultdict(list)
inf = -10**7
for s in S:
    LmR[bend(s)].append(s.count('(')-s.count(')'))
LmR = dict(LmR)
for k in LmR.keys():
    LmR[k].append(inf)
    LmR[k].sort(reverse=True)
    LmR[k] = deque(LmR[k])

keys = sorted(LmR.keys())
nk = len(keys)

comp = {k:i for i,k in enumerate(keys)}
seg = SegmentTree([(LmR[k].popleft(),k) for k in keys], lambda x,y : (x if x[0] > y[0] else y), (inf,inf))

cumsum = 0
for i in range(N):
    ind = bisect.bisect_left(keys,-cumsum)
    m,n = seg.get(ind-1,nk)
    if n == inf:
        print('No')
        exit()
    if cumsum + n < 0:
        print('No')
        exit()
    cumsum += m
    new = LmR[n].popleft()
    seg.set(comp[n], (new,n))

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

Submission status: Runtime Error

Solution code:
if __name__ == '__main__':
    l = []
    n = int(input())
    s = []
    for i in range(n):
        s.append(input())
    for string in s:
        top = -1
        sb = []
        for c in string:
            if len(sb) == 0:
                sb.append(c)
                top+=1
            else:
                if c == '(':
                    sb.append(c)
                    top+=1
                else:
                    if sb[top] == '(':
                        sb.pop()
                        top-=1
                    else:
                        sb.append(c)
        start = 0
        end = 0
        i = 0
        while i<len(sb) and sb[i] == ')':
            start+=1
            i+=1
        while i<len(sb) and sb[i] == '(':
            end+=1
            i+=1
        if start == 0 and end == 0:
            pass
        else:
            l.append((start,end))
    
    sz = False
    ez = False
    sums = 0
    sume = 0
    maxi = -1
    ele = -1
    for t in l:
        if t[0] == 0:
            sz = True
        if t[1] == 0:
            ez = True

        sums += t[0]
        sume += t[1]
        if t[0] == 0:
            ele = t[1]
            count+=1
        else:
            maxi = max(maxi,t[0])
    if not sz:
        print("No")
        exit()
    if not ez:
        print("No")
        exit()
    if count == 1:
        if ele > maxi:
            print("No")
            exit()
    if sums == sume:
        print("Yes")
    else:
        print("No")

Submission status: Runtime Error

Solution code:
input = raw_input

n = int(input())

def f(s):
    l = 0
    n = len(s)
    si = None
    for i in range(n):
        if s[i] == ")":
            l -= 1
        else:
            si = i
            break
    r = 0
    if si is None:
        pass
    else:
        for i in range(si, n):
            if s[i] == "(":
                r += 1
            else:
                r -= 1
    return l, r


ind = 0
pairs = []
ls = []
rs = []

sum_ls = [0, 0]
sum_rs = [0, 0]

sum_l_2 = 0
sum_r_2 = 0

nokori_l = 0
nokori_r = 0

def g1():
    ii = 0
    sum_l = sum_ls[ii]
    sum_r = sum_rs[ii]

    sum_l1 = sum_l
    sum_r1 = r
    mid1 = sum_r + l
    if mid1 < 0:
        sum_l1 += mid1
    else:
        sum_r1 += mid1

    sum_l2 = l
    sum_r2 = sum_r
    mid2 = r + sum_l
    if mid2 < 0:
        sum_l2 += mid2
    else:
        sum_r2 += mid2

    if sum_r2 <= sum_r1:
        sum_l = sum_l2
        sum_r = sum_r2
    else:
        sum_l = sum_l1
        sum_r = sum_r1
    sum_ls[ii] = sum_l
    sum_rs[ii] = sum_r

def g2():
    ii = 1
    sum_l = sum_ls[ii]
    sum_r = sum_rs[ii]

    sum_l1 = sum_l
    sum_r1 = r
    mid1 = sum_r + l
    if mid1 < 0:
        sum_l1 += mid1
    else:
        sum_r1 += mid1

    sum_l2 = l
    sum_r2 = sum_r
    mid2 = r + sum_l
    if mid2 < 0:
        sum_l2 += mid2
    else:
        sum_r2 += mid2

    #if sum_r2 <= sum_r1:
    if sum_r2 < sum_r1:
        sum_l = sum_l2
        sum_r = sum_r2
    else:
        sum_l = sum_l1
        sum_r = sum_r1
    sum_ls[ii] = sum_l
    sum_rs[ii] = sum_r


for i in range(n):
    s = input()
    l, r = f(s)
    if l == 0 and r == 0:
        continue
    elif l != 0 and r != 0:
        g1()
        g2()
    else:
        if l != 0:
            nokori_l += l
        else:
            nokori_r += r

flag = False
for i in range(2):
    sum_l = sum_ls[i]
    sum_r = sum_ls[r]
    right_side = sum_r + nokori_l
    left_side = nokori_r + sum_l

    if left_side >= 0 and right_side <= 0:
        if left_side + right_side == 0:
            flag = True

if flag:
    print("Yes")
else:
    print("No")

Submission status: Runtime Error

Solution code:
def ques():
    n=input()
    open=0
    close=0
    lis=[]
    for _ in range(int(n)):
        co=0
        cc=0
        t=input()
        for i in t:
            if i=="(":
                co+=1
            if i==")":
                if co>=1:
                    co-=1
                else:
                    cc+=1
        if (co,cc)!=(0,0):
            lis.append((cc,co))
    # print(lis)
    if not lis:
        print("Yes")
        return
    lis.sort()
    curr_open=0
    i=0
    while(i<=len(lis) and lis[i][0]==0):
        curr_open+=lis[i][1]
        i+=1
    if curr_open==0:
        print("No")
        return
    while(i<len(lis) and curr_open>0):
        curr_open-=lis[i][0]
        if curr_open<0:
            print("No")
            return
        curr_open+=lis[i][1]
        i+=1
    if curr_open==0:
        print("Yes")
    else:
        print("No")
ques()

Submission status: Runtime Error

Solution code:
N = int(input())
s = [input() for i in range(N)]
S = [[0]*len(s[i]) for i in range(N)]
for i, x in enumerate(s):
    res = []
    q = 0
    for j in range(len(x)):
        if x[j] == ')':
            S[i][j] = -1
        else:
            S[i][j] = 1
s = [0]*N
m = [len(S[i]) for i in range(N)]
for i, x in enumerate(S):
    tmp = 0
    for j in range(len(x)):
        tmp += S[i][j]
        m[i] = min(tmp, m[i])
    s[i] = tmp
if sum(s) == 0:
    ss = [m[i], s[i]) for i in range(N)]
    ss.sort(key=lambda x: (x[1], x[2]), reverse=True)
    tmp = 0
    for x,y in ss:
        for z in x:
            if tmp + x < 0:
                print("No")
                exit(0)
            tmp += y
                    
    print("Yes")

else:
    print("No")