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:
n = int(input())
l = [0 for _ in range(n)]
r = [0 for _ in range(n)]
l_count = 0
r_count = 0
for i in range(n):
    s = input()
    if s[0] == '(':
        l[i] += 1
    if s[-1] == ')':
        r[i] += 1
    l_count += s.count('(')
    r_count += s.count(')')
if l_count != r_count:
    print('No')
elif sum(l) == 1 and sum(r) == 1:
    if l.index(1)==r.index(1):
        print('No')
else:
    print('Yes')

Submission status: Wrong Answer

Solution code:
n = int(input())
s = [""]*n
dp = [[] for i in range(n+1)]
plus = []
minas = []
pgomi = []
mgomi = []
kosu = 0
for i in range(n):
    s[i] = input()
    dp[i] = [0]*(len(s[i]) + 1)
    check = True
    kosu += len(s[i])
    for j in range(len(s[i])):
        p = 0
        if s[i][j] == '(':p = 1
        else:p = -1
        dp[i][j+1] = dp[i][j] + p
        if dp[i][j+1] < 0:
            check = False
    saisyo = min(dp[i])
    if saisyo >= 0:plus.append(i)
    elif saisyo == dp[i][-1]:minas.append(i)
    elif dp[i][-1] >= 0:pgomi.append(i)
    else:mgomi.append(i)
minas.sort()
ruiseki = [0]*(10**6+5)
idx = 0
for i in plus + pgomi + mgomi + minas:
    for j in range(len(s[i])):
        p = 0
        if s[i][j] == '(':p = 1
        else:p = -1
        ruiseki[idx+1] = ruiseki[idx] + p
        idx += 1
check = True
for i in range(kosu):
    if ruiseki[i+1] < 0:
        check = False
        break
if check == False or ruiseki[kosu] != 0:
    print("No")
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

    neg1.sort(reverse = True, key = lambda x: x[0])
    for min_v, v in neg1:
        if u + min_v < 0:
            return "No"
        else:
            u += v

    neg2.sort(reverse = True, key = lambda x: x[0])
    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:
n = int(input())
l = []
#[c,d]c=right d=left
for i in range(n):
    s = list(input())
    c = 0
    d = 0
    for j in range(len(s)):
        if s[j] == "(":
            c += 1
        else:
            if c > 0:
                c -= 1
            else:
                d += 1
    l.append([c,d])
key = [0,0,0]
ac = 0
ad = 0
for i in range(n):
    c,d = l[i]
    if c == 0:
        if d == 0:
            key[2] += 1
        else:
            key[0] += 1
    else:
        if d == 0:
            key[1] += 1
    ac += c
    ad += d
if ac == ad:
    if key[0] > 0 and key[1] > 0:
        print("Yes")
    else:
        print("No")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
n = int(input())
data = []
for i in range(n):
    s = input()
    k = len(s) - s.count(')')
    data.append([k,s])
data.sort(reverse=True,key=lambda x: x[0])
ans = 0
for i in range(len(data)):
    for j in list(data[i][1]):
        if j == '(':
            ans += 1
        else:
            ans -= 1
        if ans < 0:
            print("No")
            exit()
if ans == 0:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    S = [input() for _ in range(N)]
    L = []
    for i in range(N):
        t = 0
        mint = 1
        for s in S[i]:
            if s == "(":
                t += 1
            else:
                t -= 1
            mint = min(mint, t)
        L.append((t, mint))
    L.sort(key=lambda x: x[0], reverse=True)
    L.sort(key=lambda x: x[1], reverse=True)
    t = 0
    for l, m in L:
        if t + m < 0:
            return False
        t += l
        if t < 0:
            return False
    if t == 0:
        return True
    return False


if main():
    print("Yes")
else:
    print("NO")

Submission status: Wrong Answer

Solution code:
import bisect
import copy
import heapq
import sys
import itertools
import math
import queue
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
# mod = 10 ** 9 + 7
mod = 998244353 

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]
def init_dp1(init, N): return [init for _ in range(N)]
def init_dp2(init, N, M): return [[init for _ in range(M)] for _ in range(N)]


class V:
    def __init__(self, f, v=None):
        self.f = f
        self.v = v
 
    def __str__(self):
        return str(self.v)
 
    def ud(self, n):
        if n is None:
            return

        if self.v is None:
            self.v = n
            return
        self.v = self.f(self.v, n) 


