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:
from operator import itemgetter
n=int(input())
s=[input() for _ in range(n)]
cnt=[[0,0] for _ in range(n)]
for i in range(n):
    k=len(s[i])
    r=n-1
    for l in range(k):
        s[i]=s[i].replace("()","")
    for j in range(len(s[i])):
        if s[i][j]=="(":
            cnt[i][0]+=1
        else:
            cnt[i][1]+=1
cnt.sort(key=itemgetter(1))
#print(s)
#print(cnt)
ok=True
cnt0,cnt1=0,0
for i in range(n):
    if cnt0<cnt1+cnt[i][1]:
        ok=False
        break
    cnt0+=cnt[i][0]
    cnt1+=cnt[i][1]
if cnt0!=cnt1:
    ok=False
if ok:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
from operator import itemgetter
n=int(input())
s=[input() for _ in range(n)]
cnt=[[0,0] for _ in range(n)]
for i in range(n):
    k=len(s[i])
    r=n-1
    for l in range(k):
        s[i]=s[i].replace("()","")
    for j in range(len(s[i])):
        if s[i][j]=="(":
            cnt[i][0]+=1
        else:
            cnt[i][1]+=1
cnt.sort(key=itemgetter(1))
#print(s)
#print(cnt)
ok=True
cnt0,cnt1=0,0
for i in range(n):
    if cnt0==cnt1:
        if cnt[i][1]>=1:
            ok=False
    cnt0+=cnt[i][0]
    cnt1+=cnt[i][1]
    if cnt0<cnt1:
        ok=False
if cnt0!=cnt1:
    ok=False
if ok:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()

n = int(input())
s = []
for _ in range(n):
    s.append(input())

inc = []
zeros = []
dec = []

for i, j in enumerate(s):
    minimum = 0
    now = 0
    for k in j:
        if k == "(":
            now += 1
        else:
            now -= 1
        minimum = min(minimum, now)
    if now > 0:
        inc.append([minimum, i])
    elif now < 0:
        dec.append([minimum, i])
    else:
        zeros.append([minimum, i])

inc.sort(reverse=True)
dec.sort()

now = 0

for i, j in inc:
    for k in s[j]:
        if k == "(":
            now += 1
        else:
            now -= 1
        if now < 0:
            print("No")
            sys.exit()
for i, j in zeros:
    for k in s[j]:
        if k == "(":
            now += 1
        else:
            now -= 1
        if now < 0:
            print("No")
            sys.exit()
for i, j in dec:
    for k in s[j]:
        if k == "(":
            now += 1
        else:
            now -= 1
        if now < 0:
            print("No")
            sys.exit()
ans = "Yes" if now == 0 else "No"
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()

n = int(input())
s = []
for _ in range(n):
    s.append(input())

A = []

for i, j in enumerate(s):
    min_val = 10**10
    val = 0
   
    for k in j:
        if k == "(":
            val += 1
        else:
            val -= 1
        min_val = min(min_val, val)
    A.append([min_val, i])
A.sort()
A = A[::-1]
val = 0
for i, j in A:
    for k in list(s[j]):
        if k == "(":
            val += 1
        else:
            val -= 1
            if val < 0:
                print("No")
                sys.exit()
ans = "Yes" if val == 0 else "No"
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()

n = int(input())
s = []
for _ in range(n):
    s.append(input())

A = []

for i, j in enumerate(s):
    min_val = 0
    val = 10**10
   
    for k in j:
        if k == "(":
            val += 1
        else:
            val -= 1
        min_val = min(min_val, val)
    A.append([min_val, i])
A.sort()
A = A[::-1]
val = 0
for i, j in A:
    for k in list(s[j]):
        if k == "(":
            val += 1
        else:
            val -= 1
            if val < 0:
                print("No")
                sys.exit()
ans = "Yes" if val == 0 else "No"
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()

n = int(input())
s = []
for _ in range(n):
    s.append(input())

A = []

for i, j in enumerate(s):
    min_val = 0
    val = 0
    for k in j:
        if k == "(":
            val += 1
        else:
            val -= 1
            min_val = min(min_val, val)
    A.append([min_val, i])
A.sort()
A = A[::-1]
val = 0
for i, j in A:
    for k in list(s[j]):
        if k == "(":
            val += 1
        else:
            val -= 1
            if val < 0:
                print("No")
                sys.exit()
