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:
# -*- coding: utf-8 -*-
import sys
# sys.setrecursionlimit(10**6)
buff_readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, S):
    l = []
    r = []
    b = [[0, 0]]
    for s in S:
        stack = []
        for c in s:
            if c == '(':
                stack.append('(')
            else:
                if stack and stack[-1] == '(':
                    stack.pop()
                else:
                    stack.append(')')
        lc = stack.count('(')
        rc = stack.count(')')
        if lc != 0 and rc != 0:
            b.append([lc, rc])
        elif lc != 0:
            l.append(lc)
        elif rc != 0:
            r.append(rc)

    if sum(l) != sum(r):
        return 'No'

    sl = sum(l)
    sr = sum(r)
    b.append([sl, 0])
    b.append([0, sr])
    b.sort(key=lambda x: x[1]-x[0])

    while len(b) > 1:
        x = b.pop()
        y = b.pop()
        if x[1] < y[0]:
            z = [x[0] + y[0]-x[1], y[1]]
        else:
            z = [x[0], x[1]-y[0] + y[1]]
        b.append(z)

    if b[0][0] == 0 and b[0][0] == 0:
        return 'Yes'

    return 'No'


def main():
    N = read_int()
    S = [read_str() for _ in range(N)]
    print(slv(N, S))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())

S = [input() for i in range(N)]

T = []

for i in range(N):
    count1 = 0
    count2 = 0
    count = 0
    for j in range(len(S[i])):
        if S[i][j]=="(":
            count += 1
        else:
            count -= 1
        count1 = max(count1,-count)
    count = 0
    for j in range(len(S[i])):
        if S[i][len(S[i])-j-1]=="(":
            count += 1
        else:
            count -= 1
        count2 = max(count2,count)

    T.append((count1,count2))
flag1 = False
flag2 = False
count0 = 0
for i in range(N):
    if T[i][0]==0 and T[i][1]==0:
        count0 += 1
    elif T[i][0]==0 and T[i][1]!=0:
        flag1 = True
    elif T[i][0]!=0 and T[i][1]==0:
        flag2 = True

if (flag1 and flag2):
    count1=0
    count2=0
    for i in range(N):
        count1 += T[i][0]
        count2 += T[i][1]
    if count1==count2:
        print("Yes")
    else:
        print("No")
elif N==1 and count0==1:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
n=int(input())
l,r=0,0
ll=[]
for i in range(n):
    s=input()
    x,y=0,0
    for j in s:
        if j=="(":
            x+=1
        else:
            if x==0:
                y+=1
            else:
                x-=1
    if x==0 or y==0:
        l+=x
        r+=y
    else:
        ll.append((x-y,x,y))
ll.append((l,l,0))
ll.append((-r,0,r))
ll.sort(reverse=True)

x,y=0,0
for i,p,q in ll:
    if q-x>0:
        print("No")
        exit()
    else:
        x-=q
    x+=p

if x==y==0:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

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

LP = 0
RP = 0
minLS = float('inf')
minRS = float('inf')
LS = 0
RS = 0
for i in range(N):
    L = LR[i][0]
    R = LR[i][1]
    if (L==0)and(R==0):
        continue
    elif L==0:
        RP += R
    elif R==0:
        LP += L
    else:
        LS += L
        RS += R
        if LS < minLS:
            minLS = LS
        if RS < minRS:
            minRS = RS

if (LP==RP)and(LS==0)and(RS==0):
    print("Yes")

else:
    if minLS<minRS:
        LS = minLS
        RS = minLS+abs(LS-RS)
    elif minLS>minRS:
        LS = minRS+abs(LS-RS)
        RS = minRS
    else:
        LS = minLS
        RS = minRS
    if (LS<=RP)and(RS<=LP):
        print("Yes")
    else:
        print("No")

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
S = [input() for _ in range(N)]

