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:
import sys,bisect,string,math,time,functools,random,fractions
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
def Golf():*a,=map(int,open(0))
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if len(inp)==2:
            a,b=inp;c=1
        else:
            a,b,c=inp
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1) # sample usage
    mp=[boundary]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def bit_combination(n,base=2):
    rt=[]
    for tb in range(base**n):s=[tb//(base**bt)%base for bt in range(n)];rt+=[s]
    return rt
def gcd(x,y):
    if x%y==0:return y
    while x%y!=0:x,y=y,x%y
    return y
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
FourNb=[(1,0),(-1,0),(0,1),(0,-1)];EightNb=[(1,0),(-1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('EWNS',FourNb))
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
input=lambda: sys.stdin.readline().rstrip()

class Tree:
    def __init__(self,inp_size=None,ls=None,init=True,index=0):
        self.LCA_init_stat=False
        self.ETtable=[]
        if init:
            if ls==None:
                self.stdin(inp_size,index=index)
            else:
                self.size=len(ls)+1
                self.edges,_=GI(self.size,self.size-1,ls,index=index)
        return

    def stdin(self,inp_size=None,index=1):
        if inp_size==None:
            self.size=int(input())
        else:
            self.size=inp_size
        self.edges,_=GI(self.size,self.size-1,index=index)
        return
    
    def listin(self,ls,index=0):
        self.size=len(ls)+1
        self.edges,_=GI(self.size,self.size-1,ls,index=index)
        return

    def __str__(self):
        return  str(self.edges)

    def dfs(self,x,func=lambda prv,nx,dist:prv+dist,root_v=0):
        q=deque()
        q.append(x)
        v=[-1]*self.size
        v[x]=root_v
        while q:
            c=q.pop()
            for nb,d in self.edges[c]:
                if v[nb]==-1:
                    q.append(nb)
                    v[nb]=func(v[c],nb,d)
        return v

    def EulerTour(self,x):
        q=deque()
        q.append(x)
        self.depth=[None]*self.size
        self.depth[x]=0
        self.ETtable=[]
        self.ETdepth=[]
        self.ETin=[-1]*self.size
        self.ETout=[-1]*self.size
        cnt=0
        while q:
            c=q.pop()
            if c<0:
                ce=~c
            else:
                ce=c
                for nb,d in self.edges[ce]:
                    if self.depth[nb]==None:
                        q.append(~ce)
                        q.append(nb)
                        self.depth[nb]=self.depth[ce]+1
            self.ETtable.append(ce)
            self.ETdepth.append(self.depth[ce])
            if self.ETin[ce]==-1:
                self.ETin[ce]=cnt
            else:
                self.ETout[ce]=cnt
            cnt+=1
        return
    
    def LCA_init(self,root):
        self.EulerTour(root)
        self.st=SparseTable(self.ETdepth,init_func=min,init_idl=inf)
        self.LCA_init_stat=True
        return
    
    def LCA(self,root,x,y):
        if self.LCA_init_stat==False:
            self.LCA_init(root)
        xin,xout=self.ETin[x],self.ETout[x]
        yin,yout=self.ETin[y],self.ETout[y]
        a=min(xin,yin)
        b=max(xout,yout,xin,yin)
        id_of_min_dep_in_et=self.st.query_id(a,b+1)
        return self.ETtable[id_of_min_dep_in_et]

class SparseTable: # O(N log N) for init, O(1) for query(l,r)
    def __init__(self,ls,init_func=min,init_idl=float('inf')):
        self.func=init_func
        self.idl=init_idl
        self.size=len(ls)
        self.N0=self.size.bit_length()
        self.table=[ls[:]]
        self.index=[list(range(self.size))]
        self.lg=[0]*(self.size+1)
        
        for i in range(2,self.size+1):
            self.lg[i]=self.lg[i>>1]+1

        for i in range(self.N0):
            tmp=[self.func(self.table[i][j],self.table[i][min(j+(1<<i),self.size-1)]) for j in range(self.size)]
            tmp_id=[self.index[i][j] if self.table[i][j]==self.func(self.table[i][j],self.table[i][min(j+(1<<i),self.size-1)]) else self.index[i][min(j+(1<<i),self.size-1)] for j in range(self.size)]
            self.table+=[tmp]
            self.index+=[tmp_id]
    
    # return func of [l,r)
    def query(self,l,r):
        if r>self.size:r=self.size
        #N=(r-l).bit_length()-1
        N=self.lg[r-l]
        return self.func(self.table[N][l],self.table[N][r-(1<<N)])
    
    # return index of which val[i] = func of v among [l,r)
    def query_id(self,l,r):
        if r>self.size:r=self.size
        #N=(r-l).bit_length()-1
        N=self.lg[r-l]
        a,b=self.index[N][l],self.index[N][r-(1<<N)]
        if self.table[0][a]==self.func(self.table[N][l],self.table[N][r-(1<<N)]):
            b=a
        return b
    
    def __str__(self):
        return str(self.table[0])

    def print(self):
        for i in self.table:
            print(*i)

class Comb:
    def __init__(self,n,mo=10**9+7):
        self.fac=[0]*(n+1)
        self.inv=[1]*(n+1)
        self.fac[0]=1
        self.fact(n)
        for i in range(1,n+1):
            self.fac[i]=i*self.fac[i-1]%mo
            self.inv[n]*=i
            self.inv[n]%=mo
        self.inv[n]=pow(self.inv[n],mo-2,mo)
        for i in range(1,n):
            self.inv[n-i]=self.inv[n-i+1]*(n-i+1)%mo
        return
    
    def fact(self,n):
        return self.fac[n]
        
    def invf(self,n):
        return self.inv[n]

    def comb(self,x,y):
        if y<0 or y>x:
            return 0
        return self.fac[x]*self.inv[x-y]*self.inv[y]%mo

show_flg=False
show_flg=True
ans=0

mo=998244353

n=I()
b=[]
L,R=0,0
for i in range(n):
    s=S_()
    ns=len(s)
    a=[0]
    m,M=0,0
    l,r=0,0
    lv=0
    for j in s:
        if j=='(':
            lv+=1
            l+=1
            x=a[-1]+1
            a+=[a[-1]+1]
            if M<x:
                M=x
        else:
            lv-=1
            r+=1
            x=a[-1]-1
            a+=[a[-1]-1]
            if m>x:
                m=x
    y=( (M)*10**7+m*10**14+m,lv,l,r,m,M)
    #b+=[(l,r,m,M,s)]
    b+=[y]
    L+=l
    R+=r

fl=True

if L!=R:
    fl=False
    
b.sort(key=lambda x:-x[0])

x=0

for i in b:
    sc,lv,l,r,m,M=i
    if x+m<0:
        fl=False
        
    x+=lv

#    print(i)

if x==0:
    fl=fl and True
    

print(Yn[not fl])

Submission status: Wrong Answer

Solution code:
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 a == b:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
import sys

N = int(input())
left = 0
right = 0
mid_right = 0
mid_left = 0
mid = 0

for _ in range(N):
	s = input()
	L = len(s)
	while True:
		s = s.replace('()', '')
		tmp = len(s)
		if tmp == L:
			break
		else:
			L = tmp
	
	if s:
		if L == 1:
			if s == '(':
				left += 1
			else:
				right += 1
		elif L > 1:
			if s[0] == s[-1]:
				if s[0] == '(':
					left += L
				else:
					right += L
			else:
				mid = 1
				for i in range(L):
					if s[i] == '(':
						mid_right += i
						mid_left += (L - i)
						break

if mid:
	if (right == 0) or (left == 0):
		print('No')
	else:
		if (mid_left + left) == (mid_right + right):
			print('Yes')
		else:
			print('No')
else:
	if right == left:
		print('Yes')
	else:
		print('No')

Submission status: Wrong Answer

Solution code:

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


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()
if sum(item[1] for item in minsum)!=0:
    print("No")
else:
    c = 0
    i = n-1
    while minsum:
        m, s = minsum[i]
        if m<0:
            break
        c += s
        i -= 1
        minsum.pop()
    if not minsum:
        print("Yes")
    else:
#         minsum.sort(key=lambda x: x[1])
    #     print(minsum, c)
        i = len(minsum)-1
        update = False
        for i in range(len(minsum)):
            m, s = minsum[i]
            if c+m>=0:
                c += s
            else:
                print("No")
                break
        else:
            print("Yes")

Submission status: Wrong Answer

Solution code:
N=int(input())

slist=[]
for _ in range(N):
  s=input()
  while True:
    s_new=s.replace("()","")
    #print(s,s_new)
    if s_new==s:
      s=s_new
      break
    else:
      s=s_new
  slist.append(s)
print(slist)

rl_list=[]
for i in range(N):
  s=slist[i]
  l=s.count("(")
  r=s.count(")")
  if l>0 or r>0:
    rl_list.append((l-r,l,r))
rl_list.sort(reverse=True)
#print(rl_list)
  
lsum=rsum=0
lmin=rmin=float("inf")
l0max=r0max=0
for lr,r,l in rl_list:
  rsum+=r
  lsum+=l
  lmin=min(lmin,l)
  rmin=min(rmin,r)
  if l==0:
    l0max=max(l0max,r)
  if r==0:
    r0max=max(r0max,l)
  
if rsum!=lsum:
  print("No")
elif rmin>0 or lmin>0:
  print("No")
else:
  #print(l0max,r0max)
  if r0max>=rl_list[0][1]:
    print("Yes")
  else:
    print("No")

Submission status: Wrong Answer

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))

