Problem:


Score : 600 points

Problem Statement

A bracket sequence is a string that is one of the following:

An empty string;

The concatenation of (, A, and ) in this order, for some bracket sequence A ;

The concatenation of A and B in this order, for some non-empty bracket sequences A and B /

Given are N strings S_i. Can a bracket sequence be formed by concatenating all the N strings in some order?

Constraints

1 \leq N \leq 10^6

The total length of the strings S_i is at most 10^6.

S_i is a non-empty string consisting of ( and ).

Input

Input is given from Standard Input in the following format:

N
S_1
:
S_N

Output

If a bracket sequence can be formed by concatenating all the N strings in some order, print Yes; otherwise, print No.

Sample Input 1

2
)
(()

Sample Output 1

Yes

Concatenating (() and ) in this order forms a bracket sequence.

Sample Input 2

2
)(
()

Sample Output 2

No

Sample Input 3

4
((()))
((((((
))))))
()()()

Sample Output 3

Yes

Sample Input 4

3
(((
)
)

Sample Output 4

No



Sample input:
2
)
(()


Sample output:
Yes

Submission status: Wrong Answer

Solution code:
import math
import fractions
#import sys
#input = sys.stdin.readline

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

def ValueToBits(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

def BitsToValue(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        ans+= arr[i] * 2**i
    return ans

def ZipArray(a):
    aa = [[a[i],i]for i in range(n)]

    aa.sort(key = lambda x : x[0])
    for i in range(n):
        aa[i][0]=i+1
    aa.sort(key = lambda x : x[1])
    b=[aa[i][0] for i in range(len(a))]
    return b

def ValueToArray10(x, digit):
    ans = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        ans[digit-i-1] = now%10
        now = now //10
    return ans

def Zeros(a,b):
    if(b<=-1):
        return [0 for i in range(a)]
    else:
        return [[0 for i in range(b)] for i in range(a)]

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
            
'''
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 2
N = 10 ** 6 + 2
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

'''

#a = list(map(int, input().split()))

#################################################
#################################################
#################################################
#################################################



n = int(input())

lr = []

for i in range(n):
    s = input()
    m = len(s)
    #exam left
    count = 0
    left = 0
    for j in range(m):
        if(s[j]=='('):
            count += 1
        else:
            if(count == 0):
                left+=1
            else:
                count -=1
    #exam right
    count = 0
    right = 0
    for j in range(m):
        if(s[m-j-1]==')'):
            count += 1
        else:
            if(count == 0):
                right+=1
            else:
                count -=1

    #print(left,right)
    lr.append([left,right])

existL = 0
existR = 0
sumL = 0
sumR = 0
for i in range(n):
    sumL += lr[i][0]
    sumR += lr[i][1]
    if(lr[i][0]==0 and lr[i][1]!=0):
        existL=1
        #print(lr[i])
    if(lr[i][1]==0 and lr[i][0]!=0):
        existR=1
        #print(lr[i])

lr.sort(key = lambda x : (x[0]-x[1])*(-x[0]-x[1]))
lr.sort(key = lambda x : x[0]-x[1])

ok = 1
now = 0
for i in range(n):
    now -= lr[i][0]
    if(now<0):
        ok = 0
        #print('a',lr[i])
    now += lr[i][1]
    
if(existL*existR == 1 and sumL == sumR and ok==1):
    print("Yes")
else:
    if(sumL==0 and sumR==0):
        print("Yes")
    else:
        print("No")

Submission status: Wrong Answer

Solution code:
import sys
n=int(input())
s=[input() for i in range(n)]
t=[2*(i.count("("))-len(i) for i in s]
if sum(t)!=0:
    print("No")
    sys.exit()
st=list(map(list,zip(s,t)))
for i in range(n):
    u=st[i][0]
    l=len(u)
    now,mi=0,0
    for j in range(l):
        if u[j]=="(":
            now+=1
        else:
            now-=1
        mi=min(mi,now)
    st[i].append(mi)
st.sort(reverse=True,key=lambda z:z[1])
st.sort(reverse=True,key=lambda z:z[2])
now2=0
for i in range(n):
    if now2+st[i][2]<0:
        print("No")
        break
    now2+=st[i][1]
else:
    print("Yes")

Submission status: Wrong Answer

Solution code:
import sys
from operator import itemgetter

def solve():
    input = sys.stdin.readline
    N = int(input())
    Left = []
    Both = 0
    lB = None
    rB = None
    for _ in range(N):
        S = input().strip("\n")
        M = len(S)
        aL, aR = 0, 0
        #自身より左にある"("
        r = 0
        for i in range(M):
            if S[i] == ")":
                if r == 0: aL += 1
                else: r -= 1
            else: r += 1
        aR = r
        if aL == aR == 0: Both += 1
        elif aR == 0: 
            if rB == None: rB = (aL, aR)
            elif aL > rB[0]:
                Left.append((rB[0], rB[1]))
                rB = (aL, aR)
            else: Left.append((aL, aR))
        elif aL == 0: 
            if lB == None: lB = (aL, aR)
            elif aR > lB[1]:
                Left.append((lB[0], lB[1]))
                lB = (aL, aR)
            else: Left.append((aL, aR))       
        else: Left.append((aL, aR))
    Left.sort(key = itemgetter(1), reverse = True)
    Left.sort(key = itemgetter(0))
    
    #print(Left)
    rightOver = 0
    if lB != None: rightOver += lB[1]
    for i in range(len(Left)):
        rightOver -= Left[i][0]
        if rightOver < 0:
            print("No")
            break
        rightOver += Left[i][1]
    else:
        if rB != None:
            rightOver -= rB[0]
            if rightOver != 0: print("No")
            else: print("Yes")
        else: 
            if rightOver == 0: print("Yes")
            else: print("No")

    return  0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
#!python3

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

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


def main():
    w = [None] * N
    for i in range(N):
        l = 0
        b = 0
        for s in S[i]:
            if s == "(":
                l += 1
            else:
                l -= 1
                b = min(b, l)
        w[i] = (-b, l)
    w.sort()

    x = 0
    for b, l in w:
        if x - b < 0:
            print("No")
            return
        x += l
    if x == 0:
        print("Yes")
    else:
        print("No")


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
N = int(input())
brackets = []
def change(S):
    left = 0
    right = 0
    cnt = 0
    SUM = 0
    for i in S:
        if i == '(':
            left += 1
            SUM += 1
        else:
            if left > 0:
                left -= 1
                cnt += 1
            right += 1
            SUM += 1
            
    return (right - cnt, -1 * (SUM - right - cnt))

for _ in range(N):
    brackets.append(change(input()))

B = []
cnt = 0
for b in brackets:
    if b[0] == 0:
        cnt -= b[1]
    else:
        B.append(-b[1]-b[0])
B.sort(reverse = True)


for b in B:
    cnt += b
    if cnt < 0:
        print('No')
        sys.exit()

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

Submission status: Wrong Answer

Solution code:
INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))
def do():
    n=INT()
    cost=[0]*n
    flg1=[1]*n
    ancost=[0]*n
    ansflg=1
    for i in range(n):
        flg2=1
        temp=0
        at=0
        s=STR()
        for k in s:
            if k=='(':
                temp+=1
                at+=1
            elif k==')':
                temp-=1
            if temp<0:
                flg2=0
        cost[i]=temp
        if flg2==0 and temp>=0:
            flg1[i]=0
            ancost[i]=at
        
        
    
    if sum(cost)!=0:
        ansflg=0
    
    an=sum(ancost)
    co=0
    for i in range(n):
        if cost[i]<=0:
            co-=cost[i]
    
    if co<an:
        ansflg=0
    
    
    if ansflg==1:
        print('Yes')
    else:
        print('No')
        
if __name__ == '__main__':
    do()

Submission status: Wrong Answer

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))

