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)
tmp = deque()
stack = []
flag = False
while x:
    _, v = x.popleft()
    if not flag:
        if v[0] == '(':
            flag = True
            for i in v:
                if i == '(':
                    stack.append(i)
                else:
                    if stack:
                        stack.pop()
                    else:
                        print('No')
                        quit()
            while tmp:
                u = tmp.popleft()
                for i in u:
                    if i == '(':
                        stack.append(i)
                    else:
                        if stack:
                            stack.pop()
                        else:
                            print('No')
                            quit()
        else:
            tmp.append(v)
    else:
        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:
import sys
from collections import deque
def input():
    return sys.stdin.readline().strip()

tozan = []
gezan = []

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

N = int(input())
for _ in range(N):
    check()

tozan.sort(reverse=True)
gezan.sort(reverse=True)

b = 0

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

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

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

Submission status: Wrong Answer

Solution code:
N = int(input())

memo1 = []
memo2 = []
memo3 = []
memo4 = []
for i in range(N):
  S = input()
  sum_n = sum([1 if s=='(' else -1 for s in S])
  if sum_n >= 0:
    sum_n = 0
    min_n = 1
    for s in S:
      if s == ')':
        sum_n -= 1
        min_n = min(min_n, sum_n)
      else:
        sum_n += 1
    if min_n >= 0:
      memo1.append([min_n, sum_n])
    else:
      memo2.append([min_n, sum_n])
  else:
    sum_n = 0
    min_n = 1
    for s in S[::-1]:
      if s == '(':
        sum_n -= 1
        min_n = min(min_n, sum_n)
      else:
        sum_n += 1
    if min_n >= 0:
      memo4.append([min_n, sum_n])
    else:
      memo3.append([min_n, sum_n])

left = 0
for min_n, sum_n in memo1:
  left += sum_n

memo2.sort(reverse=True)
for min_n, sum_n in memo2:
  if left + min_n < 0:
    print('No')
    quit()
  else:
    left += sum_n

right = 0
for min_n, sum_n in memo4:
  right += sum_n

memo3.sort(reverse=True)
for min_n, sum_n in memo3:
  if left + min_n < 0:
    print('No')
    quit()
  else:
    right += sum_n

if left == right:
  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])
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:
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 lr:
    if llst-rlst==0:
        print("Yes")
    else:
        print("No")
    exit()

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


        if L-r>=0:
            main(n+1,L-r+l,R)
        else:
            main(n+1,l,R-(L-r))

        if R-l>=0:
            main(n+1,L,r+R-l)
        else:
            main(n+1,L-(R-l),r)





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



print("No")

Submission status: Wrong Answer

Solution code:
n = int(input())
l = 0
r = 0
cntl = 0
cntr = 0
fl = 0
fr = 0
exl = 0
exr = 0
only_r = 0
only_l = 0
maxl = 0
maxr = 0
exlr = []
for i in range(n):
    s = input()
    templ = 0
    tempr = 0
    temp_exl = 0
    temp_exr = 0
    fl = 0
    fr = 0
    for i in s:
        if i == "(":
            tempr += 1
        elif i == ")":
            tempr -= 1
            if tempr < 0:
                tempr = 0
                templ += 1
                fl = 1
    temp_exl += templ
    if tempr > 0:
        temp_exr += tempr
        fr = 1
    if fl == 1 and fr == 0:
        only_l += temp_exl
    elif fr == 1 and fl == 0:
        only_r += temp_exr
    elif temp_exl + temp_exr > 0:
        exl += temp_exl
        exr += temp_exr
        exlr.append([temp_exl-temp_exr, temp_exl,temp_exr])
    # maxl = max(maxl,temp_exl)
    # maxr = max(maxr,temp_exr)
# print (exr,exl,only_r,only_l)
a = only_r
b = 0
exlr.sort()
exlr.sort(key=lambda x: x[1])

# print(exlr)
for i in range(len(exlr)):
    if exlr[i][1] <= a and exlr[i][0] <= 0:
        a -= exlr[i][0]
        exlr[i] = [0,0,0]
# print(exlr)
for i in exlr:
    a -= i[1]
    if a<0:
        print("No")
        exit()
    a += i[2]
