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 math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    N = I()
    landr = []
    lonly = 0
    ronly = 0
    for i in range(N):
        t = S()
        left = 0
        right = 0
        for c in t:
            if c == '(':
                left += 1
            else:
                if left > 0:
                    left -= 1
                    continue
                else:
                    right += 1
        if left == 0 and right > 0:
            ronly += right
        if left > 0 and right == 0:
            lonly += left
        if left > 0 and right > 0:
            landr.append((left, right))
        if left == 0 and right == 0:
            continue

    if landr == []:
        if lonly == ronly:
            print("Yes")
        else:
            print("No")
        return
    f = landr[0]
    fl, fr = f[0], f[1]
    if len(landr) == 1:
        if fr == landr[0] and fl == landr[1]:
            print("Yes")
        else:
            print("No")
        return

    for i in range(1, len(landr)):
        elem = landr[i]
        left, right = elem
        newl, newr = 0, 0
        if fr > left:
            fr -= left
            newl = fl
            newr = fr + right
        else:
            left -= fr
            newl = fl + left
            newr = right
        fl = newl
        fr = newr
        if fl == lonly and fr == ronly:
            print("Yes")
        else:
            print("No")

main()

Submission status: Wrong Answer

Solution code:
n = int(input())
s = [input() for i in range(n)]
left = 0
right = 0
kakko = []
for i in s:
  now = 0
  tmp = len(i)
  for j in i:
    if j == "(":
      left += 1
      now += 1
    else:
      right += 1
      now -= 1
      tmp = min(tmp,now)
  kakko.append(tmp)
if left == right:
  if sum(kakko) >= 0:
    print("Yes")
  else:
    print("No")
else:
  print("No")

Submission status: Wrong Answer

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

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

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

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

print("Yes")

Submission status: Wrong Answer

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=list(map(list,zip(s,t)))

for i in range(n):
    now,mi=0,0
    for j in st[i][0]:
        if j=="(":
            now+=1
        else:
            now-=1
        mi=min(mi,now)
    st[i].append(mi)
st.sort(reverse=True,key=lambda z:z[1])
st.sort(reverse=True,key=lambda z:z[2])
now2=0
for i in range(n):
    if now2+st[i][2]<0:
        print("No")
        break
    now2+=st[i][1]
else:
    print("Yes")

Submission status: Wrong Answer

Solution code:
def main():

    N = int(input())
    S = []
    pos = []
    neg1 = []
    neg2 = []
    tot_v = 0
    for _ in range(N):
        t = input()
        S.append(t)
        v = 0
        min_v = float('inf')
        for c in t:
            if c == '(': v += 1
            else: v -= 1
            min_v = min(min_v, v)
        tot_v += v
        if min_v >=0:
            pos.append([min_v, v])
        else:
            if v > 0:
                neg1.append([min_v, v])
            else:
                neg2.append([min_v, v])

    if tot_v !=  0: return "No"

    u = 0
    for _, v in pos:
        u += v

    k = 0
    for _, v in neg1:
        k += v

    for min_v, v in neg1:
        if u + k - v + min_v < 0:
            return "No"

    u += k

    for min_v, v in neg2:
        if u + min_v < 0:
            return "No"
        else:
            u += v

    return "Yes"


if __name__ == '__main__':
    print(main())

Submission status: Wrong Answer

Solution code:
# あらかじめ前処理すれば、
# 1: (((...
# 2: )))...
# 3: ...)(((..
# のいずれかの形式に出来る
# typeでソートして、1, 3, 2の形にして解決していけるかを調べれば良さそう？
# "))(", ")))((("とかが険しい
# ほんまか？なんかいけそう
import sys
input = lambda: sys.stdin.readline().rstrip()
sys.setrecursionlimit(20000000)

def remove(s):
    while True:
        if len(s) <= 0:
            break
        pre_len = len(s)
        s = s.replace("()", "")
        if len(s) == pre_len:
            break
    return s

