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:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
s = [input() for _ in range(n)]
x = []
for i in range(n):
    cnt = 0
    for j in range(len(s[i])):
        if s[i][j] == '(':
            cnt += 1
        else:
            cnt -= 1
    x.append((cnt, s[i]))
x.sort(reverse=True)
x = deque(x)
stack = []
while x:
    _, v = x.popleft()
    for i in v:
        if i == '(':
            stack.append(i)
        else:
            if stack:
                stack.pop()
            else:
                print('No')
                quit()
if stack:
    print('No')
else:
    print('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):
    b = []
    for s in S:
        lc = 0
        rc = 0
        for c in s:
            if c == '(':
                lc += 1
            else:
                if lc > 0:
                    lc -= 1
                else:
                    rc += 1
        b.append([lc, rc])
    b.sort(key=lambda x: x[1], reverse=True)
    b.sort()

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

    if b[0][0] == 0 and b[0][1] == 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:
import sys
n = int(input())
si = []
for _ in range(n):
    s = input()
    l = 0
    r = 0
    count = 0
    for i in range(len(s)):
        if s[i] == "(":
            count += 1
        else:
            count = max(0, count-1)
    l = count
    count = 0
    for i in range(len(s)-1, -1, -1):
        if s[i] == ")":
            count += 1
        else:
            count = max(0, count-1)
    r = count
    si.append((l, r))

if len(si) == 1:
    if si[0] == (0, 0):
        print("Yes")
        sys.exit()

index_l = -1
index_r = -1
maxi_l = 0
maxi_r = 0
for i in range(n):
    a, b = si[i]
    if a == 0:
        if maxi_l < b:
            maxi_l = b
            index_l = i
    if b == 0:
        if maxi_r < a:
            maxi_r = a
            index_r = i


count = 0
if index_r < index_l:
    count += si.pop(index_l)[1]
    last = si.pop(index_r)
else:
    last = si.pop(index_r)
    count += si.pop(index_l)[1]

minus = []
plus = []
while si:
    a, b = si.pop()
    if a <= b:
        plus.append((a, b))
    else:
        minus.append((a, b))

plus.sort()
minus.sort(reverse = True)

for a, b in plus:
    if count >= a:
        count += b-a
    else:
        print("No")
        sys.exit()

for a, b in minus:
    if count >= a:
        count += b-a
    else:
        print("No")
        sys.exit()

count -= last[0]

if count == 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)]
llst=[]
lr=[]
rlst=[]
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 and not r:
        llst.append(l)
    elif not l and r:
        rlst.append(r)
    elif l or r:
        lr.append([l,r])
llst=sum(llst)
rlst=sum(rlst)

if not llst and not rlst and not lr:
    print("Yes")
    exit()
if not lr:
    if llst-rlst==0:
        print("Yes")
    else:
        print("No")
    exit()

idleR=10**7

def main(n,xl,xr):
    X=xl+idleR*xr
    if  not dp[n][X]:
        dp[n][X]=1
        stack.append([n,xl,xr])
if lr:
    L,R=lr[0]
    dp=[defaultdict(int) for i in range(len(lr))]
    X=L+idleR*R
    dp[0][X]=1
    stack=[[0,L,R]]
    while stack:
        n,l,r=stack.pop()
        if n+1<len(lr):
            L,R=lr[n+1]

            if r<L:
                main(n+1,L-r+l,R)
            else:
                main(n+1,l,R+r-L)

            if l<R:
                main(n+1,L,r+R-l)
            else:
                main(n+1,L+l-R,r)





        else:
            if l<=rlst:
                L=rlst-l
            else:
                continue
            if r<=llst:
                R=llst-r
            else:
                continue
            if L-R==0:
                print("Yes")
                exit()



print("No")

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):
    b = []
    for s in S:
        lc = 0
        rc = 0
        for c in s:
            if c == '(':
                lc += 1
            else:
                if lc > 0:
                    lc -= 1
                else:
                    rc += 1
        b.append([lc, rc])
    b.sort(key=lambda x: x[1])
    b.sort()

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

    if b[0][0] == 0 and b[0][1] == 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:
if __name__ == '__main__':
    l = []
    n = int(input())
    s = []
    for i in range(n):
        s.append(input())
    for string in s:
        top = -1
        sb = []
        for c in string:
            if len(sb) == 0:
                sb.append(c)
                top+=1
            else:
                if c == '(':
                    sb.append(c)
                    top+=1
                else:
                    if sb[top] == '(':
                        sb.pop()
                        top-=1
                    else:
                        sb.append(c)
        start = 0
        end = 0
        i = 0
        while i<len(sb) and sb[i] == ')':
            start+=1
            i+=1
        while i<len(sb) and sb[i] == '(':
            end+=1
            i+=1
        if start == 0 and end == 0:
            pass
        else:
            l.append((start,end))
    
    sz = False
    ez = False
    sums = 0
    sume = 0
    mini = 1000000
    ele = -1
    count = 0
    for t in l:
        if t[0] == 0:
            sz = True
        if t[1] == 0:
            ez = True

        sums += t[0]
        sume += t[1]
        if t[0] == 0:
            ele = t[1]
            count+=1
        else:
            mini = min(mini,t[0])
    if not sz:
        print("No")
        exit()
    if not ez:
        print("No")
        exit()
    if count == 1:
        if ele < mini:
            print("No")
            exit()
    if sums == sume:
        print("Yes")
    else:
        print("No")

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])
lr2 = []
for i in range(n):
    if(lr[i][0]==0): lr2.append(lr[i])
lr3 = []
for i in range(n):
    if(lr[i][0]*lr[i][1]!=0): lr3.append(lr[i])
lr3.sort(key = lambda x : x[0]-x[1])
for i in lr3:
    lr2.append(i)
for i in range(n):
    if(lr[i][1]==0): lr2.append(lr[i])
#print(lr2)

ok = 1
now = 0
for i in range(n):
    now -= lr2[i][0]
    if(now<0):
        ok = 0
        print('a',lr2[i])
    now += lr2[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:
input = raw_input

n = int(input())

def f(s):
    l = 0
    n = len(s)
    si = None
    for i in range(n):
        if s[i] == ")":
            l -= 1
        else:
            si = i
            break
    r = 0
    if si is None:
        pass
    else:
        for i in range(si, n):
            if s[i] == "(":
                r += 1
            else:
                r -= 1
    return l, r


ind = 0
pairs = []
ls = []
rs = []

sum_ls = [0, 0]
sum_rs = [0, 0]

sum_l_2 = 0
sum_r_2 = 0

nokori_l = 0
nokori_r = 0

def g1(l, r):
    ii = 0
    sum_l = sum_ls[ii]
    sum_r = sum_rs[ii]

    sum_l1 = sum_l
    sum_r1 = r
    mid1 = sum_r + l
    if mid1 < 0:
        sum_l1 += mid1
    else:
        sum_r1 += mid1

    sum_l2 = l
    sum_r2 = sum_r
    mid2 = r + sum_l
    if mid2 < 0:
        sum_l2 += mid2
    else:
        sum_r2 += mid2

    if sum_r2 <= sum_r1:
        sum_l = sum_l2
        sum_r = sum_r2
    else:
        sum_l = sum_l1
        sum_r = sum_r1
    sum_ls[ii] = sum_l
    sum_rs[ii] = sum_r

def g2(l, r):
    ii = 1
    sum_l = sum_ls[ii]
    sum_r = sum_rs[ii]

    sum_l1 = sum_l
    sum_r1 = r
    mid1 = sum_r + l
    if mid1 < 0:
        sum_l1 += mid1
    else:
        sum_r1 += mid1

    sum_l2 = l
    sum_r2 = sum_r
    mid2 = r + sum_l
    if mid2 < 0:
        sum_l2 += mid2
    else:
        sum_r2 += mid2

    if sum_r2 <= sum_r1:
    #if sum_r2 < sum_r1:
        sum_l = sum_l2
        sum_r = sum_r2
    else:
        sum_l = sum_l1
        sum_r = sum_r1
    sum_ls[ii] = sum_l
    sum_rs[ii] = sum_r


for i in range(n):
    s = input()
    l, r = f(s)
    if l == 0 and r == 0:
        continue
    elif l != 0 and r != 0:
        g1(l, r)
        #g2(l, r)
    else:
        if l != 0:
            nokori_l += l
        else:
            nokori_r += r

flag = False
#for i in range(2):
for i in range(1):
    sum_l = sum_ls[i]
    sum_r = sum_ls[i]
    right_side = sum_r + nokori_l
    left_side = nokori_r + sum_l

    if left_side >= 0 and right_side <= 0:
        if left_side + right_side == 0:
            flag = True

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

Submission status: Wrong Answer

Solution code:
if __name__ == '__main__':
    l = []
    n = int(input())
    s = []
    for i in range(n):
        s.append(input())
    for string in s:
        top = -1
        sb = []
        for c in string:
            if len(sb) == 0:
                sb.append(c)
                top+=1
            else:
                if c == '(':
                    sb.append(c)
                    top+=1
                else:
                    if sb[top] == '(':
                        sb.pop()
                        top-=1
                    else:
                        sb.append(c)
        start = 0
        end = 0
        i = 0
        while i<len(sb) and sb[i] == ')':
            start+=1
            i+=1
        while i<len(sb) and sb[i] == '(':
            end+=1
            i+=1
        if start == 0 and end == 0:
            pass
        else:
            l.append((start,end))
    
    sz = False
    ez = False
    sums = 0
    sume = 0
    maxi = -1
    ele = -1
    count = 0
    for t in l:
        if t[0] == 0:
            sz = True
        if t[1] == 0:
            ez = True

        sums += t[0]
        sume += t[1]
        if t[0] == 0:
            ele = t[1]
            count+=1
        else:
            maxi = max(maxi,t[0])
    if not sz:
        print("No")
        exit()
    if not ez:
        print("No")
        exit()
    if count == 1:
        if ele > maxi:
            print("No")
            exit()
    if sums == sume:
        print("Yes")
    else:
        print("No")

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():
    pl, ml = [], []
    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)
        if l > 0:
            pl.append((-b, l))
        else:
            ml.append((-l, b))
    pl.sort()
    ml.sort()

    x = 0
    for b, l in pl:
        if x - b < 0:
            print("No")
            return
        x += l
    for l, b in ml:
        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