ans = "Yes" if val == 0 else "No"
print(ans)

Submission status: Wrong Answer

Solution code:
from functools import reduce
n, *s = open(0).read().split()
u = []
for t in s:
    close_cnt = 0
    tmp = 0
    for c in t:
        tmp += (1 if c == '(' else -1)
        close_cnt = min(close_cnt, tmp)
    u.append((close_cnt, tmp - close_cnt))
M = 10**6 + 1
acc = 0
for a, b in sorted(u, key=lambda z: - M * (z[0] + z[1]) - (-z[1] if z[0] + z[1] < 0 else z[0])):
    if acc + a < 0:
        print("No")
        exit(0)
    else:
        acc += a + b
print(("No" if acc else "Yes"))

Submission status: Wrong Answer

Solution code:
from functools import reduce
n, *s = open(0).read().split()
u = []
for t in s:
    close_cnt = 0
    tmp = 0
    for c in t:
        tmp += (1 if c == '(' else -1)
        close_cnt = min(close_cnt, tmp)
    u.append((close_cnt, tmp - close_cnt))
M = 10**6 + 1
acc = 0
for a, b in sorted(u, key=lambda z: - M * (z[0] + z[1]) - (z[1] if z[0] + z[1] < 0 else z[0])):
    if acc + a < 0:
        print("No")
        exit(0)
    else:
        acc += a + b
print(("No" if acc else "Yes"))

Submission status: Wrong Answer

Solution code:
from functools import reduce
n, *s = open(0).read().split()
u = []
for t in s:
    close_cnt = 0
    tmp = 0
    for c in t:
        tmp += (1 if c == '(' else -1)
        close_cnt = min(close_cnt, tmp)
    u.append((close_cnt, tmp - close_cnt))
M = 10**6 + 1
acc = 0
for a, b in sorted(u, key=lambda z: - M * (z[0] + z[1]) + (z[1] if z[0] + z[1] < 0 else -z[0])):
    if acc + a < 0:
        print("No")
        exit(0)
    else:
        acc += a + b
print(("No" if acc else "Yes"))

Submission status: Wrong Answer

Solution code:
from functools import reduce
n, *s = open(0).read().split()
u = []
for t in s:
    close_cnt = 0
    tmp = 0
    for c in t:
        tmp += (1 if c == '(' else -1)
        close_cnt = min(close_cnt, tmp)
    u.append((close_cnt, tmp - close_cnt))
M = 10**6 + 1
acc = 0
for a, b in sorted(u, key=lambda z: - M * (z[0] + z[1]) - z[0]):
    if acc + a < 0:
        print("No")
        exit(0)
    else:
        acc += a + b
print(("No" if acc else "Yes"))

Submission status: Wrong Answer

Solution code:
from functools import reduce
n, *s = open(0).read().split()
u = []
for t in s:
    close_cnt = 0
    tmp = 0
    for c in t:
        tmp += (1 if c == '(' else -1)
        close_cnt = min(close_cnt, tmp)
    u.append((close_cnt, tmp - close_cnt))
M = 10**6 + 1
acc = 0
for a, b in sorted(u, key=lambda z: M * (z[0] + z[1]) - z[0]):
    if acc + a < 0:
        print("No")
        exit(0)
    else:
        acc += a + b
print(("No" if acc else "Yes"))

Submission status: Wrong Answer

Solution code:
from functools import reduce

n, *s = open(0).read().split()
u = []
for t in s:
    close_cnt = 0
    tmp = 0
    for c in t:
        tmp += (1 if c == '(' else -1)
        close_cnt = min(close_cnt, tmp)
    u.append((close_cnt, tmp - close_cnt))
M = 10**6 + 1
acc = 0
for a, b in sorted(u, key=lambda z: z[1] - M * z[0]):
    if acc + a < 0:
        print("No")
        exit(0)
    else:
        acc += a + b
print(("No" if acc else "Yes"))

Submission status: Wrong Answer

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

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

species = [(bend(s),s.count('(')-s.count(')')) for s in S]

ups = [(b,u) for b,u in species if u > 0]
flats = [(b,u) for b,u in species if u == 0]
downs = [(b,u) for b,u in species if u < 0]


ups.sort()
downs.sort()
high = 0
for b,u in ups[::-1]:
    if high + b < 0:
        print('No')
        exit()
    high += u