lis = [None]*N
for i, s in enumerate(S):
	tmp = 0
	stack = []
	for x in s:
		if x == "(":
			stack.append("(")
		else:
			if stack and stack[-1] == "(":
				stack.pop()
			else:
				stack.append(")")

	l = 0
	r = 0
	for s in "".join(stack):
		if s == "(":
			r += 1
		else:
			l += 1

	lis[i] = (r, l)

l = 0
r = 0
for i in range(N):
	m1 = min(lis[i][0], l)
	m2 = min(lis[i][1], r)
	if m1 >= m2:
		r = r+lis[i][0]-m1
		l = l+lis[i][1]-m1
	else:
		r = r+lis[i][0]-m2
		l = l+lis[i][1]-m2
print("Yes" if l == r == 0 else "No")

Submission status: Wrong Answer

Solution code:
N = int(input())
string = ""
for i in range(N):
  s = input()
  string += s
a = string.count('(')
b = string.count(')')
if a == b and string[0] != ')' and string[-1] != '(':
  print("Yes")
else:
  print("No")

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

def l_in():
    return list(map(int, input().split()))

n=n_in()

base=[]

for _ in range(n):
    s = s_in()

    c = s[0]
    cnt = 1
    ar = []
    for t in range(1,len(s)):
        if s[t-1] == s[t]:
            cnt += 1
        else:
            ar.append((c,cnt))
            c = s[t]
            cnt = 1
    ar.append((c,cnt))

    start = 0
    if ar[0][0] == ")":
        start = 1

    r = 0 # ( の数
    sgn = 1
    for c,cnt in ar[start:]:
        r += sgn*cnt
        sgn *= -1


    res = ()
    if ar[0][0] == ")":
        if r >= 0:
            res = (ar[0][1], r)
        else:
            res = (ar[0][1]-r,0)
    else:
        if r >= 0:
            res = (0, r)
        else:
            res = (r, 0)

    base.append(res)

i_cnt = 0
j_cnt = 0

base2 = []

for i,j in base:
    i_cnt += i
    j_cnt += j

    if j > 0:
        base2.append((i,-(j-i),j))

if i_cnt != j_cnt:
    print("No")
    exit()

base2.sort()

current = 0


for i,p,j in filter(lambda x: x[1] <= 0 ,base2):
    if current < i:
        print("No")
        exit()
    current -= i
    current += j

base3 = []
for i,p,j in filter(lambda x: x[1] > 0 ,base2):
    base3.append((p,i,j))

base3.sort()
for p,i,j in base3:    
    if current < i:
        print("No")
        exit()
    current -= i
    current += j
    
print("Yes")

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()
    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:
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


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

    ans = 0

    A = [[0, 0] for j in range(N)]

    for i, s in enumerate(S):
        x = 0
        y = 0
        for ss in s:
            if ss == ')':
                if y == 0:
                    x -= 1
                else:
                    y -= 1
            else:
                y += 1

        A[i][0] = x
        A[i][1] = y

    cntr = 0
    cntl = 0
    mr = 0
    ml = 0
    fr = False
    fl = False
    for aa in A:
        if aa[0] == 0:
            if aa[1] != 0:
                fr = True
            cntr += aa[1]
        elif aa[1] == 0:
            if aa[0] != 0:
                fl = True
            cntl += aa[0]
        else:
            mr += aa[1]
            ml += aa[0]

    if fr and fl:
        if mr + cntr + cntl + ml != 0:
            print("No")
        else:
            print("Yes")
    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((r-l, l))
plus.sort()
minus.sort(reverse=True)
for l, k in plus:
    if nr < l:
        print("No")
        exit()
    nr += k
for k, l in minus:
    if nr < l:
        print("No")
        exit()
    nr += k
if nr != 0:
    print("No")
else:
    print("Yes")

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.readline
n = int(input())

sl = []