n = int(input())
s = [[], [], []]
for i in range(n):
    s_ = remove(input())
    t1 = s_.count("(")
    t2 = s_.count(")")
    if t1 > 0 and t2 > 0:
        s[1].append(s_)
    elif t1 > 0:
        s[0].append(s_)
    else:
        s[2].append(s_)
for i in range(3):
    s[i] = "".join(s[i])

s = "".join(s)
s = remove(s)
if len(s) == 0:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
import sys

def read():
    return sys.stdin.readline().rstrip()

def main():
    n = int(read())
    s = []
    al, ar = 0, 0
    for _ in range(n):
        l, r, d = 0, 0, 0
        for si in read():
            if si == "(":
                l += 1
            if si == ")":
                r += 1
                d = min(l - r, d)
        if l != r or d < 0:
            al += l
            ar += r
            s.append((l, r, d))
    if al != ar:
        print("No")
        return
    cl, cr = 0, 0
    for l, r, d in sorted(s, key=lambda x: x[1] - x[0]):
        if cl - cr + d < 0:
            print("No")
            break
        cl += l
        cr += r
    else:
        print("Yes")

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys


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


def calc(S):
    tmp = 0
    MIN = 0
    for s in S:
        if s == "(":
            tmp += 1
        else:
            tmp -= 1
        MIN = min(tmp, MIN)

    return MIN, tmp


cnts = []
for s in ss:
    down, up = calc(s)
    if up > 0:
        cnts.append((1, -down, up, s))
    elif up == 0:
        cnts.append((0, -down, up, s))
    else:
        cnts.append((-1, -down, up, s))

cnts.sort(reverse=True)
# print(cnts)

tmp = 0
for f, d, u, _ in cnts:
    if tmp - d < 0:
        print("No")
        sys.exit()

    tmp += u

    if tmp < 0:
        print("No")
        sys.exit()


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

Submission status: Wrong Answer

Solution code:
import networkx as nx

N = input().split()
A = list(map(str, input().split()))

I = list()
O = list()
for s in A:
  a = 0
  for c in s:
    if(c==')'):
      ++a
    else:
      --a
  I.append(a)
  a = 0
  for c in reversed(s):
    if(c=='('):
      ++a
    else:
      --a
  O.append(a)

if nx.algorithms.graphical.is_digraphical(I, O):
  print("Yes")
else:
  print("No")

Submission status: Wrong Answer

Solution code:
n = int(input())
l = 0
r = 0
cntl = 0
cntr = 0
f = 0
exl = 0
exr = 0
for i in range(n):
    s = input()
    templ = 0
    tempr = 0
    f = 0
    for i in s:
        if i == "(":
            tempr += 1
        elif i == ")":
            templ += 1
            tempr -= 1
            if tempr < 0:
                tempr = 0
                templ = 0
                exl += 1
                if f == 0:
                    cntl += 1
                    f = 1
    if tempr > 0:
        exr += tempr
        if f == 0:
            cntr += 1
# print (exr,exl,cntl,cntr)
if exr == exl and cntl + cntr >= 2:
    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
        done = [False] * len(minsum)
        for i in range(len(minsum)):
            m, s = minsum[i]
            if s<0:
                continue
            if c+m>=0:
                c += s
                done[i] = True
        for i in range(len(minsum)):
            m, s = minsum[i]
            if done[i]:
                continue
            if c+m>=0:
                c += s
            else:
                print("No")
                break
        else:
            print("Yes")

Submission status: Wrong Answer

Solution code:
def main():

    N = int(input())
    S = []
    pos = []
    neg1 = []
    neg2 = []
    tot_v = 0
    for _ in range(N):
        t = input()
        S.append(t)
        v = 0
        min_v = float('inf')
        for c in t:
            if c == '(': v += 1
            else: v -= 1
            min_v = min(min_v, v)
        tot_v += v
        if min_v >=0:
            pos.append([min_v, v])
        else:
            if v > 0:
                neg1.append([min_v, v])
            else:
                neg2.append([min_v, v])

    if tot_v !=  0: return "No"

    u = 0
    for _, v in pos:
        u += v

    k = 0
    for _, v in neg1:
        k += v

    for min_v, v in neg1:
        if u + k - v + min_v < 0:
            return "No"

    for min_v, v in neg2:
        if u + min_v < 0:
            return "No"
        else:
            u += v

    return "Yes"