from collections import defaultdict, deque
from sys import exit
import math
import copy
from bisect import bisect_left

import sys
# sys.setrecursionlimit(1000000)
INF = 10 ** 17
MOD = 998244353

def main():
    n = getN()
    al, ar = 0, 0
    kakkos = []
    for i in range(n):
        s = input().strip()
        q = deque()
        l, r = 0, 0
        for c in s:
            if c == "(":
                r += 1
            else:
                if r == 0:
                    l += 1
                else:
                    r -= 1
        kakkos.append([l, r])
    # kakkos = list(sorted(kakkos))
    kakkos.sort(key=lambda x: x[0])
    kakkos.sort(key=lambda x: -x[1])
    if kakkos[0][0] != 0:
        print("No")
        return
    # print(kakkos)
    tr = kakkos[0][1]
    for cl, cr in kakkos[1:]:
        if cl > tr:
            print("No")
            return
        tr = (tr - cl) + cr

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

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
ls = [0] * N
rs = [0] * N
t = 0
for x in range(N):
  S = list(input())[: -1]
  for i in range(len(S)):
    if S[i] == "(":
      t += 1
      rs[x] += 1
    if S[i] == ")":
      t -= 1
      if rs[x]: rs[x] -= 1
      else: ls[x] += 1
if t:
  print("No")
  exit(0)