left = 0
right = 0
lrl = []
for _ in range(n):
    s = list(input())
    for ss in s:
        if ss == "(":
            left += 1
        elif ss == ")":
            right += 1
    lrl.append(s)
if left != right:
    print("No")
    exit()


values = []
cost = 0
import heapq
heapq.heapify(values)
values = []
for lr in lrl:
    value = [0, 0]
    for i in lr:
        if i == "(":
            value[1] += 1
        elif i == ")":
            value[1] -= 1
        value[0] = min(value[0], value[1])
    value[1] = -value[1]
    values.append(value)
ansl = []
heapq.heapify(ansl)

ans = 0
while True:
    while values:
        c, s = heapq.heappop(values)
        if c <= cost:
            heapq.heappush(ansl, [-s, c])
        else:
            heapq.heappush(values, [c, s])
            break
    if not ansl:
        print("No")
        exit()
    s, c = heapq.heappop(ansl)
    if c > cost:
        print("No")
        exit()
    cost -= s
    if cost < 0:
        print("No")
        exit()
    ans += 1
    if ans == n:
        print("Yes")
        exit()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from operator import mul


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 998244353


n = I()
m = SR(n)
A = []
L = 0
R = 0
for b in m:
    l = 0
    r = 0
    m = deque()
    flg = 0
    for a in b:
        if m and m[-1] == '(' and a == ')':
            m.pop()
            r -= 1
        elif a == '(':
            m += ['(']
            r += 1
        else:
            l += 1
    A += [(l, r)]
    L += l
    R += r


if L != R:
    print('No')
else:
    A.sort()
    ret = 0
    for c, d in A:
        if c > ret:
            print('No')
            break
        ret -= c
        ret += d
    else:
        print('Yes')

Submission status: Wrong Answer

Solution code:
N = int(input())
braket =[]
left_flag = 0
right_flag = 0
tot_flag = 0
sum_braket = 0
for i in range(N):
    S = input()
    left = 0
    right = 0
    for j in range(len(S)):
        if S[j]==")":
            left += 1
        else:
            left_end = j
            break
    for j in range(len(S)-1,-1,-1):
        if S[j]=="(":
            right += 1
        else:
            right_end = j
            break
    left_tot=0
    right_tot=0
    for j in range(len(S)):
        if S[j]==")":
            left_tot += 1
        else:
            right_tot += 1
    left_bt = left_tot - left
    right_bt = right_tot - right
    if left_bt > right_bt:
        left += (left_bt-right_bt)
    elif left_bt < right_bt:
        right += (right_bt-left_bt)
    braket.append([left,right])
    if left==0:
        left_flag=1
    if right==0:
        right_flag=1
    if left==0 or right==0:
        tot_flag += 1
    sum_braket += right - left
    
if N>=2 and tot_flag >= 2 and sum_braket==0:
    print("Yes")
elif N==1 and tot_flag == 1 and sum_braket==0:
    print("Yes")
else:
    print("No")
#print(braket)

Submission status: Wrong Answer

Solution code:
import sys
N=int(input())
L=[0]*N
R=[0]*N
for i in range(N):
  S=input()
  for j in range(len(S)):
    if S[j]=='(':
      L[i]+=1
    elif S[j]==')' and L[i]==0:
      R[i]+=1
    else:
      L[i]-=1
if sum(L)!=sum(R):
  print('No')
  sys.exit()
r,l=0,0
LR=[]
for i in range(N):
  if L[i]==0 and R[i]!=0:
    r+=R[i]
  elif L[i]!=0 and R[i]==0:
    l+=L[i]
  elif L[i]!=0 and R[i]!=0:
    LR.append([R[i]-L[i],L[i],R[i]])
LR.sort()
LL,RR=0,0
for i in range(len(LR)):
  if LL<LR[i][2]:
    RR+=(LR[i][2]-LL)
    LL=0
  elif LL>=LR[i][2]:
    LL-=LR[i][2]
  LL+=LR[i][1]