from collections import defaultdict, deque
from sys import exit
import math
import copy
from bisect import bisect_left

import sys
# sys.setrecursionlimit(1000000)
INF = 10 ** 17
MOD = 998244353

def main():
    n = getN()
    al, ar = 0, 0
    kakkos = []
    for i in range(n):
        s = input().strip()
        q = deque()
        l, r = 0, 0
        for c in s:
            if c == "(":
                r += 1
            else:
                if r == 0:
                    l += 1
                else:
                    r -= 1
        kakkos.append([l, r])
    kakkos = list(sorted(kakkos))
    if kakkos[0][0] != 0:
        print("No")
        return
    # print(kakkos)
    tr = kakkos[0][1]
    for cl, cr in kakkos[1:]:
        if cl > tr:
            print("No")
            return
        tr = (tr - cl) + cr

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

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def calc(s):
    r = 0
    for c in s:
        if c == '(':
            r += 1
        else:
            r -= 1
    return r

def check(S):
    score = sorted([calc(s) for s in S])
    if sum(score) != 0:
        return False
    return True

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

if check(S):
    print('Yes')
else:
    print('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 depth > 0 and min_depth < 0:
        p2.append((min_depth,depth))
    else:
        p3.append((min_depth,depth))
pp2 = sorted(p2,reverse=True)
pp3 = sorted(p3,reverse=True)
# 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:
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


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


def main():
    N = int(input())
    left = 0
    right = 0
    left_ = 0
    right_ = 0
    for _ in range(N):
        S = input()
        stack = 0
        n_pop = 0
        for s in S:
            if s == "(":
                stack += 1
            elif stack > 0:
                stack -= 1
                n_pop += 1

        l = stack
        r = len(S) - 2 * n_pop - stack

        if l == 0:
            right += len(S) - 2 * n_pop
        elif r == 0:
            left += l
        else:
            if left_ == 0 and right_ == 0:
                left_ = l
                right_ = r
            elif left_ - r >= 0:
                left_ -= r
                left_ += l
            elif r - left_ >= 0:
                r -= left_
                left_ = l
                right_ += r
            elif right_ - l >= 0:
                right_ -= l
                right_ += r
            elif l - right_ >= 0:
                l -= right_
                right_ = r
                left_ += l

    left -= right_
    right -= left_
    if left >= 0 and right >= 0 and left == right:
        print("Yes")
    else:
        print("No")


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n,*s=open(0)
n=int(n)
f=g=h=a=b=m=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==y==0:h+=1
    if x==0:f=1
    elif y==0:g=1
    else:m+=1
    a+=x
    b+=y
if (h>1 or f and g) and a==b and m < n / 3 * 2:
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

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

nums=[0]*N
soko=[0]*N
for i in range(N):
  s=S[i]
  x=len(s)
  c=0
  for j in range(x):
    if s[j]=='(':
      c+=1
    else:
      c-=1
    if c<soko[i]:
      soko[i]=c
  
  nums[i]=c
  
res=[[nums[i], soko[i]] for i in range(N)]
res=sorted(res, key=itemgetter(1), reverse=True)

if sum(nums)!=0:
  print('No')
  exit()
  
h=0
i=0
while i<N and res[i][0]>=0:
  if h+res[i][1]<0:
    print('No')
    exit()
  h+=res[i][0]
  if h<0:
    print('No')
    exit()
  i+=1
  
if i==N:
  print('Yes')
else:
  res=res[i:]
  res=res[::-1]
  N=len(res)
  for i in range(N):
    if h+res[i][1]<0:
      print('No')
      exit()
    h+=res[i][0]
    if h<0:
      print('No')
      exit()
    i+=1
  print('Yes')

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==count0:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
N = int(input())
a = 0
aa = 0
b = 0
c = 0
for i in range (N):
    S = input()
    a += S.count('(')
    aa += len(S)-a
    if S[0] == ')':
        b += 1
    elif S[-1] == '(':
        c += 1


if a == aa and b == c:
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

Solution code:
import sys


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


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

    return MIN, tmp


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

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

tmp = 0
for f, d, u, _ in cnts:
    if f == -1:
        d *= -1

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

    tmp += u

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


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

Submission status: Wrong Answer

Solution code:
N = int(input())
sum = 0
Max = 0
M = 0
for i in range(N):
    S = input()
    m = 0
    n = 0
    t = 0
    for s in S:
        if s == "(":
            t += 1
        else:
            t -= 1
        if m >= t:
            m = t
        if n <= t:
            n = t
    if m == 0:
        M += t
    else:
        M0 = min(M,sum+m)
        if t >= 0:
            M = min(Max+m,M0+t)
    sum += t
    if Max <= sum:
        Max = sum
if sum != 0 or M < 0:
    print("No")
else:
    print("Yes")

Submission status: Wrong Answer

Solution code:
import heapq

n = int(input())

demand_dic = {}

open_list = set()

for i in range(n):
    s = input()
    need_open = 0
    need_close = 0
    for j in range(len(s)):
        if s[j] == ")":
            if need_close > 0:
                need_close -= 1
            else:
                need_open += 1
        if s[j] == "(":
            need_close += 1

    if demand_dic.get(need_open, None) is None:
        demand_dic[need_open] = []
    heapq.heappush(demand_dic[need_open], -need_close)
    open_list.add(need_open)

yn_answer = "No"

end = False

can_close = 0
for k in open_list:
    needs = demand_dic[k]
    for i in range(len(needs)):
        if k > can_close:
            end = True
            break
        else:
            can_close -=  k + heapq.heappop(needs)
    if end:
        break

if not end and can_close == 0:
    yn_answer = "Yes"

print(yn_answer)

Submission status: Wrong Answer

Solution code:
from __future__ import division, print_function
import sys
if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip

import os, sys, bisect, copy
from collections import defaultdict, Counter, deque
#from functools import lru_cache   #use @lru_cache(None)
if os.path.exists('in.txt'): sys.stdin=open('in.txt','r')
if os.path.exists('out.txt'): sys.stdout=open('out.txt', 'w')
#
def input(): return sys.stdin.readline()
def mapi(arg=0): return map(int if arg==0 else str,input().split())
#------------------------------------------------------------------

n = int(input())
a = []
mp = defaultdict(int)
for i in range(n):
    s = input().strip()
    bal = 0
    neg = 0
    for j in s:
        if bal<0 and j=="(":
            neg+=bal
        if j=="(":
            bal+=1
        else:bal-=1
    pos = 0
    s = s[::-1]
    bal=0
    for j in s:
        if bal<0 and j==")":
            pos+=bal
        if j==")":
            bal+=1
        else:bal-=1
    mp[(pos,bal,neg)]+=1
    #mp[neg]+=1
    #mp[bal]+=1
    #mp[pos]+=1
f = 1
#print(mp)
for i,j,k in mp.keys():
    if mp[(-i,-j,-k)]!=mp[(i,j,k)]:
        f = 0
        break
if f:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

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

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

L, R, tl, tr = 0, 0, False, False
bigl, tmpl, tmpr, bigr = 0, 0, 0, 0
for i in S:
    a = brancket(i)
    print(a)
    if a != [0, 0]:
        if a[0] == 0:
            tl = True
        if a[1] == 0:
            tr = True
    L += a[0]
    R += a[1]
    if bigl < a[0]:
        bigl = a[0]
        tmpr = a[1]
    if bigr < a[1]:
        bigr = a[1]
        tmpl = a[0]

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

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
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)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    a = [input() for i in range(n)]
    s = []
    for i in range(n):
        p = 0
        m = 0
        for j in a[i]:
            if j == "(":
                p += 1
            else:
                p -= 1
            if p < m:
                m = p
        s.append((m,p))
    s.sort(reverse = True)
    k = 0
    for m,p in s:
        if k+m < 0:
            print("No")
            return
        k += p
    if k > 0:
        print("No")
    else:
        print("Yes")
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
n = int(input())
left_left = []
left_right = []
right_left = []
right_right = []
left = 0
right = 0