if sum(ls) == 0:
  print("Yes")
  exit(0)
l = 0
r = 0
for i in range(N):
  if ls[i] == 0 and (rs[i] > 0): l = 1
  if rs[i] == 0 and (ls[i] > 0): r = 1
if l & r:
  print("Yes")
else: print("Yes")

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
si = []
for _ in range(n):
    s = input().strip()
    l = 0
    r = 0
    count = 0
    for i in range(len(s)):
        if s[i] == "(":
            count += 1
        else:
            count = max(0, count-1)
    l = count
    count = 0
    for i in range(len(s)-1, -1, -1):
        if s[i] == ")":
            count += 1
        else:
            count = max(0, count-1)
    r = count
    si.append((l, r))

if len(si) == 1:
    if si[0] == (0, 0):
        print("Yes")
        sys.exit()

index_l = -1
index_r = -1
maxi_l = 0
maxi_r = 0
for i in range(n):
    a, b = si[i]
    if a == 0:
        if maxi_l < b:
            maxi_l = b
            index_l = i
    if b == 0:
        if maxi_r < a:
            maxi_r = a
            index_r = i

if index_l == -1 or index_r == -1:
    print("No")
    sys.exit()

count = 0
if index_r < index_l:
    count += si.pop(index_l)[1]
    last = si.pop(index_r)
else:
    last = si.pop(index_r)
    count += si.pop(index_l)[1]

from heapq import *
c = [[] for i in range(10**6+1)]
for i, j in si:
    c[i].append(j-i)
ind = count
use = 0
q = []
for i in range(count):
    for j in c[i]:
        heappush(q, -j)
        use += 1
while q:
    now = -q.pop()
    count += now
    ind += now
    if now > 0:
        for i in range(ind-now+1, ind+1):
            for j in c[i]:
                heappush(q, -j)
                use += 1

count -= last[0]

