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:
def init_max(init_max_val):
    #set_val
    for i in range(n):
        seg_max[i+num_max-1]=init_max_val[i]
    for i in range(num_max-2,-1,-1) :
        seg_max[i]=max(seg_max[2*i+1],seg_max[2*i+2])
    
def update_max(k,x):
    k += num_max-1
    seg_max[k] = x
    while k:
        k = (k-1)//2
        seg_max[k] = max(seg_max[k*2+1],seg_max[k*2+2])
    
def query_max(p,q):
    if q<=p:
        return ide_ele_max
    p += num_max-1
    q += num_max-2
    res=ide_ele_max
    while q-p>1:
        if p&1 == 0:
            res = max(res,seg_max[p])
        if q&1 == 1:
            res = max(res,seg_max[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = max(res,seg_max[p])
    else:
        res = max(max(res,seg_max[p]),seg_max[q])
    return res


n=int(input())

ide_ele_max = (-10**9,-10**9)
num_max =2**(n-1).bit_length()
seg_max=[ide_ele_max]*2*num_max

A=[]#left,over
for i in range(n):
    s=input()
    leftlast=0
    over=0
    for c in s:
        if c=='(':
            leftlast+=1
        else:
            leftlast-=1
            over=min(over,leftlast)
    A.append([leftlast,over])
A.sort(key=lambda x: x[1])

left=[(a[0],idx) for idx,a in enumerate(A)]
over=[a[1] for a in A]

init_max(left)

from bisect import bisect_left
now=0
flag=False
for i in range(n):
    idx=bisect_left(over,-now)
    M=query_max(idx,n)
    M,i=M # max,index
    if M<=-10**7:
        flag=True
        break
    update_max(i,(-10**9,0))
    now+=M
flag|=(now!=0)
print("No" if flag else "Yes")

Submission status: Wrong Answer

Solution code:
N=int(input())
class newint():
    def __init__(self, name, age):
        self.a = name
        self.b = age
    def __lt__(self,other):
        return min(self.a,self.b-other.a)>min(other.a,other.b-self.a)
D=[]       
for _ in range(N):
    x=list(input())
    mini=0
    maxi=0
    now=0
    for some in x:
        if some=="(":
            now+=1
        else:
            now-=1
            mini=min(mini,now)
    D.append(newint(mini,now-mini))
D.sort()
flag=True
dif=0
for some in D:
    minus,plus=some.a,some.b
    dif+=minus
    if dif<0:
        flag=False
        break
    else:
        dif+=plus
if flag and dif==0:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
N=int(input())
class newint():
    def __init__(self, name, age):
        self.a = name
        self.b = age
    def __lt__(self,other):
        return min(self.a,self.b-other.a)>=min(other.a,other.b-self.a)
D=[]       
for _ in range(N):
    x=list(input())
    mini=0
    maxi=0
    now=0
    for some in x:
        if some=="(":
            now+=1
        else:
            now-=1
            mini=min(mini,now)
    D.append(newint(mini,now-mini))
D.sort()
flag=True
dif=0
for some in D:
    minus,plus=some.a,some.b
    dif+=minus
    if dif<0:
        flag=False
        break
    else:
        dif+=plus
if flag and dif==0:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
# +1/-1の折れ線で表したとき
# 「0で終わる」かつ「途中で0未満にならない」を満たせば良い

# あとは貪欲を上手い事使う


def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    #from math import gcd

    #inf = 10**17
    #mod = 10**9 + 7

    n = int(input())
    a = []
    b = []
    for _ in range(n):
        s = input().rstrip()
        # 最終的に上がる量/最下点
        up, down = 0, 0
        for i in s:
            if i == ')':
                up -= 1
                if down > up:
                    down = up
            else:
                up += 1
        if up >= 0:
            a.append((down, up))
        else:
            b.append((down-up, -up))

    a.sort(key=lambda a: a[0],reverse=True)
    b.sort(key=lambda a: a[0],reverse=True)

    left, right = 0, 0

    for d, u in a:
        if left+d < 0:
            print('No')
            break
        else:
            left += u
    for d, u in b:
        if right+d < 0:
            print('No')
            break
        else:
            right += u
    if left == right:
        print('Yes')
    else:
        print('No')
    
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# +1/-1の折れ線で表したとき
# 「0で終わる」かつ「途中で0未満にならない」を満たせば良い

# あとは貪欲を上手い事使う


def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    #from math import gcd

    #inf = 10**17
    #mod = 10**9 + 7

    n = int(input())
    a = []
    b = []
    for _ in range(n):
        s = input().rstrip()
        # 最終的に上がる量/最下点
        up, down = 0, 0
        for i in s:
            if i == ')':
                up -= 1
                if down > up:
                    down = up
            else:
                up += 1
        if up >= 0:
            a.append((down, up))
        else:
            b.append((down-up, -up))

    a.sort(key=lambda a: a[0],reverse=True)
    b.sort(key=lambda a: a[0],reverse=True)

    left, right = 0, 0

    for d, u in a:
        if left+d < 0:
            print('No')
            break
        else:
            left += u
    for d, u in a:
        if right+d < 0:
            print('No')
            break
        else:
            right += u
    if left == right:
        print('Yes')
    else:
        print('No')
    
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# +1/-1の折れ線で表したとき
# 「0で終わる」かつ「途中で0未満にならない」を満たせば良い

# あとは貪欲を上手い事使う


def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    #from math import gcd

    #inf = 10**17
    #mod = 10**9 + 7

    n = int(input())
    a = []
    b = []
    for _ in range(n):
        s = input().rstrip()
        # 最終的に上がる量/最下点
        up, down = 0, 0
        for i in s:
            if i == ')':
                up -= 1
                if down > up:
                    down = up
            else:
                up += 1
        if up >= 0:
            a.append((down, up))
        else:
            b.append((down, up))

    a.sort(reverse=True)
    b.sort(key=lambda a: a[1],reverse=True)
    b.sort()

    c = 0

    for d, u in a:
        if c+d < 0:
            print('No')
            break
        else:
            c += u
    else:
        for d, u in b:
            if c+d < 0:
                print('No')
                break
            else:
                c += u
        else:
            if c == 0:
                print('Yes')
            else:
                print('No')
    
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    #from math import gcd

    #inf = 10**17
    #mod = 10**9 + 7

    n = int(input())
    a = []
    b = []
    for _ in range(n):
        s = input().rstrip()
        # 最終的に上がる量/最下点
        up, down = 0, 0
        for i in s:
            if i == ')':
                up -= 1
                if down > up:
                    down = up
            else:
                up += 1
        if up >= 0:
            a.append((down, up))
        else:
            b.append((down, up))

    a.sort(reverse=True)
    b.sort()

    c = 0

    for d, u in a:
        if c+d < 0:
            print('No')
            break
        else:
            c += u
    else:
        for d, u in b:
            if c+d < 0:
                print('No')
                break
            else:
                c += u
        else:
            if c == 0:
                print('Yes')
            else:
                print('No')
    
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def count_scan(s):
    max_min = 0
    compare = 0
    for c in s:
        if c == '(':
            compare += 1
        elif c == ')':
            compare -= 1
            max_min = min(max_min, compare)
    return min(max_min, compare), compare


def key(lst):
    m, c = lst
    if c > 0:
        return 1, m
    else:
        return -1, c - m


def main():
    n = int(input())
    lst = [input() for _ in range(n)]

    txt = 'No'
    ans = 0
    for max_min, c in sorted([count_scan(s) for s in lst],
                             reverse=True,
                             key=key):
        if max_min + ans < 0:
            break
        ans += c
    else:
        if ans == 0:
            txt = 'Yes'

    print(txt)

Submission status: Wrong Answer

Solution code:
import numpy as np
from itertools import accumulate
from operator import itemgetter, attrgetter
from bisect import bisect_left as bil
N, *S = open(0).read().split()

S = [[1 if c == '(' else -1 for c in s]for s in S ]
A = [list(accumulate(s)) for s in S]

sun = sum(a[-1] for a in A)
if sun != 0:
    print('No')
    exit()

L = [(min(a), a[-1]) for a in A]
L.sort(reverse=True)

i = bil([l for l, _ in L], 0)
left = L[:i]
right = L[i:]

left.sort(key=itemgetter(1), reverse=True)
right.sort(key=itemgetter(1), reverse=True)

L = left + right

sun = 0
for mn, sm in L:
    if sun + mn < 0:
        print('No')
        exit()
    sun += sm

print('Yes')

Submission status: Wrong Answer

Solution code:
# 入力
N = int(input())

S1 = [] # 増えるシーケンス用
S2 = [] # 減るシーケンス用

# 入力その２
for i in range(N):

    S = input()  # シーケンス
    mid, end = 0, 0    

    for s in S:
        if s == '(':
            end += 1
        else:
            end -= 1
            
        mid = min(mid, end)  # 途中経過で一番減るところを探す

    if end > 0:
        S1.append((mid, end))
    else:
        S2.append((mid, end))

S1.sort(reverse=True)
S2.sort(key = lambda x : (x[0], -x[1]))


mid = end = 0  # スタート
out = False

for t in S1:
    a, b = t
    mid = end + a
    end = end + b
    if mid < 0 or end < 0:  # 途中で左カッコの数が右を上回る
        out = True
        break
        
for t in S2:
    a, b = t
    mid = end + a
    end = end + b
    if mid < 0 or end < 0:  # 途中で左カッコの数が右を上回る
        out = True
        break
        
if (not end == 0) or out:  # 右、左 の数が合わない
    print('No')
else:
    print('Yes')

Submission status: Wrong Answer

Solution code:
# 入力
N = int(input())

S1 = [] # 増えるシーケンス用
S2 = [] # 減るシーケンス用

# 入力その２
for i in range(N):

    S = input()  # シーケンス
    mid, end = 0, 0    

    for s in S:
        if s == '(':
            end += 1
        else:
            end -= 1
            
        mid = min(mid, end)  # 途中経過で一番減るところを探す

    if end > 0:
        S1.append((mid, end))
    else:
        S2.append((mid, end))

S1.sort(reverse=True)
S2.sort(key = lambda x : (x[0], -x[1]))


mid = end = 0  # スタート
out = False

for t in S1:
    a, b = t
    mid = end + a
    end = end + b
    if mid < 0 or end < 0:  # 途中で左カッコの数が右を上回る
        out = True
        break
        
for t in S2:
    a, b = t
    mid = end + a
    end = end + b
    if mid < 0 or end < 0:  # 途中で左カッコの数が右を上回る
        out = True
        break
        
if not (end == 0) or out:  # 右、左 の数が合わない
    print('No')
else:
    print('Yes')

Submission status: Wrong Answer

Solution code:
# 入力
N = int(input())

S1 = [] # 増えるシーケンス用
S2 = [] # 減るシーケンス用

# 入力その２
for i in range(N):

    S = input()  # シーケンス
    mid, end = 0, 0    

    for s in S:
        if s == '(':
            end += 1
        else:
            end -= 1
            
        mid = min(mid, end)  # 途中経過で一番減るところを探す

    if end > 0:
        S1.append((mid, end))
    else:
        S2.append((mid, end))

S1.sort(reverse=True)
S2.sort(key = lambda x : (x[0], -x[1]))

mid = end = 0  # スタート
out = False

for t in S1:
    a, b = t
    mid = end + a
    end = end + b
    if mid < 0 or end < 0:  # 途中で左カッコの数が右を上回る
        out = True
        
for t in S2:
    a, b = t
    mid = end + a
    end = end + b
    if mid < 0 or end < 0:  # 途中で左カッコの数が右を上回る
        out = True
        
if (end == 0) or out:  # 右、左 の数が合わない
    print('No')
else:
    print('Yes')

Submission status: Wrong Answer

Solution code:
from itertools import permutations

n = int(input())
s = []
for _ in range(n):
	subseq = input()
	left = 0
	right = 0
	for char in subseq:
		if char == "(":
			left += 1
		else:
			right += 1
	s.append(left - right)

for perm in permutations(s):
	foo = 0
	for num in perm:
		foo += num
		if foo < 0:
			break
	else:
		if foo == 0:
			print ("Yes")
			break
else:
	print ("No")

Submission status: Wrong Answer

Solution code:
from itertools import permutations

n = int(input())
s = []
for _ in range(n):
	subseq = input()
	left = 0
	right = 0
	for char in subseq:
		if char == "(":
			left = 0
		else:
			right = 0
	s.append(left - right)

for perm in permutations(s):
	foo = 0
	for num in perm:
		foo += num
		if foo < 0:
			break
	else:
		if foo == 0:
			print ("Yes")
			break
else:
	print ("No")

Submission status: Wrong Answer

Solution code:
from itertools import permutations

n = int(input())
s = []
for _ in range(n):
	subseq = input()
	left = 0
	right = 0
	for char in subseq:
		if char == "(":
			left = 0
		else:
			right = 0
	s.append(left - right)

for perm in permutations(s):
	foo = 0
	for num in perm:
		foo += num
		if foo < 0:
			break
	else:
		print ("Yes")
		break
else:
	print ("No")

Submission status: Wrong Answer

Solution code:
import itertools


num = int(input())
S = []
for _ in range(num):
    S.append(input())


result = False
for i in itertools.permutations(S):
    checkedArray = list(''.join(i))
    if checkedArray[0] == ")": continue

    cost = 0
    for index, item in enumerate(checkedArray):
        if item == "(": cost += 1
        else: cost -= 1

        if cost == 0 and index == len(checkedArray) - 1:
            result = True
            break

    if result == True: break

print("Yes" if result == True else "No")

Submission status: Wrong Answer

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

ls = []
rs = []
tot = 0
for si in s:
  b = 0
  h = 0
  for c in si:
    if c == '(':
      h += 1
    else:
      h -= 1
    b = min(h,b)
  if h > 0:
    ls.append((b,h))
  else:
    rs.append((b-h,-h))
  tot += h
ls.sort(reverse = True)
rs.sort(reverse = True)

def check(x):
  t = 0
  for bx,hx in x:
    if t+bx < 0:
      return False
    t += h
  return True

if check(ls) and check(rs) and tot == 0:
  print('Yes')
else:
  print('No')

Submission status: Wrong Answer

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

xs1total = 0 # ((
xs2 = [] # )((
xs3 = [] # ))(
xs4total = 0 # ))

for s in S:
    n = 0
    m = 0
    for c in s:
        if c == "(":
            n += 1
        elif c == ")":
            n -= 1
            m = min(m, n)
    k = n - m
    if m == 0 and k == 0:
        continue
    elif m == 0:
        xs1total += k
    elif k == 0:
        xs4total += -m
    else:
        if -m < k:
            xs2.append((-m, k))
        else:
            xs3.append((-m, k))

xs2.sort()
xs3.sort()

def check(xs1total, xs2, xs3, xs4total):
    t = xs1total
    for x in xs2:
        if t < x[0]:
            return False
        t = t - x[0] + x[1]
    for x in xs3:
        if t < x[0]:
            return False
        t = t - x[0] + x[1]
    return t == xs4total

#print(xs1total, xs2, xs3, xs4total)

if check(xs1total, xs2, xs3, xs4total):
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
N = int(input())
Sn = []
for _ in range(N):
    Sn.append(input())

tt = 0
lv = 0
rv = 0
ev = 0
for s in Sn:
    lo = (s[0] == '(')

    t = 0
    for _, l in enumerate(s):
        if l == '(':
            t += 1
        else:
            t -= 1

    ro = (l == ')')

    if t >= 0 and lo:
        lv += 1
    if t <= 0 and ro:
        rv += 1
    if t == 0 and lo and ro:
        ev += 1
    tt += t

lv -= ev
rv -= ev

if (lv == 0) and (ev > 0):
    lv += 1
    ev -= 1

if (rv == 0) and (ev > 0):
    rv += 1
    ev -= 1

result = (tt == 0) and (lv > 0) and (rv > 0)

if result:
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

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

xs1total = 0 # ((
xs2 = [] # )((
xs3 = [] # ))(
xs4total = 0 # ))

for s in S:
    n = 0
    m = 0
    for c in s:
        if c == "(":
            n += 1
        elif c == ")":
            n -= 1
            m = min(m, n)
    k = n - m
    if m == 0 and k == 0:
        continue
    elif m == 0:
        xs1total += k
    elif k == 0:
        xs4total += -m
    else:
        if -m < k:
            xs2.append((-m, k))
        else:
            xs3.append((-m, k))

xs2.sort()
xs3.sort(key=lambda x:-x[1])

def check(xs1total, xs2, xs3, xs4total):
    t = xs1total
    for x in xs2:
        if t < x[0]:
            return False
            t = t - x[0] + x[1]
    for x in xs3:
        if t < x[0]:
            return False
            t = t - x[0] + x[1]
    return t == xs4total

if check(xs1total, xs2, xs3, xs4total):
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

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

xs1total = 0 # ((
xs2 = [] # )((
xs3 = [] # ))(
xs4total = 0 # ))

for s in S:
    n = 0
    m = 0
    for c in s:
        if c == "(":
            n += 1
        elif c == ")":
            n -= 1
            m = min(m, n)
    k = n - m
    if m == 0 and k == 0:
        continue
    elif m == 0:
        xs1total += k
    elif k == 0:
        xs4total += -m
    else:
        if -m < k:
            xs2.append((-m, k))
        else:
            xs3.append((-m, k))

xs2.sort()
xs3.sort()

def check(xs1total, xs2, xs3, xs4total):
    t = xs1total
    for x in xs2:
        if t < x[0]:
            return False
            t = t - x[0] + x[1]
    for x in xs3:
        if t < x[0]:
            return False
            t = t - x[0] + x[1]
    return t == xs4total

if check(xs1total, xs2, xs3, xs4total):
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
n=int(input())
s1=0
s2=0
s3=list()
s4=list()
s5=list()
for i in range(n):
    a=str(input())
    a=a.replace(r'()','')
    if len(a)==0:
        continue
    if a[0]=="(" and a[-1]=="(":
        s1+=len(a)
    elif a[0]==")" and a[-1]==")":
        s2+=len(a)
    else:
        x=len(a.replace("(",""))
        y=len(a)-x
        if x<y:
            s3.append([x,y])
        elif x==y:
            s4.append(x)
        else:
            s5.append([x,y])
            
s3.sort(key=lambda x:x[0])
s5.sort(key=lambda x:x[1])

flag=0
limit=s1

if len(s3)!=0:
    for i in range(len(s3)):
        if limit>=s3[i][0]:
            limit=limit-s3[i][0]+s3[i][1]
        else:
            flag=1
            print("No")
            break

x=limit

if len(s4)!=0:
    if limit<max(s4):
        print("No")
        flag=1

limit=s2
if len(s5)!=0:    
    if flag==0:
        for i in range(len(s5)):
            if limit>=s5[i][1]:
                limit=limit-s5[i][1]+s5[i][0]
            else:
                flag=1
                print("No")
                break

if flag==0 and len(s4)!=0:
    if limit<max(s4):
        print("No")
        flag=1

if flag==0 and x==limit:
    print("Yes")
elif flag==0:
    print("No")

Submission status: Wrong Answer

Solution code:
n=int(input())
s1=0
s2=0
s3=list()
s4=list()
s5=list()
for i in range(n):
    a=str(input())
    a=a.replace(r'()','')
    if len(a)==0:
        continue
    if a[0]=="(" and a[-1]=="(":
        s1+=len(a)
    elif a[0]==")" and a[-1]==")":
        s2+=len(a)
    else:
        x=len(a.replace("(",""))
        y=len(a)-x
        if x<y:
            s3.append([x,y])
        elif x==y:
            s4.append(x)
        else:
            s5.append([x,y])
            
s3.sort(key=lambda x:x[0])
s5.sort(key=lambda x:x[1])

flag=0
limit=s1

if len(s3)!=0:
    for i in range(len(s3)):
        if limit>=s3[i][0]:
            limit=limit-s3[i][0]+s3[i][1]
        else:
            flag=1
            print("No")
            break

x=limit

if len(s4)!=0:
    if limit<max(s4):
        print("No")
        flag=1

limit=s2
if len(s5)!=0:    
    if flag==0:
        for i in range(len(s5)):
            if limit>=s5[i][1]:
                limit=limit-s5[i][1]+s5[i][0]
            else:
                flag=1
                print("No")
                break

if len(s4)!=0:
    if limit<max(s4):
        print("No")
        flag=1

if flag==0 and x==limit:
    print("Yes")
elif flag==0:
    print("No")

Submission status: Wrong Answer

Solution code:
n=int(input())
s=[0]*n
info=[0]*n
for i in range(n):
    ss=list(input())
    now=0
    mi=0
    for sss in ss:
        if sss=="(":
            now+=1
        else:
            now-=1
            mi=min(mi,now)
    info[i]=(mi,now)
#info.sort(key=lambda x:(x[1]>=0)*2+(x[0]>=0),reverse=True )

info0 = []
info1 = []
for i,inf in enumerate(info):
    if inf[1]>=0:
        info0.append(inf)
    else:
        info1.append(inf)
info0.sort(key=lambda x:x[0])
info1.sort(key=lambda x:x[1]-x[0],reverse=True)


ans=True
now=0
for inf in info0:
    if now+inf[0]>=0:
        now+=inf[1]
    else:
        ans=False
for inf in info1:
    if now+inf[0]>=0:
        now+=inf[1]
    else:
        ans=False
if now!=0:
    ans=False
    
print(ans*"Yes"+(1-ans)*"No")

Submission status: Wrong Answer

Solution code:
n=int(input())
s1=0
s2=0
s3=list()
s4=list()
s5=list()
for i in range(n):
    a=str(input())
    a=a.replace(r'()','')
    if len(a)==0:
        continue
    if a[0]=="(" and a[-1]=="(":
        s1+=len(a)
    elif a[0]==")" and a[-1]==")":
        s2+=len(a)
    else:
        x=len(a.replace("(",""))
        y=len(a)-x
        if x<=y:
            s3.append([x,y])
        elif x==y:
            s4.append(x)
        else:
            s5.append([x,y])
            
s3.sort(key=lambda x:x[0])
s5.sort(key=lambda x:x[1])

flag=0
limit=s1

if len(s3)!=0:
    for i in range(len(s3)):
        if limit>=s3[i][0]:
            limit=limit-s3[i][0]+s3[i][1]
        else:
            flag=1
            print("No")
            break

x=limit

if len(s4)!=0:
    if limit<max(s4):
        print("No")
        flag=1

limit=s2
if len(s5)!=0:    
    if flag==0:
        for i in range(len(s5)):
            if limit>=s5[i][1]:
                limit=limit-s5[i][1]+s5[i][0]
            else:
                flag=1
                print("No")
                break

if len(s4)!=0:
    if limit<max(s4):
        print("No")
        flag=1

if flag==0 and x==limit:
    print("Yes")
elif flag==0:
    print("No")

Submission status: Wrong Answer

Solution code:
n=int(input())
s=[0]*n
info=[0]*n
for i in range(n):
    ss=list(input())
    now=0
    mi=0
    for sss in ss:
        if sss=="(":
            now+=1
        else:
            now-=1
            mi=min(mi,now)
    info[i]=(mi,now)
#info.sort(key=lambda x:(x[1]>=0)*2+(x[0]>=0),reverse=True )

info0 = []
info1 = []
for i,inf in enumerate(info):
    if inf[1]>=0:
        info0.append(inf)
    else:
        info1.append(inf)
info0.sort()
info1.sort(key=lambda x:x[1]-x[0],reverse=True)


ans=True
now=0
for inf in info0:
    if now+inf[0]>=0:
        now+=inf[1]
    else:
        ans=False
for inf in info1:
    if now+inf[0]>=0:
        now+=inf[1]
    else:
        ans=False
if now!=0:
    ans=False
    
print(ans*"Yes"+(1-ans)*"No")

Submission status: Wrong Answer

Solution code:
n=int(input())
s1=0
s2=0
s3=list()
s4=list()
s5=list()
for i in range(n):
    a=str(input())
    a=a.replace(r'()','')
    if len(a)==0:
        continue
    if a[0]=="(" and a[-1]=="(":
        s1+=len(a)
    elif a[0]==")" and a[-1]==")":
        s2+=len(a)
    else:
        x=len(a.replace("(",""))
        y=len(a)-x
        if x<=y:
            s3.append([x,y])
        elif x==y:
            s4.append(x)
        else:
            s5.append([x,y])
            
s3.sort(key=lambda x:x[0])
s5.sort(key=lambda x:x[1])

flag=0
limit=s1

if len(s3)!=0:
    for i in range(len(s3)):
        if limit>=s3[i][0]:
            limit=limit-s3[i][0]+s3[i][1]
        else:
            flag=1
            print("No")
            break

x=limit

if len(s4)!=0:
    if limit<max(s4):
        print("No")
        flag=1

limit=s2
if len(s5)!=0:    
    if flag==0:
        for i in range(len(s5)):
            if limit>=s5[i][1]:
                limit=limit-s5[i][1]+s5[i][0]
            else:
                flag=1
                print("No")
                break



if flag==0 and x==limit:
    print("Yes")
elif flag==0:
    print("No")

Submission status: Wrong Answer

Solution code:
n=int(input())
s1=0
s2=0
s3=list()
s4=list()
s5=list()
for i in range(n):
    a=str(input())
    a=a.replace(r'()','')
    if len(a)==0:
        continue
    if a[0]=="(" and a[-1]=="(":
        s1+=len(a)
    elif a[0]==")" and a[-1]==")":
        s2+=len(a)
    else:
        x=len(a.replace("(",""))
        y=len(a)-x
        if x<=y:
            s3.append([x,y])
        elif x==y:
            s4.append(x)
        else:
            s5.append([x,y])
            
s3.sort(key=lambda x:x[0])
s5.sort(key=lambda x:x[1])

flag=0
limit=s1

if len(s3)!=0:
    for i in range(len(s3)):
        if limit>=s3[i][0]:
            limit=limit-s3[i][0]+s3[i][1]
        else:
            flag=1
            print("No")
            break

x=limit

if len(s4)!=0:
    if limit<max(s4):
        print("No")
        flag=1

limit=s2
if len(s5)!=0:    
    if flag==0:
        for i in range(len(s5)):
            if limit>=s5[i][1]:
                limit=limit-s5[i][1]+s5[i][0]
            else:
                flag=1
                print("No")
                break



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

Submission status: Wrong Answer

Solution code:
n=int(input())
s1=0
s2=0
s3=list()
s4=list()
s5=list()
for i in range(n):
    a=str(input())
    a=a.replace(r'()','')
    if len(a)==0:
        continue
    if a[0]=="(" and a[-1]=="(":
        s1+=len(a)
    elif a[0]==")" and a[-1]==")":
        s2+=len(a)
    else:
        x=len(a.replace("(",""))
        y=len(a)-x
        if x<=y:
            s3.append([x,y])
        elif x==y:
            s4.append(x)
        else:
            s5.append([x,y])
            
s3.sort(key=lambda x:x[0])
s5.sort(key=lambda x:x[1])

flag=0
limit=s1

if len(s3)!=0:
    for i in range(len(s3)):
        if limit>=s3[i][0]:
            limit=limit-s3[i][0]+s3[i][1]
        else:
            flag=1
            print("No")
            break

if len(s4)!=0:
    if limit<max(s4):
        print("No")
        flag=1

limit=s2
if len(s5)!=0:    
    if flag==0:
        for i in range(len(s5)):
            if limit>=s5[i][1]:
                limit=limit-s5[i][1]+s5[i][0]
            else:
                flag=1
                print("No")
                break

if flag==0:
    print("Yes")

Submission status: Wrong Answer

Solution code:
n=int(input())
s1=0
s2=0
s3=list()
s4=list()
s5=list()
for i in range(n):
    a=str(input())
    a=a.replace(r'()','')
    if len(a)==0:
        continue
    if a[0]=="(" and a[-1]=="(":
        s1+=len(a)
    elif a[0]==")" and a[-1]==")":
        s2+=len(a)
    else:
        x=len(a.replace("(",""))
        y=len(a)-x
        if x<=y:
            s3.append([x,y])
        elif x==y:
            s4.append(x)
        else:
            s5.append([x,y])
            
s3.sort(key=lambda x:x[0])
s5.sort(key=lambda x:x[1])

flag=0
limit=s1

if len(s3)!=0:
    for i in range(len(s3)):
        if limit>=s3[i][0]:
            limit=limit-s3[i][0]+s3[i][1]
        else:
            flag=1
            print("No")
            break

if len(s4)!=0:
    if limit<max(s4):
        print("No")
        flag=1

limit=s2
if len(s5)!=0:    
    if flag==0:
        for i in range(len(s5)):
            if limit>=s5[i][1]:
                limit=limit-s3[i][1]+s3[i][0]
            else:
                flag=1
                print("No")
                break

if flag==0:
    print("Yes")

Submission status: Wrong Answer

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

list_s = []
for s in S:
    tmp = 0
    min_tmp = 0
    for ss in s:
        if ss == "(":
            tmp += 1
        else:
            tmp -= 1
        min_tmp = min(tmp, min_tmp)
    list_s.append([min_tmp, tmp])
#print(list_s)
    
pos = []
neg = []
for i, (m, s) in enumerate(list_s):
    if s >= 0:
        pos.append([m, s])
    else:
        neg.append([m, s, i])
pos.sort(key = lambda x: -x[0])

list_t = []
for m, s, i in neg:
    tmp = 0
    min_tmp = 0
    min_true_tmp = 0
    for ss in S[i][::-1]:
        if ss == ")":
            tmp += 1
        else:
            tmp -= 1
        min_tmp = min(min_tmp, tmp)
        min_true_tmp = min(min_true_tmp, - tmp)
    list_t.append([min_tmp, min_true_tmp, -tmp, i])
list_t.sort(key = lambda x: x[0] * -1)
neg = list_t
#print(pos, neg)

cnt = 0
for m, s in pos:
    if cnt + m < 0:
        print("No")
        exit()
    cnt += s
for m, mt, s, i in neg:
    if cnt + mt < 0:
        print("No")
        exit()
    cnt += s
if cnt:
    print("No")
    exit()
    
print("Yes")

Submission status: Wrong Answer

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

LRM = []
for s in S:
    tmp = 0
    min_tmp = 0
    left = 0
    right = 0
    for ss in s:
        if ss == "(":
            left += 1
            tmp += 1
        else:
            right += 1
            tmp -= 1
        min_tmp = min(min_tmp, tmp)
    LRM.append([left, right, min_tmp])
#print(LRM)

plus = []
plus_m = []
minus = []

for i, (l, r, m) in enumerate(LRM):
    if m == 0:
        plus.append([l, r, m])
    else:
        if l >= r:
            plus_m.append([l, r, m])
        else:
            minus.append([l, r, m])
plus_m.sort(key = lambda x: -x[2])
minus.sort(key = lambda x: x[2])

cnt = 0
for l, r, m in plus + plus_m + minus:
    if cnt + m < 0:
        print("No")
        exit()
    cnt += l - r
    
if cnt:
    print("No")
else:
    print("Yes")