if __name__ == '__main__':
    print(main())

Submission status: Wrong Answer

Solution code:
#import numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
def pri(x): print('\n'.join(map(str, x)))

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

a = []
for li in L:
    l = li.count('(')
    r = li.count(')')
    if l != r:
        a.append((l, r))
al = sorted(a, key=lambda x: x[0])
ar = sorted(a, key=lambda x: -x[1])

if al == ar:
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
from bisect import bisect_left
import sys
readlines = sys.stdin.buffer.readlines
readline = sys.stdin.buffer.readline


class SegmentTree:
    """
    演算子は要素とセットでモノイドを形成するようなものでなければならない。
    すなわち、結合律が成り立ち単位元が存在する必要がある。

    equalityはsetを高速化するために使う。めんどい場合はNoneにしてもOK
    """
    @classmethod
    def all_identity(cls, operator, equality, identity, size):
        return cls(operator, equality, identity, [identity]*(2 << (size-1).bit_length()))

    @classmethod
    def from_initial_data(cls, operator, equality, identity, data):
        size = 1 << (len(data)-1).bit_length()
        temp = [identity]*(2*size)
        temp[size:size+len(data)] = data
        data = temp

        for i in reversed(range(size)):
            data[i] = operator(data[2*i],data[2*i+1])
        return cls(operator, equality, identity, data)

    # これ使わずファクトリーメソッド使いましょうね
    def __init__(self, operator, equality, identity, data):
        if equality is None:
            equality = lambda a,b: False
        self.op = operator
        self.eq = equality
        self.id = identity
        self.data = data
        self.size = len(data)//2

    def _interval(self, a, b):
        a += self.size
        b += self.size
        ra = self.id
        rb = self.id

        data = self.data
        op = self.op
        while a < b:
            if a & 1:
                ra = op(ra,data[a])
                a += 1
            if b & 1:
                b -= 1
                rb = op(data[b],rb)
            a >>= 1
            b >>= 1
        return op(ra,rb)

    def __getitem__(self, i):
        if isinstance(i, slice):
            return self._interval(
                                    0 if i.start is None else i.start,
                                    self.size if i.stop is None else i.stop)
        elif isinstance(i, int):
            return self.data[i+self.size]

    def __setitem__(self, i, v):
        i += self.size
        data = self.data
        op = self.op
        eq = self.eq
        while i and not eq(data[i],v):
            data[i] = v
            v = op(data[i^1],v) if i & 1 else op(v,data[i^1])
            i >>= 1

    def __iter__(self):
        return self.data[self.size:]


N = int(readline())

memo = [None]*N

for i,s in enumerate(readlines()):
    s = s.rstrip().decode()
    memo[i] = (min(0,min(accumulate(1 if c =='(' else -1 for c in s))),sum(1 if c =='(' else -1 for c in s))

memo.sort()
def solve():
    min_acc = [v for v,_ in memo]
    delta = [(v,i) for i,(_,v) in enumerate(memo)]
    identity = (-10**7, -1)

    seg = SegmentTree.from_initial_data(max, None, identity, delta)

    cur = 0
    for cnt in range(N):
        ind = bisect_left(min_acc, -cur)
        d, i = seg[ind:]
        cur += d
        if i < 0 or cur < 0:
            return False
        seg[i] = identity
    return cur == 0

print('Yes' if solve() else 'No')

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])
    dd=0
    for a,b in pp:
        if dd<a:
            print('No')
            exit()
        dd+=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
    if not pl:
        dd=0
    for a,b in pp:
        if dd<a:
            print('No')
            exit()
        dd+=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])
    dd=0
    for a,b in pp:
        if dd<a:
            print('No')
            exit()
        dd+=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])
    if not ql:
        dd=0
    for a,b in pp:
        if dd<a:
            print('No')
            exit()
        dd+=b-a