for b,u in flats:
    if high + b < 0:
        print('No')
        exit()

for b,u in downs:
    if high + b < 0:
        print('No')
        exit()
    high += u

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

Submission status: Wrong Answer

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

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

species = [(bend(s),s.count('(')-s.count(')')) for s in S]

ups = [(b,u) for b,u in species if u > 0]
flats = [(b,u) for b,u in species if u == 0]
downs = [(b,u) for b,u in species if u < 0]


ups.sort()
downs.sort()
high = 0
for b,u in ups[::-1]:
    if high + b < 0:
        print('No')
        exit()
    high += u

for b,u in flats:
    if high + b < 0:
        print('No')
        exit()

for b,u in downs[::-1]:
    if high + b < 0:
        print('No')
        exit()
    high += u

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

Submission status: Wrong Answer

Solution code:
class string:
    def __init__(self, i):
        self.i = i

N = int(input())
array = [string(i) for i in range(N)]
for i in range(N):
    array[i].contents = input()
# カッコを構成できるという事は(を+1、)を-1とした時に合計が0になる
# また、途中で負の数にならない
# 途中で負の数にならないようにするには単体で0以上のものから優先して足す
# 単体で負の数の瞬間が無いようにする
for i in range(N):
    minimum = 0
    total = 0
    for s in array[i].contents:
        if s == '(':
            total += 1
        else:
            total -= 1
        if minimum > total:
            minimum = total
    array[i].minimum = minimum
    array[i].total = total

#総和
total = 0
for i in range(N):
    total += array[i].total
if total != 0:
    print('No')
    exit()
for i in range(N):
    if array[i].total >= 0:
        array[i].left = True
    else:
        array[i].left = False
left = [array[i] for i in range(N) if array[i].left]
right = [array[i] for i in range(N) if array[i].left != True]
leftresult = sorted(left, key=lambda a: a.minimum, reverse=1)
rightresult = sorted(right, key=lambda a: a.minimum, reverse=1)
total = 0

for each in leftresult:
    if total + each.minimum < 0:
        print('No')
        exit()
    total += each.total
for each in rightresult:
    if total + each.minimum < 0:
        print('No')
        exit()
    total += each.total

print('Yes')

Submission status: Wrong Answer

Solution code:
n=int(input())
pos=[]
neg=[]
for i in range(n):
    s=input()
    bal=0
    mn=0
    for ch in s:
        if ch=='(':
            bal+=1
        if ch==')':
            bal-=1
        mn=min(mn,bal)
    if -mn<bal-mn:
        pos.append((-mn,bal-mn))
    else:
        neg.append((-mn,bal-mn))
pos.sort()
neg.sort(reverse=True)
bal=0
ok=True
for (m,b) in pos:
    if bal-m<0:
        ok=False
    bal+=b-m
for (m,b) in neg:
    if bal-m<0:
        ok=False
    bal+=b-m
if bal!=0:
    ok=False
if ok:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
n=int(input())
pos=[]
neg=[]
for i in range(n):
    s=input()
    bal=0
    mn=0
    for ch in s:
        if ch=='(':
            bal+=1
        if ch==')':
            bal-=1
        mn=min(mn,bal)
    if bal>=0:
        pos.append((mn,bal))
    else:
        neg.append((mn,bal))
def cmp(it):
    return (it[0],-it[1])
pos.sort(reverse=True,key=cmp)
neg.sort(key=cmp)
bal=0
ok=True
for (m,b) in pos:
    if bal+m<0:
        ok=False
    bal+=b
for (m,b) in neg:
    if bal+m<0:
        ok=False
    bal+=b
if bal!=0:
    ok=False
if ok:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
n=int(input())
pos=[]
neg=[]
for i in range(n):
    s=input()
    bal=0
    mn=0
    for ch in s:
        if ch=='(':
            bal+=1
        if ch==')':
            bal-=1
        mn=min(mn,bal)
    if bal>0:
        pos.append((mn,bal))
    else:
        neg.append((mn,bal))
def cmp(it):
    return (it[0],it[1])
pos.sort(reverse=True,key=cmp)
neg.sort(key=cmp)
bal=0
ok=True
for (m,b) in pos:
    if bal+m<0:
        ok=False
    bal+=b