def f(S):
    l = 0
    r = 0
    for s in S:
        if s == ")":
            if l > 0:
                l -= 1
            else:
                r += 1
        else:
            l += 1
    return (l, r)


def main():
    N = int(input())
    S = list(input().strip() for _ in range(N))

    F = list(map(f, S))

    l_0 = set()
    r_0 = set()
    l_n = 0
    r_n = 0
    for i, (l, r) in enumerate(F):
        if l == 0 and len(l_0) < 2:
            l_0.add(i)
        if r == 0 and len(r_0) < 2:
            r_0.add(i)
        l_n += l
        r_n += r
        
    if len(l_0) == 1 and len(r_0) == 1:
        if l_0 == r_0:
            print("No")
            return

    print("Yes" if l_n == r_n else "No")


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())

memo = []
for i in range(N):
  min_n = 0
  sum_n = 0
  S = input()
  for s in S:
    if s==')':
      sum_n -= 1
      min_n = min(min_n, sum_n)
    else:
      sum_n += 1
  memo.append([min_n, sum_n])

memo.sort(reverse=True)
now = 0
for m, n in memo:
  if now + m < 0:
    print('No')
    quit()
  else:
    now += n

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

Submission status: Wrong Answer

Solution code:
N=int(input())
S=[]
L=0
R=0
for i in range(N):
    s=input()
    n=len(s)
    data=[s[j] for j in range(n)]
    l=0
    r=0
    yabai=float("inf")
    for j in range(n):
        l+=(s[j]=="(")
        r+=(s[j]==")")
        yabai=min(l-r,yabai)
    S.append([yabai,l-r])
    L+=l
    R+=r

if L!=R:
    print("No")
else:
    first=[]
    last=[]
    for i in range(N):
        yabai,gap=S[i]
        if gap>0:
            first.append(S[i])
        else:
            last.append(S[i])
    first.sort(reverse=True)
    last.sort(reverse=True)
    G=0
    for i in range(len(first)):
        yabai,gap=first[i]
        if 0>G+yabai:
            print("No")
            exit()
        else:
            G+=gap
    for j in range(len(last)):
        yabai,gap=last[j]
        if 0>G+yabai:
            print("No")
            break
        else:
            G+=gap
    else:
        print("Yes")

Submission status: Wrong Answer

Solution code:
n = int(input())
left = []
mid = []
right = []
L = []
R = []

for i in range(n):
    s = input()
    l = 0
    r = 0
    for x in s:
        if x == '(':
            l += 1
        else:
            if l > 0:
                l -= 1
            else:
                r += 1
    if l > 0 and r == 0:
        left.append((l, r))
    elif l > 0 and r > 0:
        mid.append((r, l))  # a,b-a
    elif l == 0 and r > 0:
        right.append((l, r))
    L.append(l)
    R.append(r)

if sum(L) != sum(R):
    print('No')
    exit()

A = 0
B = 0
for x in left:
    A += x[0]
for x in right:
    B += x[1]

mid = sorted(mid, key=lambda x: (x[0],-x[1]))
l = A
r = 0
for a, b in mid:
    if l < a:
        print('No')
        exit()
    l -= a
    l += b

print('Yes')

Submission status: Wrong Answer

Solution code:
n = int(input())

l = []

for _ in range(n):
    s = input()
    s = s.replace("(", "3").replace(")", "1")
    s = list(map(int, s))
    l.append(sum(s) - len(s) * 2)

print("Yes" if sum(l) == 0 else "No")

Submission status: Wrong Answer

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

balance = [0 for _ in range(n)]
min_balance = [0 for i in range(n)]

for i in range(n):
	cur_bal = 0
	for j in range(len(s[i])):
		if s[i][j] == "(":
			cur_bal += 1
		else:
			cur_bal -= 1
		if cur_bal < min_balance[i]:
			min_balance[i] = cur_bal
	balance[i] = cur_bal

# for i in range(n):
# 	print("balance", balance[i])
# 	print("min_balance", min_balance[i])
# 	print()

# order = sorted(range(n), key = lambda x: (min_balance[x], balance[x]))
order = sorted(zip(min_balance, balance), reverse=True)