print('Yes')

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import combinations, product
#import bisect# lower_bound etc
#import numpy as np
def run():
    N = int(input())
    dic = {'(':-1, ')':1}
    ret = 0
    for _ in range(N):
        S = input()
        for s in S:
            ret += dic[s]
    if ret == 0:
        print('Yes')
    else:
        print('No')
if __name__ == "__main__":
    run()

Submission status: Wrong Answer

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

def count(s):
    m=0
    e=0
    for t in s:
        if t=='(':
            e+=1
        else:
            e-=1
        m=min(m,e)
    return (e,m)

def main():
    n=int(input())
    S=[input().strip() for _ in range(n)]
    C=[]
    for s in S:
        e,m=count(s)
        C.append((m,e))
    s=0
    for _,e in C:
        s+=e
    if s!=0:
        return 'No'
    C.sort()
    s=0
    hq=[]
    #print(C)
    while C:
        #print(s,C)
        while C and s+C[-1][0]>=0:
            m,e=C.pop()
            heapq.heappush(hq,-e)
        #print(hq)
        if not hq:
            return 'No'
        e=heapq.heappop(hq)
        e*=-1
        if s+e<0:
            return 'No'
        s+=e
    return 'Yes'
    
if __name__=='__main__':
    print(main())

Submission status: Wrong Answer

Solution code:
import networkx as nx

N = input().split()
A = list(map(str, input().split()))

I = list()
O = list()
for s in A:
  a = 0
  for c in s:
    if(c==')'):
      ++a
    else:
      --a
  b = 0
  for c in reversed(s):
    if(c=='('):
      ++b
    else:
      --b
  if not (a==0 and b == 0):
    I.append(a)
    O.append(b)

if nx.algorithms.graphical.is_digraphical(I, O):
  print("Yes")
else:
  print("No")

Submission status: Wrong Answer

Solution code:
# あらかじめ前処理すれば、
# 1: (((...
# 2: )))...
# 3: ...)(((..
# のいずれかの形式に出来る
# typeでソートして、1, 3, 2の形にして解決していけるかを調べれば良さそう？
# "))(", ")))((("とかが険しい
# ほんまか？なんかいけそう
def remove(s):
    while True:
        if len(s) <= 0:
            break
        pre_len = len(s)
        s = s.replace("()", "")
        if len(s) == pre_len:
            break
    return s

n = int(input())
s = [[], [], []]
for i in range(n):
    s_ = remove(input())
    t1 = s_.count("(")
    t2 = s_.count(")")
    if t1 > 0 and t2 > 0:
        s[1].append(s_)
    elif t1 > 0:
        s[0].append(s_)
    else:
        s[2].append(s_)
for i in range(3):
    s[i] = "".join(s[i])

s = "".join(s)
s = remove(s)
if len(s) == 0:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
n = int(input())
a = []
for i in range(n):
	a.append(input())

def checkMatch(string):
	stack = []
	for i in string:
		if i == '(':
			stack.append(i)
		elif i == ')':
			if len(stack)==0:
				return False
			if '(' == stack.pop():
				continue
			else: return False
	if len(stack) == 0: return True
	return False

p = []
index = 0
count = 0
for i in a:
	if checkMatch(i):
		p.append(1)
	else:
		p.append(0)
		count += 1
	index += 1
if count == 0:
	print("Yes")
elif count%2 !=0 :
	print("No")
else:
	for i in range(len(p)):
		if p[i] == 0:
			Next = True
			for j in range(i+1,len(p)):
				if p[j] == 0:
					if checkMatch(a[i]+a[j]) or checkMatch(a[j]+a[i]):
						p[j] = 1
						p[i] = 1
						count -= 2
						Next = False
			if Next : continue
			else: break
	if count == 0:
		print("Yes")
	elif count%2 !=0 :
		print("No")

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()