for (m,b) in neg:
    if bal+m<0:
        ok=False
    bal+=b
if bal!=0:
    ok=False
if ok:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
n=int(input())
pos=[]
neg=[]
for i in range(n):
    s=input()
    bal=0
    mn=0
    for ch in s:
        if ch=='(':
            bal+=1
        if ch==')':
            bal-=1
        mn=min(mn,bal)
    if bal>0:
        pos.append((mn,bal))
    else:
        neg.append((mn,bal))
def cmp(it):
    return (it[0],-it[1])
pos.sort(reverse=True,key=cmp)
neg.sort(key=cmp)
bal=0
ok=True
for (m,b) in pos:
    if bal+m<0:
        ok=False
    bal+=b
for (m,b) in neg:
    if bal+m<0:
        ok=False
    bal+=b
if bal!=0:
    ok=False
if ok:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
n=int(input())
pos=[]
neg=[]
for i in range(n):
    s=input()
    bal=0
    mn=0
    for ch in s:
        if ch=='(':
            bal+=1
        if ch==')':
            bal-=1
        mn=min(mn,bal)
    if bal>=0:
        pos.append((mn,bal))
    else:
        neg.append((mn,bal))
def cmp(it):
    return it[0]
pos.sort(reverse=True,key=cmp)
neg.sort(key=cmp)
bal=0
ok=True
for (m,b) in pos:
    if bal+m<0:
        ok=False
    bal+=b
for (m,b) in neg:
    if bal+m<0:
        ok=False
    bal+=b
if bal!=0:
    ok=False
if ok:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
n=int(input())
pos=[]
neg=[]
for i in range(n):
    s=input()
    bal=0
    mn=0
    for ch in s:
        if ch=='(':
            bal+=1
        if ch==')':
            bal-=1
        mn=min(mn,bal)
    if bal>=0:
        pos.append((mn,bal))
    else:
        neg.append((mn,bal))
pos.sort(reverse=True)
neg.sort()
bal=0
ok=True
for (m,b) in pos:
    if bal+m<0:
        ok=False
    bal+=b
for (m,b) in neg:
    if bal+m<0:
        ok=False
    bal+=b
if bal!=0:
    ok=False
if ok:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
n=int(input())
pos=[]
neg=[]
for i in range(n):
    s=input()
    bal=0
    mn=0
    for ch in s:
        if ch=='(':
            bal+=1
        else:
            bal-=1
        mn=min(mn,bal)
    if bal>=0:
        pos.append((mn,bal))
    else:
        neg.append((mn,bal))
pos.sort()
neg.sort(reverse=True)
bal=0
ok=True
for (m,b) in pos:
    if bal+m<0:
        ok=False
    bal+=b
for (m,b) in neg:
    if bal+m<0:
        ok=False
    bal+=b
if bal!=0:
    ok=False
if ok:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000000)
import math
from math import gcd
def lcm(a, b): return a * b // gcd(a, b)
from itertools import count, permutations, chain
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok

def get_inv(n, modp):
    return pow(n, modp-2, modp)

def factorials_list(n, modp):    # 10**6
    fs = [1]
    for i in range(1, n+1):
        fs.append(fs[-1] * i % modp)
    return fs

def invs_list(n, fs, modp):     # 10**6
    invs = [get_inv(fs[-1], modp)]
    for i in range(n, 1-1, -1):
        invs.append(invs[-1] * i % modp)
    invs.reverse()
    return invs

def comb(n, k, modp):
    num = 1
    for i in range(n, n-k, -1):
        num = num * i % modp
    den = 1
    for i in range(2, k+1):
        den = den * i % modp
    return num * get_inv(den, modp) % modp

def comb_from_list(n, k, modp, fs, invs):   
    return fs[n] * invs[n-k] * invs[k] % modp

#

class UnionFindEx:
    def __init__(self, size):
        #正なら根の番号、負ならグループサイズ
        self.roots = [-1] * size
    def getRootID(self, i):
        r = self.roots[i]
        if r < 0:   #負なら根
            return i
        else:
            r = self.getRootID(r)
            self.roots[i] = r
            return r
    def getGroupSize(self, i):
        return -self.roots[self.getRootID(i)]
    def connect(self, i, j):
        r1, r2 = self.getRootID(i), self.getRootID(j)
        if r1 == r2:
            return False
        if self.getGroupSize(r1) < self.getGroupSize(r2):
            r1, r2 = r2, r1
        self.roots[r1] += self.roots[r2]    #サイズ更新
        self.roots[r2] = r1
        return True