if count == 0 and use == n-2:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
n = int(input())
a, b = 0, 0
c = 0
cnt1 = [0, 0]
xx, yy = 0, 0
for _ in range(n):
    s = list(input())
    l = len(s)
    cnt0 = [0, 0]
    for i in s:
        if i == ")":
            cnt0[0] += 1
        else:
            cnt0[1] += 1
    if cnt0[0] > cnt0[1]:
        yy -= (cnt0[0] - cnt0[1])
    elif cnt0[0] < cnt0[1]:
        xx -= (cnt0[1] - cnt0[0])
    cnt1[0] += cnt0[0]
    cnt1[1] += cnt0[1]
    if not s[0] == ")":
        m = 0
        x = 0
        for i in range(l):
            if s[i] == "(":
                x += 1
            else:
                x -= 1
            m = max(x, m)
            if x < 0:
                break
        if x > 0:
            a += 1
        if m == l // 2 and x == 0:
            c += 1
    elif s[l - 1] == "(":
        u, v = 0, 0
        for i in range(l):
            if s[i] == ")":
                u += 1
                u -= v
                v = 0
            else:
                v += 1
        xx += max(0, u)
    if not s[l - 1] == "(":
        y = 0
        for i in range(l):
            if s[l - i - 1] == ")":
                y += 1
            else:
                y -= 1
            if y < 0:
                break
        if y > 0:
            b += 1
    elif s[0] == ")":
        u, v = 0, 0
        for i in range(l):
            if s[l - i - 1] == "(":
                u += 1
                u -= v
                v = 0
            else:
                v += 1
        yy += max(0, u)
print("Yes" if (cnt1[0] == cnt1[1] and a > 0 and b > 0 and xx <= 0 and yy <= 0) or (c == n) else "No")

Submission status: Wrong Answer

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

n = int(input())
sn = [input().strip() for _ in range(n)]

ls = [0, 0]
for i in sn:
    count = 0
    
    for j in i:
        if j == '(':
            count += 1
        else:
            count -= 1
        
        if count < 0:
            ls[1] += 1
            count = 0
    
    ls[0] += count
    
if ls[0] == ls[1]:
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

def main():  
    N = int(input())
    flag1 = False
    flag2 = False
    left = 0
    left2 = []
    right = 0
    right2 = []
    for _ in range(N):
        s = input()
        stack = ['-']
        for t in s:
            if t == '(':
                stack.append(t)
            else:
                if stack[-1] == '(':
                    stack.pop()
                else:
                    stack.append(')')
        if len(stack) == 1:
            continue
        elif stack[1] == '(':
            flag1 = True
            left += len(stack) - 1
        elif len(stack) >= 3  and stack[1] == ')' and stack[-1] == '(':
            for i in range(len(stack)):
                if stack[i] == '(':
                    s = i
                    break
            left2.append(len(stack) - s)
            right2.append(s - 1)
        else:
            flag2 = True
            right += len(stack) - 1
    if (right == 0 and left == 0 and  right2 == 0 and left2 == 0):
        print('Yes')
    else:
        l = 0
        if len(left2) > 0:
            l = min(left2)
        r = 0
        if len(right2) > 0:
            r = min(right2)
        x = min(r,l)
        if flag1 and flag2 and (right + sum(right2) == left + sum(left2)) and (left >= x) and (right >= x):
            print('Yes')
        else:
            print('No')
if __name__ == '__main__':
    main()

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(key=lambda x:(-x[0],-x[1]))
    k = 0
    for m,p in s:
        if k+m < 0:
            print("No")
            return
        k += p
    if k > 0:
        print("No")
    else:
        print("Yes")
    return

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

Submission status: Wrong Answer

Solution code:
import sys

pos, neg = [], []
n = int(input())
for i in range(n):
    s = input()
    bal = 0
    min_bal = 0
    for c in s:
        bal += 1 if c == '(' else -1
        min_bal = min(bal, min_bal)

    if bal > 0:
        pos.append((min_bal, bal))
    else:
        neg.append((min_bal, bal))

pos.sort(reverse=True) #hi to lo min_bal, hi to lo bal
neg.sort(key = lambda p: (-p[1], p[0]))#  lo to hi bal, hi to lo min_bal

cur = 0
for m, e in pos:
    if cur + m < 0:
        print("No")
        sys.exit()

    cur += e

for m, e in neg:
    if cur + m < 0:
        print("No")
        sys.exit()

    cur += e

print("Yes" if cur == 0 else "No")

Submission status: Wrong Answer

Solution code:
N = int(input())
S = [list(input()) for i in range(N)]
check1 = 0
check2 = 0