from collections import deque
def input():
    return sys.stdin.readline().strip()

def check():
    s = input()
    m = 0
    res = 0
    for i in s:
        if i == "(":
            m += 1 
        else:
            m -= 1
            res = min(res,m)
    return [res,m]

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

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

a = 0
b = 0

for res,m in S:
    a = b + res
    b += m
    if a < 0:
        print("No")
        exit()

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

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import combinations, product
#import bisect# lower_bound etc
#import numpy as np
def run():
    N = int(input())
    dic = {'(':- 1, ')': 1}
    dic2 = {'(': 0, ')': 1}
    ret = 0
    cri = [0,0,0]
    for _ in range(N):
        S = input()
        arr = []
        for s in S:
            ret += dic[s]
            arr.append(dic2[s])
            try:
                if arr[-1] == 1 and arr[-2] == 0:
                    arr.pop()
                    arr.pop()
            except:
                continue

        if arr == []: continue
        if len(arr) == 1:
            cri[arr[0]] += 1
        else:
            if arr[0] == 0 and arr[-1] == 0:
                cri[0] += 1
            elif arr[0] == 1 and arr[-1] == 1:
                cri[1] += 1
            else:
                cri[2] += 1

    if ret == 0 and (cri[2] == 0 or (cri[1] > 0 or cri[0] > 0)):
        print('Yes')
    else:
        print('No')
if __name__ == "__main__":
    run()

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():
    pl, ml = [], []
    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)
        if l > 0:
            pl.append((-b, l))
        else:
            ml.append((-l, b))
    pl.sort
    ml.sort

    x = 0
    for b, l in pl:
        if x - b < 0:
            print("No")
            return
        x += l
    for l, b in ml:
        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:
input = raw_input

n = int(input())

def f(s):
    l = 0
    n = len(s)
    si = None
    for i in range(n):
        if s[i] == ")":
            l -= 1
        else:
            si = i
            break
    r = 0
    if si is None:
        pass
    else:
        for i in range(si, n):
            if s[i] == "(":
                r += 1
            else:
                r -= 1
    return l, r


ind = 0
pairs = []
ls = []
rs = []

sum_ls = [0, 0]
sum_rs = [0, 0]