flag_good = True
cur_balance = 0
for i in range(n):
	if order[i][0] + cur_balance >= 0:
		cur_balance += order[i][1]
	else:
		flag_good = False
		break

if flag_good and cur_balance == 0:
	print("Yes")
else:
	print("No")

Submission status: Wrong Answer

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product
from math import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

n=int(input())
s=[input() for i in range(n)]
lst=[[0]*2 for i in range(n)]

for i in range(n):
    l,r=0,0
    for j in range(len(s[i])):
        if s[i][j]==")":
            if r==0:
                l+=1
            else:
                r-=1
        if s[i][j]=="(":
            r+=1
    lst[i][0]=l
    lst[i][1]=r
# print(lst)
lst.sort(key=lambda x: (x[0],-x[1]))
# print(lst)
tmp=0
for i in range(n):
    tmp-=lst[i][0]
    if tmp<0:
        print("No")
        break
    tmp+=lst[i][1]
else:
    if tmp==0:
        print("Yes")
    else:
        print("No")

Submission status: Wrong Answer

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

N = int(input())
S = [input().rstrip() for _ in range(N)]

def calc(S):
    now = 0
    ret = 0
    for s in S:
        if s == '(':
            now += 1
        else:
            now -= 1
        ret = min(ret, now)
    return ret

T = [(calc(s), s) for s in S]
T.sort(key=lambda a: a[0], reverse=True)
ans = ''.join([s for _, s in T])

# H = []
# P = []
# L = []

# for s in S:
#     less = -calc(s)
#     if less == 0:
#         H.append(s)
#     else:
#         l = s.count('(')
#         r = len(s) - l
#         if l >= r:
#             P.append((less, s))
#         else:
#             L.append((less, s))

# P.sort(key=lambda a: a[0])
# L.sort(key=lambda a: a[0], reverse=True)
# P = [s for _, s in P]
# L = [s for _, s in L]
# ans = ''.join(H + P + L)

l = ans.count('(')
r = ans.count(')')

if l == r and calc(ans) == 0:
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

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


ruiseki = [[] for i in range(n)]

for i in range(n):
    ruiseki[i].append(0)
    for char in s[i]:
        if char == "(":
            ruiseki[i].append(ruiseki[i][-1] + 1)
        else:
            ruiseki[i].append(ruiseki[i][-1] - 1)
min_ = [0] * n
sum_ = [0] * n

for i in range(n):
    min_[i] = min(ruiseki[i])
    sum_[i] = ruiseki[i][-1]

info = [(min_[i], sum_[i]) for i in range(n)]
info = sorted(info, reverse=True)

now_m = 0
now_s = 0

for mi, su in info:
    if now_s + mi < 0:
        print("No")
        exit()
    now_s += su
    
if now_s == 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)]
lr=[]
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 or r:
        lr.append([l,r])
lr.sort(key=lambda x:x[0]*x[1],reverse=True)
idleR=10**7
#print(lr)
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])


        stack=nstack
    #print(stack)
    if not stack or [0,0] in stack:
        print("Yes")
    else:
        print("No")
else:
    print("Yes")

Submission status: Wrong Answer

Solution code:
import heapq

N = int(input())
S = [input() for _ in range(N)]
B = []
for s in S:
    ncl = nop = 0
    for c in s:
        if c=='(':
            nop+=1
        else:
            if nop>0: nop-=1
            else: ncl+=1

    B.append((nop-ncl, ncl))

B = sorted(B, key=lambda x:x[1])
h = []
x = 0
ib = 0
while True:
    while ib<N:
        b = B[ib]
        if b[1]>x: break
        heapq.heappush(h, b)
        ib += 1

    if len(h)==0:
        break

    c = heapq.heappop(h)
    if c[1]>x:
        print('No')
        exit()
        
    x += c[0]

print('Yes' if ib==N and x==0 else 'No')

Submission status: Wrong Answer

Solution code:
import heapq

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

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

Submission status: Wrong Answer

Solution code:
def f_bracket_sequencing():
    N = int(input())
    Brackets = [input() for _ in range(N)]

    strings = ''
    for s in Brackets:
        left, right = 0, 0
        flag = True
        for ch in s:
            if ch == '(':
                left += 1
            else:
                right += 1
            if left < right:
                flag = False
        if left > right:
            strings = s + strings
        elif left < right:
            strings += s
        elif left == right:
            if flag:
                pass
            else:
                strings += s

    left, right = 0, 0
    for ch in strings:
        if ch == '(':
            left += 1
        else:
            right += 1
        if left < right:
            return 'No'
    return 'Yes' if left == right else 'No'