LEFT = [0]*N
RIGHT = [0]*N


for i in range(N):
    right=0
    left=0
    
    for j in S[i]:
        if j == ")":
            if left>0:
                left -= 1
            else:
                right += 1
        else:
            left += 1
    LEFT[i]+=left
    RIGHT[i]+=right
    
    if right==0 and left>0:
        check1 += 1

    if right>0 and left==0:
        check2 += 1

        
if sum(RIGHT) == sum(LEFT) and check1>0 and check2>0:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
def check(pt, brackets):
    brackets.sort(reverse=True)
    for m, t in brackets:
        if pt + m < 0:
            return False
        pt += t
    return pt


n = int(input())
brackets_p = []  # (始めを0として、( = +1, ) = -1 として、最後はいくつか, 途中の最小値はいくつか)
brackets_m = []
pt = 0
mt = 0
for _ in range(n):
    s = input()
    total = 0
    mini = 0
    for c in s:
        if c == '(':
            total += 1
        else:
            total -= 1
            mini = min(mini, total)

    if total >= 0:
        if mini == 0:
            pt += total
        else:
            brackets_p.append((mini, total))
        continue

    total = 0
    mini = 0
    for c in s[::-1]:
        if c == ')':
            total += 1
        else:
            total -= 1
            mini = min(mini, total)

    if mini == 0:
        mt += total
    else:
        brackets_m.append((mini, total))

pt = check(pt, brackets_p)
mt = check(mt, brackets_m)

if pt == False or mt == False or pt != mt:
    print('No')
else:
    print('Yes')

Submission status: Wrong Answer

Solution code:
import heapq

N = int(input())
S = list(input() for _ in range(N))
X = []
for s in S:
    l,r = 0,0
    for c in s:
        if c == ")":
            if r > 0:
                r -= 1
            else:
                l += 1
        else:
            r += 1
    X.append([l,r])
X.sort(key = lambda x:x[0])
Y = []
L = 0
for p in range(N):
    if X[p][0] > L:
        print("No)")
        quit()
    if X[p][1] >= X[p][0]:
        L -= X[p][0]
        L += X[p][1]
    else:
        Y.append(X[p][:])
Y.sort(key = lambda x:-x[1])
for a,b in Y:
    if a > L:
        print("No")
        quit()
    L -= a
    L += b
if L:
    print("No")
else:
    print("Yes")

Submission status: Wrong Answer

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

for i, x in enumerate(S):
    res = []
    q = 0
    for y in x:
        if y == ')':
            if q > 0:
                q -= 1
            else:
                res.append(y)
        else:
            q += 1
    res += ['(']*q
    S[i] = list(res)
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)):
        if x[j] == '(':
            tmp += 1
        else:
            tmp -= 1
        m[i] = min(tmp, m[i])
    s[i] = tmp

if sum(s) == 0:
    ss = [(S[i], m[i]) for i in range(N)]
    tmp = 0
    for x, y in ss:
        for z in x:
            if z == '(':
                tmp += 1
            else:
                tmp -= 1
                if tmp < 0:
                    print("No")
                    exit(0)
    print("Yes")

else:
    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()
double.sort(key=lambda x:x[0]-x[1])
now = left
for a,b in double:
    if now < a:
        print("No")
        exit()
    now += (b-a)
print("Yes")

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-


def main():
  values = []
  total = 0

  for _ in range(int(input())):
    s = input().strip()
    open_required = len(s)
    close_required = len(s)
    open_close = 0

    for i, c in enumerate(s):
      if c == '(':
        open_required = min(i, open_required)
        open_close += 1
      else:
        close_required = min(len(s) - i - 1, close_required)
        open_close -= 1

    total += open_close
    values.append([open_required, close_required, open_close, 0])

  if total != 0:
    print('No')
    return
  
  if len(values) > 200000:
    print('No')
    return

  fvals = values.copy()
  bvals = values

  fvals.sort(key=lambda x: (x[0], -x[2]))
  bvals.sort(key=lambda x: (x[1], x[2]))

  findex = 0
  bindex = 0

  while True:
    while findex < len(fvals) and fvals[findex][3] != 0:
      findex += 1

    while bindex < len(bvals) and bvals[bindex][3] != 0:
      bindex += 1

    if findex >= len(fvals) and bindex >= len(bvals):
      break

    fvals[findex][3] = 1
    bvals[bindex][3] = -1

  values = [v for v in fvals if v[3] == 1] + [v for v in bvals if v[3] == -1][::-1]

  open_close_f = 0
  open_close_b = 0

  for (oreq_f, _, ocval_f, _), (_, creq_b, ocval_b, _) in zip(values, values[::-1]):
    if oreq_f > open_close_f:
      print('No')
      return

    if creq_b > open_close_b:
      print('No')
      return

    open_close_f += ocval_f
    open_close_b -= ocval_b

  print('Yes')