if exl+only_l == exr+only_r and exl-exr == only_r-only_l and only_l > 0 and only_r > 0:
    print("Yes")
elif exr+exl+only_l+only_r == 0:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
import sys
n = int(input())
ss = input()*n
 
cnt_p = []
cnt_m = []
for i in range(n):
    left = 0
    right = 0
    for s in ss[i]:
        if(s == '('):
            left += 1
        elif(s == ')'):
            if(left > 0):
                left -= 1
            else:
                right += 1
    if(left-right > 0):
        cnt_p.append((right,left))
    else:
        cnt_m.append((right,left))
 
 
cnt_p = sorted(cnt_p, key=lambda x: (x[0]))
cnt_m = sorted(cnt_m, key=lambda x: (x[1]*-1))
cnt = cnt_p + cnt_m
num = 0
for right,left in cnt:
    num -= right
    if(num < 0):
        print('No')
        sys.exit()
    num += left
if(num==0):
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

Solution code:
import sys
n=int(input())
lrp=[]
lrm=[]
def g(s):
    i = 0
    l = [0]
    for j in s:
        if j =="(":
            i += 1
        else:
            i -= 1
        l.append(i)
    return min(l),max(l)
for _ in range(n):
    s = input()
    l = s.count("(")
    r = len(s) - l
    mi,ma =g(s)
    if l>r:
        lrp.append((l,r))
    else:
        lrm.append((l,r))
    #lr.append((mi,ma,l,r))
    
lrp.sort(key=lambda x:x[0])
lrm.sort(key=lambda x:-x[1])
lr=lrp+lrm
num = 0
for right,left in lr:
    num -= right
    if(num < 0):
        print('No')
        sys.exit()
    num += left