for i in range(n):
    S = input()
    l = len(S)
    left += S.count('(')
    right+= S.count(')')
    if S[0] == '(':
        if S[l - 1] == '(':
            left_left.append(S.count('(') - S.count(')'))
        else:
            left_right.append(S.count('(') - S.count(')'))
    else:
        if S[l - 1] == '(':
            right_left.append(S.count('(') - S.count(')'))
        else:
            right_right.append(S.count('(') - S.count(')'))
if left != right:
    print('No')
else:
    sum_ll = sum(left_left)
    sum_lr = sum(left_right)
    sum_rl = sum(right_left)
    sum_rr = sum(right_right)
    if sum_ll + sum_lr == -(sum_rl + sum_rr):
        if len(left_left) == 0 and len(right_right) == 0:
            print('No')
        else:
            if len(left_left) == 0 and len(left_right) == 0:
                print('No')
            else:
                if len(right_left) == 0 and len(right_right) == 0:
                    print('No')
                else:
                    print('Yes')
    else:
        print('No')

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    Ss = [input() for _ in range(n)]
    U = [[0, 0] for _ in range(n)]
    for i in range(n):
        for c in Ss[i]:
            if c == "(":
                U[i][1] += 1
            else:
                if U[i][1] == 0:
                    U[i][0] += 1
                else:
                    U[i][1] -= 1
    R, L = 0, 0
    P = 0
    cnt_P = 0
    for i in range(n):
        if U[i][0] == 0 and U[i][1] > 0:
            R += U[i][1]
        elif U[i][1] == 0 and U[i][0] > 0:
            L += U[i][0]
        elif U[i][0] > 0 and U[i][1] > 0:
            P += U[i][1] - U[i][0]
            cnt_P += 1
    if R == 0 and L == 0:
        if cnt_P > 0:
            print("No")
        else:
            print("Yes")
    else:
        if R + P == L:
            print("Yes")
        else:
            print("No")


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