if __name__ == '__main__':
  main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
import sys
sys.setrecursionlimit(10**9)
from collections import deque
import heapq
from itertools import combinations
import bisect

n=int(input())
l=[]
for i in range(n):
    l.append(list(input()))

p=0
q=0
for i in range(n):
    for j in l[i]:
        if j=='(':
            p+=1
        else:
            q+=1
if p!=q:
    print('No')
    exit()
pl=[]
ql=[]
ml=[]
for i in range(n):
    a=l[i]
    p=0
    q=0
    for j in a:
        if j=='(':
            p+=1
        else:
            q+=1
    if p>q:
        pl.append(a)
    elif p<q:
        ql.append(a)
    else:
        ml.append(a)
# if pl:
#     pl.sort()
# if ql:
#     ql.sort()
# if ml:
#     ml.sort()
# if pl:
#     if pl[0][0]==')':
#         print('No')
#         exit()
# else:
#     if ml[0][0]==')':
#         print('No')
#         exit()

# if ql:
#     if ql[-1][-1]=='(':
#         print('No')
#         exit()
# else:
#     if ml[-1][-1]=='(':
#         print('No')
#         exit()


if pl:
    pp=[]
    for i in pl:
        d=0
        t=0
        for j in i:
            if j=='(':
                d+=1
            else:
                d-=1
            t=max(t,-d)
        pp.append([t,d])
    pp.sort(key=lambda x: x[0]*(10**6)-x[1])
    d=0
    for a,b in pp:
        if d<a:
            print('No')
            exit()
        d+=b-a
if ql:
    pp=[]
    for i in ql:
        d=0
        t=0
        for j in range(len(i)):
            if i[len(i)-1-j]==')':
                d+=1
            else:
                d-=1
            t=max(t,-d)
        pp.append([t,d])
    pp.sort(key=lambda x: x[0]*(10**6)-x[1])
    d=0
    for a,b in pp:
        if d<a:
            print('No')
            exit()
        d+=b-a

if ml:
    pp=[]
    for i in ml:
        d=0
        t=0
        for j in i:
            if j=='(':
                d+=1
            else:
                d-=1
            t=max(t,-d)
        pp.append([t,d])
    pp.sort(key=lambda x: x[0]*(10**6)-x[1])
    d=0
    for a,b in pp:
        if d<a:
            print('No')
            exit()
        d+=b-a
if ml:
    pp=[]
    for i in ml:
        d=0
        t=0
        for j in range(len(i)):
            if i[len(i)-1-j]==')':
                d+=1
            else:
                d-=1
            t=max(t,-d)
        pp.append([t,d])
    pp.sort(key=lambda x: x[0]*(10**6)-x[1])
    d=0
    for a,b in pp:
        if d<a:
            print('No')
            exit()
        d+=b-a


print('Yes')

Submission status: Wrong Answer

Solution code:
import heapq

N=int(input())
S = [input() for _ in range(N)]
p1 = 0
p2 = []
p3 = []
for i,s in enumerate(S):
    depth = 0
    max_depth = 0
    min_depth = 0
    for chr in s:
        if chr=='(':
            depth += 1
            if depth > max_depth:
                max_depth = depth
        else:
            depth -= 1
            if depth < min_depth:
                min_depth = depth
    if depth >= 0 and min_depth >= 0:
        p1 += depth
    elif depth >= 0:
        p2.append((min_depth,depth))
    else:
        p3.append((min_depth,depth))
pp2 = sorted(p2,reverse=True)
pp3 = sorted(p3,reverse=True)
# print(p1)
# print(p2)
# print(p3)

depth = p1
for p in pp2:
    if depth+p[0] < 0:
        print('No')
        exit()
    depth += p[1]
for p in pp3:
    if depth+p[0] < 0:
        print('No')
        exit()
    depth += p[1]
if depth != 0:
    print('No')
else:
    print('Yes')