print(f_bracket_sequencing())

Submission status: Wrong Answer

Solution code:
def RunLengthEncoding(S):
    res = []
    N = len(S)
    i = 0
    while i < N:
        cnt = 1
        while i < N - 1 and S[i] == S[i + 1]:
            cnt += 1
            i += 1
        res.append([S[i], cnt])
        i += 1

    while True:
        res2 = omit(res)
        if res == res2:
            return res2
        res = res2


def omit(RLE):
    res = []
    i = 0
    while i < len(RLE):
        k, v = RLE[i]
        if k == ")":
            res.append([k, v])
            i += 1
            continue
        if i >= len(RLE) - 1:
            res.append([k, v])
            break

        kk, y = RLE[i + 1]
        if v > min(v, y):
            res.append([k, v - min(v, y)])
        if y > min(v, y):
            res.append([kk, y - min(v, y)])
        i += 2
    if res:
        res = merge(res)
    return res


def merge(RLE):
    res = []
    res.append(RLE[0])
    for i in range(1, len(RLE)):
        k, v = RLE[i]
        if res[-1][0] != k:
            res.append([k, v])
        else:
            res[-1][1] += v
    return res


if __name__ == "__main__":
    N = int(input())
    tmp = []
    for _ in range(N):
        RLE = RunLengthEncoding(input())
        if RLE:
            tmp.append(RLE)

    outR = 0
    outL = 0
    LR = []
    for b in tmp:
        if len(b) == 1:
            k, v = b[0]
            if k == "(":
                outR += v
            else:
                outL += v
        else:
            _, v1 = b[0]
            _, v2 = b[1]
            LR.append((v1, -v2))

    LR.sort()
    for l, r in LR:
        if outR < l:
            print("No")
            exit()
        outR = outR - l - r

    if outR == outL:
        print("Yes")
    else:
        print("No")

Submission status: Wrong Answer

Solution code:
#0や1のケースに注意
#index out of range

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())
    left = 0
    right = 0
    flag = 0
    ss = []
    for i in range(n):
        s = input().rstrip()
        ss.append(s)
    for s in ss:
        if s[0] == '(':
            for i in s:
                if i=='(':
                    left += 1
                else:
                    left -= 1
        else:
            for i in s:
                if i == ')':
                    right += 1
                else:
                    right -= 1
            if s[-1] == ')':
                flag = 1
    if flag == 1 and left == right:
        left = 0
        right = 0
        flag = 0
        for s in ss:
            s = s[::-1]
            if s[0] == '(':
                for i in s:
                    if i=='(':
                        left += 1
                    else:
                        left -= 1
            else:
                for i in s:
                    if i == ')':
                        right += 1
                    else:
                        right -= 1
                if s[-1] == ')':
                    flag = 1
        if flag == 1 and left == right:
            print('Yes')
        else:
            print('No')
    else:
        print('No')


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
LR = []
idx = -1
nr = -1
minus = []
plus = []
for i in range(n):
    S = input()
    l = 0
    r = 0
    for s in S:
        if s == "(":
            r += 1
        else:
            if r > 0:
                r -= 1
            else:
                l += 1
    LR.append((l, r))
    if l == 0:
        if r > nr:
            nr = r
            idx = i
if idx == -1:
    print("No")
    exit()
for i in range(n):
    if i == idx:
        continue
    l, r = LR[i]
    if r - l >= 0:
        plus.append((l, r-l))
    else:
        minus.append((l, r-l))
plus.sort()
minus.sort(reverse=True)
for l, k in plus:
    if nr < l:
        print("No")
        exit()
    nr += k
for l, k in minus:
    if nr < l:
        print("No")
        exit()
    nr += k
if nr != 0:
    print("No")
else:
    print("Yes")

Submission status: Wrong Answer

Solution code:
def task(n, s):
    deltas = []

    for ss in s:
        localleft = 0
        localright = 0

        for c in ss:
            if c == '(':
                localleft += 1
            elif c == ')':
                if localleft > 0:
                    localleft -= 1
                else:
                    localright += 1

        if localleft > 0 or localright > 0:
            deltas.append([localleft, localright])

    deltas = sorted(deltas, key=lambda x: x[1])
    total = 0

    for delta in deltas:
        total -= delta[1]

        if total < 0:
            print("No")
            return

        total += delta[0]

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