sum_l_2 = 0
sum_r_2 = 0

nokori_l = 0
nokori_r = 0

def g1(l, r):
    ii = 0
    sum_l = sum_ls[ii]
    sum_r = sum_rs[ii]

    sum_l1 = sum_l
    sum_r1 = r
    mid1 = sum_r + l
    if mid1 < 0:
        sum_l1 += mid1
    else:
        sum_r1 += mid1

    sum_l2 = l
    sum_r2 = sum_r
    mid2 = r + sum_l
    if mid2 < 0:
        sum_l2 += mid2
    else:
        sum_r2 += mid2

    if sum_r2 <= sum_r1:
        sum_l = sum_l2
        sum_r = sum_r2
    else:
        sum_l = sum_l1
        sum_r = sum_r1
    sum_ls[ii] = sum_l
    sum_rs[ii] = sum_r

def g2(l, r):
    ii = 1
    sum_l = sum_ls[ii]
    sum_r = sum_rs[ii]

    sum_l1 = sum_l
    sum_r1 = r
    mid1 = sum_r + l
    if mid1 < 0:
        sum_l1 += mid1
    else:
        sum_r1 += mid1

    sum_l2 = l
    sum_r2 = sum_r
    mid2 = r + sum_l
    if mid2 < 0:
        sum_l2 += mid2
    else:
        sum_r2 += mid2

    if sum_r2 <= sum_r1:
    #if sum_r2 < sum_r1:
        sum_l = sum_l2
        sum_r = sum_r2
    else:
        sum_l = sum_l1
        sum_r = sum_r1
    sum_ls[ii] = sum_l
    sum_rs[ii] = sum_r


for i in range(n):
    s = input()
    l, r = f(s)
    if l == 0 and r == 0:
        continue
    elif l != 0 and r != 0:
        g1(l, r)
        #g2(l, r)
    else:
        if l != 0:
            nokori_l += l
        else:
            nokori_r += r

flag = False
for i in range(2):
    sum_l = sum_ls[i]
    sum_r = sum_ls[i]
    right_side = sum_r + nokori_l
    left_side = nokori_r + sum_l

    if left_side >= 0 and right_side <= 0:
        if left_side + right_side == 0:
            flag = True

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

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
def input():
    return sys.stdin.readline().strip()

def check():
    s = input()
    m = 0
    res = 0
    for i in s:
        if i == "(":
            m += 1 
        else:
            m -= 1
            res = min(res,m)
    return [res,m]

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

S.sort(reverse=True)
print(S)

a = 0
b = 0

for res,m in S:
    a = b + res
    b += m
    if a < 0:
        print("No")
        exit()

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

Submission status: Wrong Answer

Solution code:
N = int(input())
s = [input() for i in range(N)]
S = [[0]*len(s[i]) for i in range(N)]
for i, x in enumerate(s):
    res = []
    q = 0
    for j in range(len(x)):
        if x[j] == ')':
            S[i][j] = -1
        else:
            S[i][j] = 1
s = [0]*N
m = [len(S[i]) for i in range(N)]
for i, x in enumerate(S):
    tmp = 0
    for j in range(len(x)):
        tmp += S[i][j]
        m[i] = min(tmp, m[i])
    s[i] = tmp

if sum(s) == 0:
    sp = [(m[i], s[i]) for i in range(N) if s[i] >= 0]
    mp = [(m[i], s[i]) for i in range(N) if s[i] < 0]
    sp.sort(key=lambda x: x[0], reverse=True)
    tmp = 0
    for x, y in sp:
        if tmp + x < 0:
            print("No")
            exit(0)
        tmp += y
    #mp.sort(key=lambda x: x[1])
    for x, y in sp:
        if tmp + x < 0:
            print("No")
            exit(0)
        tmp += y
    print("Yes")