N = int(input())
tbl = []
sum_left, sum_right, sum_maxdif, sum_dif = 0, 0, 0, 0
for i in range(N):
    S = input()
    left = 0
    right = 0
    maxdif = 0
    for c in S:
        if c=='(':
            left += 1
        else:
            right += 1
        maxdif = max(maxdif, right - left)
    if S[0] == '(':
        s = True
    else:
        s = False
    if S[-1] == ')':
        e = True
    else:
        e = False
    tbl.append([left-right, left, right, maxdif, s, e])
    sum_left += left
    sum_right += right
    sum_maxdif += maxdif
    sum_dif += max(left-right, 0)
tbl.sort()
for i in range(N):
    if tbl[i][5]:
        if tbl[i][0] > 0:
            sum_dif -= tbl[i][0]
        break
for i in range(N-1, -1, -1):
    if tbl[i][4]:
        if tbl[i][3] < 0:
            sum_dif -= tbl[i][0]
        break
    
if sum_left != sum_right:
    print('No')
elif sum_maxdif > sum_dif:
    print('No')
else:
    print('Yes')

Submission status: Wrong Answer

Solution code:
def multi(ar,al,br,bl):
  return ar + max(br-al,0), bl + max(al-br,0)

N = int(input())
suml1 = 0
suml2 =0
sumr1 = 0
sumr2 = 0
for i in range(N):
  bufl = 0
  bufr = 0
  for s in input():
    if s=="(":
      bufl += 1
    elif s==")":
      if bufl > 0:
        bufl -= 1
      else:
        bufr += 1
  if bufl == 0 or bufr==0:
    suml1 += bufl
    sumr1 += bufr
  else:
    if min(sumr2,bufl) > min(suml2,bufr):
      sumr2, suml2 = multi(bufr,bufl,sumr2,suml2)
    else:
      sumr2, suml2 = multi(sumr2,suml2,bufr,bufl)
summ = suml1 + suml2 - sumr1 -sumr2
if summ==0:
  if suml2 <= sumr1 and sumr2 <= suml1: 
    print("Yes")
  else:
    print("No")
else:
  print("No")

Submission status: Wrong Answer

Solution code:
import sys

n = int(input())
s = [list(input()) for i in range(n)]

s_cnt, s_minmax = [0] * n, [[0, 0] for i in range(n)]
for i in range(n):
    for j in s[i]:
        if j == '(':
            s_cnt[i - 1] += 1
            s_minmax[i-1][1] = max(s_minmax[i-1][1], s_cnt[i - 1])
        else:
            s_cnt[i - 1] -= 1
            s_minmax[i-1][1] =max(s_minmax[i-1][1]-1, 0)
            s_minmax[i-1][0] = min(s_minmax[i-1][0], s_cnt[i - 1])

s_minmax.sort(reverse=True)
if sum(s_cnt) != 0:
    print('No')
    exit()

right = 0
for list in s_minmax:
    l,r=list
    right += l
    if right < 0:
        print('No')
        exit()
    right += r
else:
    print('Yes')

Submission status: Wrong Answer

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

LP = 0
RP = 0
S = []
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:
        S.append([L,R])

if (LP==RP)and(len(S)==0):
    print("Yes")

else:
    L = LP
    for i in range(len(S)):
        L += -1*S[i][1]
        L += S[i][0]
    if L == RP:
        print("Yes")
    else:
        print("No")

Submission status: Wrong Answer

Solution code:
from sys import stdin
n = int(stdin.readline().rstrip())
s = [stdin.readline().rstrip() for _ in range(n)]