n = int(input())
s = [input().rstrip() for _ in range(n)]
s_cnt = []
l = 0
r = 0
for i in range(n):
    s_ = list(s[i])
    left = 0
    right = 0
    for j in s_:
        if j == ")":
            if left >= 1:
                left -= 1
            else:
                right += 1
        else:
            left += 1
    if left != 0 and right != 0:
        s_cnt.append([left, right])
    elif left != 0 and right == 0:
        l += left
    elif right != 0 and left == 0:
        r += right
if s_cnt:
    left, right = s_cnt[0]
    for i in range(1, len(s_cnt)):
        if i >= len(s_cnt):
            break
        l_, r_ = s_cnt[i]
        if right >= l_:
            right -= l_
            l_ = 0
        else:
            right = 0
            l_ -= right
        left += l_
        right += r_
    if left == r and right == l:
        print("Yes")
    else:
        print("No")
else:
    if l == r:
        print("Yes")
    else:
        print("No")

Submission status: Wrong Answer

Solution code:
import sys
N = int(input())
brackets = []
def change(S):
    left = 0
    right = 0
    cnt = 0
    SUM = 0
    for i in S:
        if i == '(':
            left += 1
            SUM += 1
        else:
            if left > 0:
                left -= 1
                cnt += 1
            right += 1
            SUM += 1
            
    return (right - cnt, -1 * (SUM - right - cnt))