Yes = 'Yes'
No = 'No'


def main():
    N=ii()
    up = []
    downup = []
    down = []
    for _ in range(N):
        S = input()
        h = 0
        b = 0
        for s in S:
            if s=='(':
                h += 1
            else:
                h -= 1
                b = min(b, h)
        #
        if b>=0:
            up.append((h, b))
        elif h>=0:
            downup.append((h, b))
        else:
            down.append((h, b))
    #
    downup.sort(key=lambda t: t[1]-t[0], reverse=True)
    down.sort(key=lambda t: t[0]-t[1], reverse=True)
    H = sum(h for h, b in up)
    for h, b in downup:
        if H+b>=0:
            H += h
        else:
            print(No)
            return
    for h, b in down:
        H += h
    #
    if H == 0:
        print(Yes)
    else:
        print(No)





main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000000)
import math
from math import gcd
def lcm(a, b): return a * b // gcd(a, b)
from itertools import count, permutations, chain
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok

def get_inv(n, modp):
    return pow(n, modp-2, modp)

def factorials_list(n, modp):    # 10**6
    fs = [1]
    for i in range(1, n+1):
        fs.append(fs[-1] * i % modp)
    return fs

def invs_list(n, fs, modp):     # 10**6
    invs = [get_inv(fs[-1], modp)]
    for i in range(n, 1-1, -1):
        invs.append(invs[-1] * i % modp)
    invs.reverse()
    return invs

def comb(n, k, modp):
    num = 1
    for i in range(n, n-k, -1):
        num = num * i % modp
    den = 1
    for i in range(2, k+1):
        den = den * i % modp
    return num * get_inv(den, modp) % modp

def comb_from_list(n, k, modp, fs, invs):   
    return fs[n] * invs[n-k] * invs[k] % modp

#

class UnionFindEx:
    def __init__(self, size):
        #正なら根の番号、負ならグループサイズ
        self.roots = [-1] * size
    def getRootID(self, i):
        r = self.roots[i]
        if r < 0:   #負なら根
            return i
        else:
            r = self.getRootID(r)
            self.roots[i] = r
            return r
    def getGroupSize(self, i):
        return -self.roots[self.getRootID(i)]
    def connect(self, i, j):
        r1, r2 = self.getRootID(i), self.getRootID(j)
        if r1 == r2:
            return False
        if self.getGroupSize(r1) < self.getGroupSize(r2):
            r1, r2 = r2, r1
        self.roots[r1] += self.roots[r2]    #サイズ更新
        self.roots[r2] = r1
        return True

Yes = 'Yes'
No = 'No'


def main():
    N=ii()
    up = []
    down = []
    for _ in range(N):
        S = input()
        h = 0
        b = 0
        for s in S:
            if s=='(':
                h += 1
            else:
                h -= 1
                b = min(b, h)
        #
        if h>=0:
            up.append((h, b))
        else:
            down.append((h, b))
    #
    up.sort(key=lambda t: t[1]-t[0], reverse=True)
    down.sort(key=lambda t: t[0]-t[1], reverse=True)
    H = 0
    for h, b in up:
        if H+b>=0:
            H += h
        else:
            print(No)
            return
    for h, b in down:
        H += h
    #
    if H == 0:
        print(Yes)
    else:
        print(No)





main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000000)
import math
from math import gcd
def lcm(a, b): return a * b // gcd(a, b)
from itertools import count, permutations, chain
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok

def get_inv(n, modp):
    return pow(n, modp-2, modp)

def factorials_list(n, modp):    # 10**6
    fs = [1]
    for i in range(1, n+1):
        fs.append(fs[-1] * i % modp)
    return fs

def invs_list(n, fs, modp):     # 10**6
    invs = [get_inv(fs[-1], modp)]
    for i in range(n, 1-1, -1):
        invs.append(invs[-1] * i % modp)
    invs.reverse()
    return invs

def comb(n, k, modp):
    num = 1
    for i in range(n, n-k, -1):
        num = num * i % modp
    den = 1
    for i in range(2, k+1):
        den = den * i % modp
    return num * get_inv(den, modp) % modp