if(num==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 lr:
    if llst-rlst==0:
        print("Yes")
    else:
        print("No")
    exit()

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


        if L-r>=0:
            main(n+1,L-r+l,R)
        else:
            main(n+1,l,R-(L-r))

        if R-l>=0:
            main(n+1,L,r+R-l)
        else:
            main(n+1,L-(R-l),r)





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



print("No")

Submission status: Wrong Answer

Solution code:
n = int(input())
scop = [] #高低差,min値
scom = []
ssum = 0

for i in range(n):
    s = input()
    sa = 0
    ms = 0
    for i in range(len(s)):
        if s[i] == "(":
            sa += 1
        else:
            sa -= 1
        if ms > sa:
            ms = sa
    if sa > 0:
        scop.append([ms,sa])
    else:
        scom.append([ms,sa])
    ssum += sa

if not ssum == 0:
    print("No")
    exit()

scop.sort(reverse = True)
scom.sort()

now = 0
for i in scop:
    if now + i[0] < 0:
        print("No")
        exit()
    else:
        now += i[1]
for i in scom:
    if now + i[0] < 0:
        print("No")
        exit()
    else:
        now += i[1]

print("Yes")

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 lr:
    if llst-rlst==0:
        print("Yes")
    else:
        print("No")
    exit()

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


        if L-r>=0:
            main(n+1,L-r+l,R)
        else:
            main(n+1,l,R-(L-r))

        if R-l>=0:
            main(n+1,L,r+R-l)
        else:
            main(n+1,L-(R-l),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:
import sys
from itertools import permutations
readline = sys.stdin.readline

n = int(readline())
s = [readline().strip() for i in range(n)]

comb_s = list(permutations(s, n))

def checker(x):
    print(x)
    if not x: return 0

    if x[0] != '(' or x[-1] != ')': return 0

    r = x.count('(')
    l = x.count(')')
    if r != l: return 0

    return 1

def main():
    for i in range(len(comb_s)):
        jud = checker(''.join(comb_s[i]))
        if jud == 1:
            print('Yes')
            return

    print('No')
    return

main()

Submission status: Wrong Answer

Solution code:
import sys
n=int(input())
lrp=[]
lrm=[]
def g(s):
    i = 0
    l = [0]
    for j in s:
        if j =="(":
            i += 1
        else:
            i -= 1
        l.append(i)
    return min(l),max(l)
for _ in range(n):
    s = input()
    l = s.count("(")
    r = len(s) - l
    mi,ma =g(s)
    if l>r:
        lrp.append((l,r))
    else:
        lrm.append((l,r))
    #lr.append((mi,ma,l,r))
    
lrp.sort(key=lambda x:x[0])
lrm.sort(key=lambda x:-x[1])
lr=lrp+lrm
cnt = 0
for l,r in lr:
    cnt -= r
    if cnt >=0:
        cnt += l
    else:
        print("No")
        sys.exit()
if cnt !=0:
    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:
        bottom = 0
        cur = 0
        for c in s:
            if c == '(':
                cur += 1
            else:
                cur -= 1
            bottom = min(bottom, cur)
        b.append((bottom, cur))

    bp = [_ for _ in b if _[1] > 0]
    bn = [_ for _ in b if _[1] <= 0]
    bp.sort(key=lambda x: x[0], reverse=True)
    bn.sort(key=lambda x: x[1], reverse=True)

    cur = 0
    for bt, ct in bp:
        if cur + bt < 0:
            return 'No'
        cur += ct

    for bt, ct in bn:
        if cur + bt < 0:
            return 'No'
        cur += ct

    if cur != 0:
        return 'No'
    return 'Yes'



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

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

plus.sort()
minus.sort(reverse = True, key = lambda x: x[1])
countl = 0
for a, b in plus:
    if countl >= a:
        countl += b-a
    else:
        print("No")
        sys.exit()

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


if countr == countl:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
n = int(input())
l = 0
r = 0
cntl = 0
cntr = 0
fl = 0
fr = 0
exl = 0
exr = 0
only_r = 0
only_l = 0
maxl = 0
maxr = 0
exlr = []
for i in range(n):
    s = input()
    templ = 0
    tempr = 0
    temp_exl = 0
    temp_exr = 0
    fl = 0
    fr = 0
    for i in s:
        if i == "(":
            tempr += 1
        elif i == ")":
            tempr -= 1
            if tempr < 0:
                tempr = 0
                templ += 1
                fl = 1
    temp_exl += templ
    if tempr > 0:
        temp_exr += tempr
        fr = 1
    if fl == 1 and fr == 0:
        only_l += temp_exl
    elif fr == 1 and fl == 0:
        only_r += temp_exr
    elif temp_exl + temp_exr > 0:
        exl += temp_exl
        exr += temp_exr
        exlr.append([temp_exl-temp_exr, temp_exl,temp_exr])
    # maxl = max(maxl,temp_exl)
    # maxr = max(maxr,temp_exr)
# print (exr,exl,only_r,only_l)
a = only_r
b = 0
exlr.sort()
exlr.sort(key=lambda x: x[1])

# print(exlr)
for i in range(len(exlr)):
    if exlr[i][1] <= a:
        a -= exlr[i][0]
        exlr[i] = [0,0,0]
# print(exlr)
for i in exlr:
    a -= i[1]
    if a<0:
        print("No")
        exit()
    a += i[2]
if exl+only_l == exr+only_r and exl-exr == only_r-only_l and only_l > 0 and only_r > 0:
    print("Yes")
elif exr+exl+only_l+only_r == 0:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

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

tozan = []
gezan = []

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

N = int(input())
for _ in range(N):
    check()

tozan.sort(reverse=True)
gezan.sort(reverse=True)

b = 0

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

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

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

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], 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:
def check(s):
    to = 0
    min_path = 0
    for chr in s:
        if chr == '(':
            to += 1
        else:
            to -= 1
            if min_path > to:
                min_path = to
    return min_path, to


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


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

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:
N = int(input())

Lflg = 0
Rflg = 0
ryohoCnt = 0
LOver = 0

for i in range(N):
    S = input()
    lnum = S.count("(") - S.count(")")
    konkaiflg= 0

    if Lflg < 2 or ryohoCnt < 2:
        if S[0] == "(" and lnum >= 0:
            f = 0
            for j in range(len(S)):
                if S[0:j].count("(") - S[0:j].count(")") < 0:
                    f=1
                    break
            if f==0:
               Lflg = Lflg + 1
               konkaiflg= 1

    if Rflg < 2 or ryohoCnt < 2:
        if S[-1] == ")" and lnum <= 0:
            f = 0
            for j in range(len(S)):
                if S[j*(-1)].count("(") - S[j*(-1)].count(")") > 0:
                    f=1
                    break
            if f==0:
               Rflg = Rflg + 1
               if konkaiflg== 1:
                   ryohoCnt = ryohoCnt + 1

    LOver = LOver + lnum

if Lflg>=1 and Rflg>=1 and LOver==0 and not (ryohoCnt==1 and Lflg==1 and Rflg==1):
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
import sys
def main():
    N = int(input())
    S = [sys.stdin.readline().strip() for i in range(N)]
    DR = []
    for s in S:
        d = 0    # ["(" の数]  - [")" の数]
        rmax = 0 # ")" が最も深くなるときの ")" の数
        # rmax <= d
        for lr in s:
            if lr == '(':
                d += 1
            else:
                d -= 1
                rmax = min(d, rmax)

        DR.append((d, rmax))

    # print(DR)
    # 戦略
    # 1. d = 0とする
    # 2. d + rmax >= 0 となるものを選択
    #    選択後、d += di とする

    # rmaxの大きい順に並べ替える
    DR.sort(key=lambda x: (-x[1], x[0]))
    # print(DR)
    D = 0
    ans = 'yes'
    for dr in DR:
        d, r = dr
        if D + r < 0:
            ans = 'No'
            break
        D += d
    
    if D != 0:
        ans = 'No'
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
l = 0
r = 0
cntl = 0
cntr = 0
fl = 0
fr = 0
exl = 0
exr = 0
only_r = 0
only_l = 0
maxl = 0
maxr = 0
exlr = []
for i in range(n):
    s = input()
    templ = 0
    tempr = 0
    temp_exl = 0
    temp_exr = 0
    fl = 0
    fr = 0
    for i in s:
        if i == "(":
            tempr += 1
        elif i == ")":
            tempr -= 1
            if tempr < 0:
                tempr = 0
                templ += 1
                fl = 1
    temp_exl += templ
    if tempr > 0:
        temp_exr += tempr
        fr = 1
    if fl == 1 and fr == 0:
        only_l += temp_exl
    elif fr == 1 and fl == 0:
        only_r += temp_exr
    elif temp_exl + temp_exr > 0:
        exl += temp_exl
        exr += temp_exr
        exlr.append([temp_exl-temp_exr, temp_exl,temp_exr])
    # maxl = max(maxl,temp_exl)
    # maxr = max(maxr,temp_exr)
# print (exr,exl,only_r,only_l)
a = only_r
b = 0
exlr.sort()
exlr.sort(key=lambda x: x[1])

# print(exlr)
for i in range(len(exlr)):
    if exlr[i][1] <= a:
        a -= exlr[i][1]
        exlr[i] = [0,0,0]
# print(exlr)
for i in exlr:
    a -= i[1]
    if a<0:
        print("No")
        exit()
    a += i[2]
if exl+only_l == exr+only_r and exl-exr == only_r-only_l and only_l > 0 and only_r > 0:
    print("Yes")
elif exr+exl+only_l+only_r == 0:
    print("Yes")
else:
    print("No")

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

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, key = lambda x: x[1])
countl = 0
for a, b in plus:
    if countl >= a:
        countl += b-a
    else:
        print("No")
        sys.exit()

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


if countr == countl:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
import sys
n=int(input())
lr=[]
def g(s):
    i = 0
    l = [0]
    for j in s:
        if j =="(":
            i += 1
        else:
            i -= 1
        l.append(i)
    return min(l),max(l)
for _ in range(n):
    s = input()
    l = s.count("(")
    r = len(s) - l
    mi,ma =g(s)
    lr.append((mi,ma,l,r))
lr.sort(key=lambda x: x[2] if l<r else x[3])
cnt = 0
for mi,ma,l,r in lr:
    #print(cnt)
    if cnt+mi>=0:
        cnt += (l-r)
    else:
        print("No")
        sys.exit()
if cnt !=0:
    print("No")
else:
    print("Yes")