for _ in range(N):
    brackets.append(change(input()))

B = []
cnt = 0
for b in brackets:
    if b[0] == 0:
        cnt -= b[1]
    else:
        B.append(-b[1]-b[0])
B.sort(reverse = True)

for b in B:
    cnt -= b
    if cnt < 0:
        print('No')
        sys.exit()

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

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
l=[]
ln=[]
for i in range(n):
    s=input().rstrip()
    l.append(s)
    m=0
    temp=0
    for j in s:
        if j=='(':
            temp+=1
        else:
            temp-=1
        m=min(m,temp)
    ln.append((m,temp))
ln.sort(reverse=True)
s=0
for i in ln:
    if s+i[0]>=0:
        s+=i[1]
    else:
        print('No')
        sys.exit()
if s==0:
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

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

T = [0]*N
M = [0]*N
for i in range(N):
    res = 0
    idx = 0
    s = S[i]
    l = len(s)
    m = 0
    while idx<l:
        if s[idx]==')':
            res -= 1
            m = min(res,m)
        else:
            res += 1
        idx += 1
    
    M[i] = -m
    T[i] = res-m

MT = []
for i in range(N):
    MT.append([M[i],T[i]])

MT.sort()

if MT[0][0] != 0:
    print('No')
    exit()

res = 0
for m,t in MT:
    res -= m
    if res<0:
        print('No')
        exit()
    res += t
if res!=0:
    print('No')
else:
    print('Yes')

Submission status: Wrong Answer

Solution code:
def count(s):
    ret = 0
    max_down = 0
    for c in s:
        if c=="(": ret += 1
        else: ret -= 1
        max_down = min(max_down,ret)
    return max_down, ret

n = int(input())
s_count_plus = []
s_count_minus = []
for i in range(n):
    si = input()
    down, num = count(si)
    if num >= 0:
        s_count_plus.append((down, num))
    else:
        s_count_minus.append((-down,num))

s_count_plus.sort(reverse=True)
s_count_minus.sort(reverse=True)

ans = "No"
count_sum = 0

flag = 1

for down, num in s_count_plus:
    if count_sum + down < 0:
        flag = 0
        break
    count_sum += num

for down, num in s_count_minus:
    if count_sum < down:
        flag = 0
        break
    count_sum += num