def comb_from_list(n, k, modp, fs, invs):   
    return fs[n] * invs[n-k] * invs[k] % modp

#

class UnionFindEx:
    def __init__(self, size):
        #正なら根の番号、負ならグループサイズ
        self.roots = [-1] * size
    def getRootID(self, i):
        r = self.roots[i]
        if r < 0:   #負なら根
            return i
        else:
            r = self.getRootID(r)
            self.roots[i] = r
            return r
    def getGroupSize(self, i):
        return -self.roots[self.getRootID(i)]
    def connect(self, i, j):
        r1, r2 = self.getRootID(i), self.getRootID(j)
        if r1 == r2:
            return False
        if self.getGroupSize(r1) < self.getGroupSize(r2):
            r1, r2 = r2, r1
        self.roots[r1] += self.roots[r2]    #サイズ更新
        self.roots[r2] = r1
        return True

Yes = 'Yes'
No = 'No'


def main():
    N=ii()
    up = []
    down = []
    for _ in range(N):
        S = input()
        h = 0
        b = 0
        for s in S:
            if s=='(':
                h += 1
            else:
                h -= 1
                b = min(b, h)
        #
        if h>=0:
            up.append((h, b))
        else:
            down.append((h, b))
    #
    up.sort(key=lambda t: t[1], reverse=True)
    down.sort(key=lambda t: t[0]-t[1], reverse=True)
    H = 0
    for h, b in up:
        if H+b>=0:
            H += h
        else:
            print(No)
            return
    for h, b in down:
        H += h
    #
    if H == 0:
        print(Yes)
    else:
        print(No)





main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000000)
import math
from math import gcd
def lcm(a, b): return a * b // gcd(a, b)
from itertools import count, permutations, chain
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok

def get_inv(n, modp):
    return pow(n, modp-2, modp)

def factorials_list(n, modp):    # 10**6
    fs = [1]
    for i in range(1, n+1):
        fs.append(fs[-1] * i % modp)
    return fs

def invs_list(n, fs, modp):     # 10**6
    invs = [get_inv(fs[-1], modp)]
    for i in range(n, 1-1, -1):
        invs.append(invs[-1] * i % modp)
    invs.reverse()
    return invs

def comb(n, k, modp):
    num = 1
    for i in range(n, n-k, -1):
        num = num * i % modp
    den = 1
    for i in range(2, k+1):
        den = den * i % modp
    return num * get_inv(den, modp) % modp

def comb_from_list(n, k, modp, fs, invs):   
    return fs[n] * invs[n-k] * invs[k] % modp

#

class UnionFindEx:
    def __init__(self, size):
        #正なら根の番号、負ならグループサイズ
        self.roots = [-1] * size
    def getRootID(self, i):
        r = self.roots[i]
        if r < 0:   #負なら根
            return i
        else:
            r = self.getRootID(r)
            self.roots[i] = r
            return r
    def getGroupSize(self, i):
        return -self.roots[self.getRootID(i)]
    def connect(self, i, j):
        r1, r2 = self.getRootID(i), self.getRootID(j)
        if r1 == r2:
            return False
        if self.getGroupSize(r1) < self.getGroupSize(r2):
            r1, r2 = r2, r1
        self.roots[r1] += self.roots[r2]    #サイズ更新
        self.roots[r2] = r1
        return True

Yes = 'Yes'
No = 'No'


def main():
    N=ii()
    up = []
    down = []
    for _ in range(N):
        S = input()
        h = 0
        b = 0
        for s in S:
            if s=='(':
                h += 1
            else:
                h -= 1
                b = min(b, h)
        #
        if h>=0:
            up.append((h, b))
        else:
            down.append((h, b))
    #
    up.sort(key=lambda t: t[1], reverse=True)
    down.sort(key=lambda t: t[1], reverse=True)
    H = 0
    for h, b in up:
        if H+b>=0:
            H += h
        else:
            print(No)
            return
    for h, b in down:
        H += h
    #
    if H == 0:
        print(Yes)
    else:
        print(No)





main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000000)
import math
from math import gcd
def lcm(a, b): return a * b // gcd(a, b)
from itertools import count, permutations, chain
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok

def get_inv(n, modp):
    return pow(n, modp-2, modp)