else:
    print("No")

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())
    first, second, third = [], [], []
    for _ 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 min_balance == 0:
            first.append((min_balance, balance))
        elif balance > 0:
            second.append((min_balance, balance))
        else:
            third.append((min_balance, balance))

    now = 0
    # first は何も考えず足せば良い
    for min_balance, balance in first:
        now += balance

    # second は min_balance の大きい方から足せば良い
    second.sort(reverse = 1)
    for min_balance, balance in second:
        if now + min_balance < 0:
            print("No")
            return
        now += balance

    # third は balance の大きい方から足せば良い
    third.sort(key = lambda tup:tup[1], reverse = 1)
    for min_balance, balance in third:
        if now + min_balance < 0:
            print("No")
            return
        now += balance

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

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
class SegmentTree:
    def __init__(self, size, f=max, default=(-float("inf"),0)):
        self.size = 2**(size-1).bit_length()
        self.default = default
        self.dat = [default]*(self.size*2)
        self.f = f

    def update(self, i, x):
        i += self.size
        self.dat[i] = x
        while i > 0:
            i >>= 1
            self.dat[i] = self.f(self.dat[i*2], self.dat[i*2+1])

    def get(self, a, b=None):
        if b is None:
            b = a + 1
        l, r = a + self.size, b + self.size
        lres, rres = self.default, self.default
        while l < r:
            if l & 1:
                lres = self.f(lres, self.dat[l])
                l += 1

            if r & 1:
                r -= 1
                rres = self.f(self.dat[r], rres)
            l >>= 1
            r >>= 1
        res = self.f(lres, rres)
        return res
def solve():
    n = I()
    a = [input() for i in range(n)]
    N = 10**6
    s = [[] for i in range(N+1)]
    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
        heappush(s[-m],-p)
    S = SegmentTree(N+1)
    for m in range(N+1):
        if s[m]:
            p = heappop(s[m])
            S.update(m,(-p,m))
    k = 0
    for _ in range(n):
        p,m = S.get(0,k+1)
        k += p
        if k < 0:
            print("No")
            return
        if s[m]:
            p = heappop(s[m])
            S.update(m,(-p,m))
        else:
            S.update(m,(-float("inf"),m))
    if k != 0:
        print("No")
    else:
        print("Yes")
    return

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

Submission status: Wrong Answer

Solution code:
def check(s):
    pos = 0
    min_path = 0
    for chr in s:
        if chr == '(':
            pos += 1
        else:
            pos -= 1
            if min_path > pos:
                min_path = pos

    return min_path, pos  # p = 左側に ) が残っている, q = 右側に ( が残っている


n = int(input())
up_list = []
down_list = []
to_zero_down = 0


for _ in range(n):
    s = input()
    min_path, to = check(s)
    if to == 0:
        if to_zero_down > min_path:
            to_zero_down = min_path

    elif to > 0:
        up = to
        up_list.append((min_path, up))

    else:
        down = -to
        down_list.append((min_path, down))


up_list.sort(reverse=True)
down_list.sort(reverse=True)

count = 0
for min_path, up in up_list:
    if count + min_path < 0:
        print('No')
        exit()
    count += up

if count + to_zero_down < 0:
    print('No')
    exit()

for min_path, down in down_list:
    if count + min_path < 0:
        print('No')
        exit()
    count -= down

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

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
s = [input() for _ in range(n)]
f = deque()
b = deque()
for i in range(n):
    if s[i][0] == '(':
        f.append(s[i])
    else:
        b.append(s[i])
stack = []
while f:
    t = f.popleft()
    for i in t:
        if i == '(':
            stack.append('(')
        else:
            if stack:
                stack.pop()
            else:
                print('No')
                quit()
while b:
    t = b.popleft()
    for i in t:
        if i == '(':
            stack.append('(')
        else:
            if stack:
                stack.pop()
            else:
                print('No')
                quit()
if stack:
    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())
    plus = []
    minus = []
    for _ in range(N):
        S = input()
        stack = 0
        m = 0
        for s in S:
            if s == "(":
                stack += 1
            else:
                stack -= 1
            m = min(stack, m)

        if stack > 0:
            plus.append((m, stack))
        else:
            minus.append((m, stack))

    plus.sort(key=lambda x: x[0], reverse=True)
    minus.sort(key=lambda x: x[0], reverse=True)
    m = 0
    cur = 0
    for i, j in plus:
        m += i
        cur += j
        if m < 0:
            print("No")
            return

        m = cur

    for i, j in minus:
        m += i
        cur += j
        if m < 0:
            print("No")
            return

        m = cur

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


if __name__ == "__main__":
    main()