if l==RR and r==LL:
  print('Yes')
elif (LL==0 or RR==0) and LL+l==RR+r:
  print('Yes')
else:
  print('No')

Submission status: Wrong Answer

Solution code:
def main():
    n=int(input())
    l1=[0]*n
    l2=[0]*n
    for i in range(n):
        S=input()
        c=0
        m=0
        for s in S:
            if s=="(":
                c+=1
            else:
                c-=1
            if c<m:
                m=c
        l1[i]=c
        l2[i]=m
    if sum(l1)!=0:
        print("No")
        exit()
    l_p=[]
    l_m=[]
    for i in range(n):
        if l1[i]>=0:
            l_p.append([l2[i],l1[i]])
        else:
            l_m.append([l2[i],l1[i]])
    l_p.sort(reverse=True)
    l_m.sort(reverse=True)
    l=l_p+l_m
    x=0
    ans="Yes"
    for i in range(n):
        if x+l[i][0]<0:
            ans="No"
            break
        else:
            x+=l[i][1]
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:

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




n = int(input())
minsum = [None] * n # (min, sum)
for i in range(n):
    tmp = list(map(int, " ".join(input()).replace("(", "1").replace(")", "-1").split()))
    c = 0
    m = 0
    for item in tmp:
        c += item
        m = min(c, m)
    minsum[i] = (m, sum(tmp))
minsum.sort()
if sum(item[1] for item in minsum)!=0:
    print("No")
else:
    c = 0
    i = n-1
    while minsum:
        m, s = minsum[i]
        if m<0:
            break
        c += s
        i -= 1
        minsum.pop()
    if not minsum:
        print("Yes")
    else:
        minsum.sort(key=lambda x: x[1])
    #     print(minsum, c)
        i = len(minsum)-1
        while minsum:
            m, s = minsum[i]
            if c+m>=0:
                minsum.pop(i)
                c += s
                i = len(minsum) - 1
            else:
                i -= 1
                if i<0:
                    print("No")
                    break
        else:
            print("Yes")

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
input = lambda:sys.stdin.readline().rstrip()
def resolve():
    n = int(input())
    positive = []
    negative = []
    for i in range(n):
        balance = min_balance = 0
        for c in input():
            if c == '(':
                balance += 1
            else:
                balance -= 1
            min_balance = min(min_balance, balance)
        if balance <= 0:
            negative.append((-min_balance, balance))
        else:
            positive.append((min_balance, balance))

    now = 0
    while positive:
        min_balance, balance = positive.pop()
        if now + min_balance < 0:
            print("No")
            return
        now += balance

    while negative:
        min_balance, balance = negative.pop()
        if now - min_balance < 0:
            print("No")
            return
        now += balance


    print("Yes" if now == 0 else "No")
resolve()

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

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