def factorials_list(n, modp):    # 10**6
    fs = [1]
    for i in range(1, n+1):
        fs.append(fs[-1] * i % modp)
    return fs

def invs_list(n, fs, modp):     # 10**6
    invs = [get_inv(fs[-1], modp)]
    for i in range(n, 1-1, -1):
        invs.append(invs[-1] * i % modp)
    invs.reverse()
    return invs

def comb(n, k, modp):
    num = 1
    for i in range(n, n-k, -1):
        num = num * i % modp
    den = 1
    for i in range(2, k+1):
        den = den * i % modp
    return num * get_inv(den, modp) % modp

def comb_from_list(n, k, modp, fs, invs):   
    return fs[n] * invs[n-k] * invs[k] % modp

#

class UnionFindEx:
    def __init__(self, size):
        #正なら根の番号、負ならグループサイズ
        self.roots = [-1] * size
    def getRootID(self, i):
        r = self.roots[i]
        if r < 0:   #負なら根
            return i
        else:
            r = self.getRootID(r)
            self.roots[i] = r
            return r
    def getGroupSize(self, i):
        return -self.roots[self.getRootID(i)]
    def connect(self, i, j):
        r1, r2 = self.getRootID(i), self.getRootID(j)
        if r1 == r2:
            return False
        if self.getGroupSize(r1) < self.getGroupSize(r2):
            r1, r2 = r2, r1
        self.roots[r1] += self.roots[r2]    #サイズ更新
        self.roots[r2] = r1
        return True

Yes = 'Yes'
No = 'No'


def main():
    N=ii()
    up = []
    downup = []
    down = []
    for _ in range(N):
        S = input()
        h = 0
        b = 0
        for s in S:
            if s=='(':
                h += 1
            else:
                h -= 1
                b = min(b, h)
        #
        if b>=0:
            up.append((h, b))
        elif h>=0:
            downup.append((h, b))
        else:
            down.append((h, b))
    #
    downup.sort(key=lambda t: t[1], reverse=True)
    H = sum(h for h, b in up)
    for h, b in downup:
        if H+b>=0:
            H += h
        else:
            print(No)
            return
    for h, b in down:
        H += h
    #
    if H == 0:
        print(Yes)
    else:
        print(No)





main()

Submission status: Wrong Answer

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

first_list = []
last_list = []
for i in range(n):
    s = slist[i]

    a_count = 0
    b_count = 0
    min_s = ""
    for c in s:
        if c == ")":
            b_count-=1
        else:
            b_count+=1
        if b_count < 0:
            b_count = 0
            a_count+= 1
    min_s = ")"* a_count + "("*b_count

    ai = len(min_s)-b_count
    bi = b_count
    if bi-ai >= 0:
        first_list.append([min_s,ai])
    else:
        last_list.append([min_s,bi])

sorted(first_list, key=lambda s: s[1])
sorted(last_list, key=lambda s: s[1], reverse=True)

ans = ""
for i in range(len(first_list)):
    ans += first_list[i][0]
for i in range(len(last_list)):
    ans += last_list[i][0]

a_count = 0
b_count = 0
min_s = ""
for c in s:
    if c == ")":
        b_count-=1
    else:
        b_count+=1
    if b_count < 0:
        b_count = 0
        a_count+= 1

if a_count == 0 and b_count == 0:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

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

first_list = []
last_list = []
for i in range(n):
    s = slist[i]

    b_count = 0
    min_s = ""
    for c in s:
        if c == ")":
            b_count-=1
        else:
            b_count+=1
        if b_count < 0:
            b_count = 0
            min_s += ")"
    min_s += "("*b_count

    ai = len(min_s)-b_count
    bi = b_count
    if len(min_s) != 0:
        if bi-ai >= 0:
            first_list.append([min_s,ai])
        else:
            last_list.append([min_s,bi])

sorted(first_list, key=lambda s: s[1])
sorted(last_list, key=lambda s: s[1], reverse=True)

ans = ""
for i in range(len(first_list)):
    ans += first_list[i][0]
for i in range(len(last_list)):
    ans += last_list[i][0]

b_count = 0
min_s = ""
for c in ans:
    if c == ")":
        b_count-=1
    else:
        b_count+=1
    if b_count < 0:
        b_count = 0
        min_s += ")"
min_s += "("*b_count

if min_s == "":
    print("Yes")
else:
    print("No")