def main():
    N0 = 2 ** (n - 1).bit_length()
    data = [float('inf')] * (2 * N0)

    def update(k, x):
        k += N0 - 1
        data[k] = x
        while k >= 0:
            k = (k - 1) // 2
            data[k] = min(data[2 * k + 1], data[2 * k + 2])
    def query(l, r):
        L = l + N0
        R = r + N0
        s = float('inf')
        while L < R:
            if R & 1:
                R -= 1
                s = min(s, data[R - 1])

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

    dl = []
    for i in range(n):
        dd = 0
        dd_min = 0
        for x in s[i]:
            if x == '(':
                dd += 1
            else:
                dd -= 1
            dd_min = min(dd_min, dd)

        dl.append([dd, dd_min])

    d = [_dl[0] for _dl in dl]
    if sum(d) != 0:
        print('No')
    else:
        dl.sort(key=lambda x:x[1]) # sorted by d_min
        d = [_dl[0] for _dl in dl]
        d_min = [_dl[1] for _dl in dl]

        from collections import defaultdict
        d_to_idx = defaultdict(list)
        for i in range(n):
            d_to_idx[d[i]].append(i)

        for i in range(len(d)):
            update(i, -d[i])

        from bisect import bisect_left
        f = True
        carry = 0
        for i in range(n):
            # print(carry, d, d_min)
            if d_min[-1] + carry < 0:
                f = False
                break

            idx = bisect_left(d_min, -carry)

            dd = -query(idx, n)
            if dd == -float('inf'):
                f = False
                break

            idx2 = d_to_idx[dd][-1]
            d_to_idx[dd].pop()

            carry += dd
            update(idx2, float('inf'))

        if f and carry == 0:
            print('Yes')
        else:
            print('No')

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

LR = []
for i in range(N):
    s = S[i]
    l = 0
    r = 0
    for ket in s:
        if ket == "(":
            l+=1
        else:
            if l > 0:
                l-=1
            else:
                r+=1
    LR.append([l,r])
    
LR.sort(reverse=True)
#print(LR)
Left = 0
Right = 0
flag = True
for lr in LR:
    l,r = lr
    if Left-r < 0:
        flag = False
        break
    Left-=r
    Left+=l
    
if flag:
    if Left == 0:
        print("Yes")
    else:
        print("No")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
n=int(input())
m=[]
for i in range(n):
  s=input()
  a,b,t=0,0,0
  # a:左に(がいくつ必要か
  # b:右に)がいくつ必要か
  # t: (のストック
  for j in s:
    if t==0 and j==")":
      a+=1
    elif j=="(":
      t+=1
    elif t>0 and j==")":
      t-=1
  m.append([a,t])
  #[ 左に(がいくつ必要か, 右に)がいくつ必要か ]
m.sort()
r=0 # (のストック
if m[0][0]!=0 or m[-1][-1]!=0:
  print("No")
  exit()
for li in m:
  r+=li[1]-li[0]
  if r<0:
    print("No")
    exit()
if r==0:
  print("Yes")
else:
  print("No")

Submission status: Wrong Answer

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

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

for l,r in stack:
    if l<llst:

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

        rlst-=r
        r=0
    else:
        continue

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

Submission status: Wrong Answer

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

def brancket(s):
    ans = [0, 0, 0, 0]
    l, r = 0, 0
    for i in s:
        if i == ')':
            ans[2] += 1
            if r == 0:
                ans[0] += 1
            else:
                r -= 1
        if i == '(':
            ans[3] += 1
            r += 1
    ans[1] = r
    return ans

L, R, tl, tr = 0, 0, False, False
bigr, bigl, tmpl, tmpr = 0, 0, 0, 0
allr, alll = 0, 0

for i in S:
    a = brancket(i)
    
    if a[0] != 0 and a[1] != 0:
        if a[0] == 0:
            tl = True
        if a[1] == 0:
            tr = True
    L += a[0]
    R += a[1]
    alll += a[2]
    allr += a[3]
    
    if a[0] > bigl:
        bigl = a[0]
        tmpr = a[1]
    if a[1] > bigr:
        bigr = a[1]
        tmpl = a[0]
    

if L != 0 or R != 0:  
    if bigl > allr - tmpr or bigr > alll - tmpl:
        print('No')
    else: 
        print('Yes' if tl and tr and L == R else 'No')
        
else:
    print('Yes')