n = int(input())
s = []
for i in range(0, n):
    s.append(input())
task(n, s)

Submission status: Wrong Answer

Solution code:
n,*s=open(0)
n=int(n)
f=g=h=a=b=0
for t in s:
    c=l=r=d=0
    for u in t[:-1]:
        if u=='(':
            if d<0:d=0
            d+=1
            r+=1
        else:
            d-=1
            if d>=0:c+=1
            l+=1
    x=r-c
    y=l-c
    if x==0:f=1
    elif y==0:g=1
    a+=x
    b+=y
if f and g and a==b:
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
cnt=[]
for i in range(n):
	s=input().rstrip()
	l=s.count("(")
	r=s.count(")")
	minus=0
	now=0
	for j in range(len(s)):
		if s[j]=="(":
			now+=1
		else:
			now-=1
			minus=min(minus,now)
	cnt.append((l,r,s,minus))
cnt.sort(key=lambda x:x[1]-x[0])
plus=[]
minus=[]
for x in cnt:
	if x[0]-x[1]>=0:
		plus.append(x)
	else:
		minus.append(x)
plus.sort(key=lambda x:-x[3])
minus.sort(key=lambda x:x[3])
l=r=0
for x in plus:
	for i in range(len(x[2])):
		if x[2][i]=="(":
			l+=1
		else:
			r+=1
		if l<r:
			print("No")
			exit()
for x in minus:
	for i in range(len(x[2])):
		if x[2][i]=="(":
			l+=1
		else:
			r+=1
		if l<r:
			print("No")
			exit()
if l==r:
	print("Yes")
else:
	print("No")

Submission status: Wrong Answer

Solution code:
#!/bin/bash
''':'
docker run --rm -it -v $(cd $(dirname $0) && pwd):/vo:ro pypy:3-2.4.0 \
   /bin/bash -c "pypy3 /vo/$(basename $0) < /vo/input.txt"
exit $?
'''
import sys

def _s(): return sys.stdin.readline().strip()

def _i(): return int(sys.stdin.readline().strip())

def parse(s):
    l, r = 0, 0
    for c in s:
        if c == '(':
            r += 1
        else:
            if r>0:
                r-=1
            else:
                l+=1
    return (r,l)


def main():
    n = _i()
    p = list(filter(lambda x: x !=(0,0), [parse(_s()) for _ in range(n)]))
    p.sort(key= lambda x: (x[1],-x[0]))

    r = 0
    for pi in p:
        rr, ll = pi
        if ll > r:
            return 'No'
        r += (rr - ll)

    return 'Yes' if r == 0 else 'No'

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

Submission status: Wrong Answer

Solution code:
n = int(input())
bracket = []
only_left = 0
only_right = 0
for i in range(n):
    left = []
    right = []
    tmp = list(input())
    for j in range(len(tmp)):
        if tmp[j] == '(':
            left.append(j)
        else:
            right.append(j)
    for l in range(len(left)-1, -1, -1):
        for r in range(len(right)-1, -1, -1):
            if left[l] < right[r]:
                left.pop(l)
                right.pop(r)
                break
    if len(left) > 0 and len(right) == 0:
        only_left += len(left)
    elif len(left) == 0 and len(right) > 0:
        only_right += len(right)
    elif len(left) > 0 and len(right) > 0:
        bracket.append([left, right])

if only_left > only_right:
    only_left -= only_right
    only_right = 0
else:
    only_right -= only_left
    only_left = 0

can_make = True
for left, right in bracket:
    if len(left) > only_left or len(right) > only_right:
        can_make = False
        break
    only_left -= len(left)
    only_right -= len(right)

if can_make and only_left == 0 and only_right == 0:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
import heapq
n = int(input())
sss = [input()[:-1] for _ in range(n)]

a = []
b = []
ss = 0
ii = 0
for i in sss:
    mi = 0
    ma = 0
    s = 0
    for j in i:
        if j == "(":
            s += 1
        else:
            s -= 1
        mi = min(mi, s)
        ma = max(ma, s)
    ss += s
    if s >= 0:
        a.append([-s, mi, ma, ii])
    else:
        a.append([s, mi - s, ma - s, ii])
    ii += 1