for s in S:
    less = -calc(s)
    if less <= 0:
        H.append(s)
    else:
        l = s.count('(')
        r = s.count(')')
        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) + ''.join(P) + ''.join(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:
import sys

sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(input())

left = 0
right = 0

has_z_left = False
has_z_right = False
has_sep = False

for _ in range(N):
    S = list(input())
    L = len(S)

    r = 0
    l = 0
    for i in range(L):
        s = S[i]

        if s == ")":
            if l == 0:
                r += 1
            else:
                l -= 1
        elif s == "(":
            l += 1

    R = r

    r = 0
    l = 0
    for i in range(L - 1, -1, -1):
        s = S[i]

        if s == "(":
            if r == 0:
                l += 1
            else:
                r -= 1
        elif s == ")":
            r += 1

    L = l

    if L == 0 and R > 0:
        has_z_left = True

    if R == 0 and L > 0:
        has_z_right = True

    if not (L == R and L == 0):
        has_sep = True

    left += L
    right += R


if left == right:
    if not has_sep:
        print("Yes")
    else:
        if has_z_left and has_z_right:
            print("Yes")
        else:
            print("No")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
main_string = ""
for i in range(int(input())):
    s = input()
    if s[0] == "(":
        main_string = s + main_string
    else:
        main_string = main_string + s
check = 1
if main_string[0] == "(" and main_string[-1] == ")":
    check = 0
    for i in main_string:
        if i == "(":
            check += 1
        else:
            check -= 1
if check == 0:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
n = int(input())
cost = [0 for _ in range(n)]
score = [0 for _ in range(n)]
for i in range(n):
    s = input()
    tmp_cost = 0
    tmp_score = 0
    cost_counter = 0
    for j in range(len(s)):
        if s[j] == '(':
            tmp_score += 1
            if cost_counter > tmp_cost:
                tmp_cost = cost_counter
                cost_counter = 0
            cost_counter -= 1
        if s[j] == ')':
            tmp_score -= 1
            cost_counter += 1
    cost[i] = tmp_cost
    score[i] = tmp_score

if sum(score) != 0:
    print('No')
else:
    judge_score = 0
    for i in range(n):
        judge_score += max(score[i], 0)
    if judge_score < max(cost):
        print('No')
    else:
        print('Yes')

Submission status: Wrong Answer

Solution code:
import sys
n = int(input())
s = [input() for _ in range(n)]
cnts = []
mins = []
plus = []
minus = []
sm = 0
for i in range(n):
    cnt = 0
    mn = 0
    mx = 0
    for c in s[i]:
        if c == '(':
            cnt+=1
        else: cnt-=1
        mn = min(cnt, mn)
        mx = max(cnt, mx)
    cnts.append(abs(cnt))
    if cnt>0 or (cnt == 0 and abs(mn)<abs(mx)):
        plus.append(i)
        mins.append(abs(mn))
    else:
        minus.append(i)
        mins.append(abs(mx))
    sm+=cnt
if(sm != 0):
    print('No')
    sys.exit()

plus.sort(key = lambda x:mins[x])
minus.sort(key = lambda x:mins[x])

now = 0
que = []
r = 0
for i in range(len(plus)):
    while r<len(plus) and mins[plus[r]]<=now:
        que.append(plus[r])
        r+=1
    if(len(que)==0):
        print('No')
        sys.exit()
    j = que.pop()
    now+=cnts[j]

plus = minus
now = 0
que = []
r = 0
for i in range(len(plus)):
    while r<len(plus) and mins[plus[r]]<=now:
        que.append(plus[r])
        r+=1
    if(len(que)==0):
        print('No')
        sys.exit()
    j = que.pop()
    now+=cnts[j]
print('Yes')

Submission status: Wrong Answer

Solution code:
from collections import deque

n = int(input())
s = [input() for i in range(n)]
ruiseki = [[None] * (len(s[i]) + 1) for i in range(n)]

for i in range(n):
    ruiseki[i][0] = 0
    for j, char in enumerate(s[i]):
        if char == "(":
            ruiseki[i][j + 1] = ruiseki[i][j] + 1
        else:
            ruiseki[i][j + 1] = ruiseki[i][j] - 1

min_ = [0] * n
sum_ = [0] * n

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

info = [(sum_[i], 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:
n = int(input())
start = 0
end = 0
left = 0
double = []
right = 0
for i in range(n):
    s = str(input())
    kienaileft = 0
    kienairight = 0
    for j in range(len(s)):
        if s[j] == ")":
            kienaileft += 1
        else:
            break
    for j in range(len(s)):
        if s[-(j+1)] == "(":
            kienairight += 1
        else:
            break
    nowleft = 0
    nowright = 0
    for j in range(kienaileft,len(s)-kienairight):
        if s[j] == ")":
            nowleft += 1
        else:
            nowright += 1
    num = min(nowleft,nowright)
    kienaileft += nowleft -num
    kienairight += nowright -num
    if kienaileft != 0:
        if kienairight != 0:
            double.append([kienaileft,kienairight])
        else:
            left += kienaileft
    else:
        if kienairight != 0:
            right += kienairight
  # print(left,double,right)
if left + sum([double[i][0] for i in range(len(double))]) != sum([double[i][1] for i in range(len(double))]) + right:
    print("No")
    exit()
if len(double) != 0:
    if not left or not right:
        print("No")
        exit()
else:
    if left == right:
        print("Yes")
        exit()
double.sort(key=lambda x:x[0]-x[1])
double.sort()
now = left
for a,b in double:
    if now < a:
        print("No")
        exit()
    now += (b-a)
print("Yes")

Submission status: Wrong Answer

Solution code:
N = int(input())
S = [input() for _ in range(N)]
D = "".join(S)
new_list = {}
List = []
for i in set(D):
   new_list[str(i)] = D.count(i)
for key,val in new_list.items():
    List.append(val)
if List[0] >= N and List[1] >= N:
    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)
cnt=-1
for i in range(n):
    if lst[-1-i][1]==0:
        lastn=n-1-i
        break
if lastn==-1:
    print("No")
    quit()

tmp=0
for i in range(n):
    if i==lastn:
        continue
    tmp-=lst[i][0]
    if tmp<0:
        print("No")
        break
    tmp+=lst[i][1]
else:
    tmp-=lst[lastn][0]
    if tmp<0:
        print("No")
    
    if tmp==0:
        print("Yes")
    else:
        print("No")

Submission status: Wrong Answer

Solution code:
from itertools import combinations

import numpy as np


def run():
    n = int(input())
    s_list = [input() for _ in range(n)]
    s_list = np.array([encode(s) for s in s_list])

    s = np.sum(s_list, axis=0)

    s_list_is_0 = s_list == 0

    left_found = (s_list_is_0 == np.array([True, False]))[:, 0]
    right_found = (s_list_is_0 == np.array([False, True]))[:, 0]

    # left_found = (s_list_is_0 == np.array([True, False])).all(axis=1)
    # right_found = (s_list_is_0 == np.array([False, True])).all(axis=1)

    if s[0] == s[1] == 0:
        print('Yes')
    elif s[0] == s[1] and left_found.any() and right_found.any():
        print('Yes')
    else:
        print('No')


def encode(s: str):
    temp_s = s
    while True:
        next_s = temp_s.replace('()', '')
        if temp_s == next_s:
            break
        temp_s = next_s

    return temp_s.count(')'), temp_s.count('(')


if __name__ == '__main__':
    run()

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[1])

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

    # neg2.sort(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:
import sys

input = sys.stdin.readline
n = int(input())

sl = []

left = 0
right = 0
lrl = []
for _ in range(n):
    s = list(input())
    for ss in s:
        if ss == "(":
            left += 1
        else:
            right += 1
    lrl.append(s)
if left != right:
    print("No")
    exit()


values = []
cost = 0
import heapq
heapq.heapify(values)
values = []
for lr in lrl:
    value = [0, 0]
    for i in lr:
        if i == "(":
            value[1] += 1
        else:
            value[1] -= 1
        value[0] = min(value[0], value[1])
    value[1] = -value[1]
    values.append(value)
ansl = []
heapq.heapify(ansl)

ans = 0
while True:
    while values:
        c, s = heapq.heappop(values)
        if c <= cost:
            heapq.heappush(ansl, [-s, c])
        else:
            heapq.heappush(values, [c, s])
            break
    if not ansl:
        print("No")
        exit()
    s, c = heapq.heappop(ansl)
    if c > cost:
        print("No")
        exit()
    cost -= s
    if cost < 0:
        print("No")
        exit()
    ans += 1
    if ans == n:
        print("Yes")
        exit()

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))

#print(B)
    
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[0]*10000000-b[1], b[0], b[1]))
        ib += 1
    #print(h)

    if len(h)==0:
        break

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

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