if flag and count_sum == 0: ans = "Yes"

print(ans)

Submission status: Wrong Answer

Solution code:
import sqlite3

conn = sqlite3.connect(":memory:")
conn.executescript(
    "CREATE TABLE tab (max_d INTEGER, tot_d INTEGER); CREATE INDEX ind ON tab(max_d DESC, tot_d DESC);",
)

N = int(input())
Ss = []
for _ in range(N):
    S = input()
    max_d = 0
    tot_d = 0
    tot_o = 0
    tot_c = 0
    for c in S:
        if c == "(":
            tot_o += 1
        else:
            tot_c += 1
            max_d = max(max_d, tot_c - tot_o)
    Ss.append((max_d, tot_o - tot_c))
conn.executemany("INSERT INTO tab VALUES (?, ?)", Ss)
d = 0
for _ in range(N):
    row = conn.execute(
        "SELECT rowid, tot_d FROM tab WHERE max_d <= ? ORDER BY tot_d DESC LIMIT 1",
        (d,),
    ).fetchone()
    if row is None:
        d = -1
        break
    d += row[1]
    conn.execute("DELETE FROM tab WHERE rowid = ?", (row[0],))
if d == 0:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
N = int(input())
S_info1 = []
S_info2 = []

tot = 0

for _ in range(N):
    s = input()
    score = 0
    maxv = 0
    minv = 0
    for c in s:
        if c == "(":
            score += 1
        else:
            score -= 1
        maxv = max(maxv, score)
        minv = min(minv, score)
    tot += score
    if score > 0:
        S_info1.append([s, score, maxv, minv])
    else:
        S_info2.append([s, score, maxv, minv])

if tot != 0:
    print("No")
else:
    S_info1.sort(key = lambda x:(-x[3], -x[1]))
    #print(S_info1)
    tot = 0
    flag = True
    for i in range(len(S_info1)):
        s, score, maxv, minv = S_info1[i]
        if tot < -minv:
            flag = False
            break
        tot += score
    if not flag:
        print("No")
    else:
        S_info = S_info1 + S_info2
        flag = True
        tot = 0
        Maxv = 0
        Minv = 0
        Maxscore = 0
        for i in range(N):
            s, score, maxv, minv = S_info[i]
            tot += score
            Maxv = max(Maxv, maxv)
            Minv = min(Minv, minv)
            if score > 0:
                Maxscore += score
        if Maxscore >= -Minv:
            print("Yes")
        else:
            print("No")

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    S = [input() for _ in [0]*n]
    s2 = []
    s3 = []
    for s in S:
        temp = [0, 0]
        m = 0
        now = 0
        for i in s:
            if i == "(":
                now += 1
            else:
                now -= 1
            m = min(m, now)
        temp[0] = m
        temp[1] = (s.count("(")-s.count(")"))
        if temp[1] >= 0:
            s2.append(temp)
        else:
            s3.append(temp)
    s2.sort(key=lambda x: x[0])
    s3.sort(key=lambda x: -x[1])
    cnt = 0
    for i, j in s2:
        if cnt+i < 0:
            print("No")
            return
        cnt += j
    for i, j in s3:
        if cnt+i < 0:
            print("No")
            return
        cnt += j
    if cnt != 0:
        print("No")
        return
    print("Yes")


main()

Submission status: Wrong Answer

Solution code:
from scipy.sparse import csr_matrix, csgraph
N = int(input())
lefts, rights = [], []
count = 0
indices = {}
ind = 0
for i in range(N):
    left, right = 0, 0
    for c in input():
        if c == "(":
            left += 1
        if c == ")":
            if left:
                left -= 1
            else:
                right += 1
    if any((left, right)):
        count += 1
        try:
            lind = indices[left]
        except:
            indices[left] = ind
            lind = ind
            ind += 1
        try:
            rind = indices[right]
        except:
            indices[right] = ind
            rind = ind
            ind += 1
        lefts.append(lind)
        rights.append(rind)
graph = csr_matrix(([1] * count, (lefts, rights)), shape=(ind, ind))
if (csgraph.connected_components(graph, return_labels=False) == 1):
    parity = [0, 0]
    for i in range(ind):
        parity[graph[i].sum() & 1] += 1
    print("Yes" if (parity[0] in [0, 2] and not parity[1] & 1) else "No")
else:
    print("No")