if ss != 0:
    print("No")
    exit()
a.sort(reverse=1, key=lambda x: x[1])
b.sort(reverse=1, key=lambda x: x[1])


def ok1(a):
    s = 0
    heap = []
    i = 0
    while True:
        while i < len(a) and a[i][1] + s >= 0:
            heapq.heappush(heap, a[i])
            i += 1
        if i < len(a) and not heap:
            print("No")
            exit()
        if not heap:
            break
        kkk = 0
        for j in sss[heapq.heappop(heap)[-1]]:
            kkk += 1
            if j == "(":
                s += 1
            else:
                s -= 1
            if s < 0:
                print("No")
                exit()


def ok(a):
    s = 0
    heap = []
    i = 0
    while True:
        while i < len(a) and a[i][1] + s >= 0:
            heapq.heappush(heap, a[i])
            i += 1
        if i < len(a) and not heap:
            print("No")
            exit()
        if not heap:
            break
        kkk = 0
        for j in reversed(sss[heapq.heappop(heap)[-1]]):
            kkk += 1
            if j == ")":
                s += 1
            else:
                s -= 1
            if s < 0:
                print("No")
                exit()


ok1(a)
ok(b)
print("Yes")

Submission status: Wrong Answer

Solution code:
import bisect
import sys
from collections import defaultdict


class Node:
    def __init__(self, value, index):
        self.value = value
        self.index = index

    def __str__(self):
        return 'val : ' + str(self.value) + ' index : ' + str(self.index)

# 0-indexed SegmentTree


class SegmentTree:
    def __init__(self, N, default_list, default_value=-10**10):
        self.N0 = pow(2, (N - 1).bit_length())
        self.nodes = [Node(default_value, i + 1 - self.N0) for i in range(2 * self.N0 - 1)]
        for i in reversed(range(2 * self.N0 - 1)):
            ind = i + 1 - self.N0
            if ind >= N:
                self.nodes[i].value = default_value
            elif N > ind >= 0:
                self.nodes[i].value = default_list[ind]
            else:
                self.nodes[i] = self.process(self.nodes[i * 2 + 1], self.nodes[i * 2 + 2])

    def __str__(self):
        return '[' + ', '.join(map(str, [self.nodes[i + self.N0 - 1].value for i in range(self.N0)])) + ']'

    def query(self, L, R):  # [L,R)の値
        retnode = Node(-10**10, -10**10)
        L += self.N0
        R += self.N0
        while L < R:
            if R & 1:
                R -= 1
                retnode = self.process(retnode, self.nodes[R - 1])
            if L & 1:
                retnode = self.process(retnode, self.nodes[L - 1])
                L += 1
            L >>= 1
            R >>= 1
        return retnode

    def process(self, node_x, node_y):  # x,yが子の時，親に返る値
        if node_x.value > node_y.value:
            return node_x
        else:
            return node_y

    def update(self, i, x):
        i += self.N0 - 1
        self.nodes[i] = Node(x, i + 1 - self.N0)
        while i:
            i = (i - 1) // 2
            self.nodes[i] = self.process(self.nodes[i * 2 + 1], self.nodes[i * 2 + 2])


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)
    cnts.append((down, up, s))

cnts.sort()
# print(cnts)

ups = []
downs = []
rights = defaultdict(int)
for i, (d, u, s) in enumerate(cnts):
    downs.append(d)
    ups.append(u)

ST = SegmentTree(N, ups)

tmp = 0
for _ in range(N):
    R = bisect.bisect_right(downs, tmp)
    # print(tmp, R)
    node = ST.query(0, R)
    ST.update(node.index, -10 ** 10)

    tmp += node.value

    # print(tmp, node)

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


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

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    S = [input() for _ in range(N)]
    L = []
    for i in range(N):
        t = 0
        mint = 1
        for s in S[i]:
            if s == "(":
                t += 1
            else:
                t -= 1
            mint = min(mint, t)
        L.append((t, mint))
    L.sort(key=lambda x: x[0], reverse=True)
    L.sort(key=lambda x: x[1], reverse=True)
    t = 0
    for l, m in L:
        if t + m < 0:
            return False
        t += l
        if t < 0:
            return False
    if t == 0:
        return True
    return False


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