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 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
            else:
                if left_ < r:
                    left_, r = r, left_
                left_ -= 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:
import sys
input = sys.stdin.readline


def main():
    N = int(input())

    nl = 0
    nr = 0

    buff_l = 0
    buff_r = 0

    for _ in range(N):
        S = input()
        for s in S:
            if s == '(':
                buff_l += 1
            elif s == ')':
                if buff_l > 0:
                    buff_l -= 1
                else:
                    buff_r += 1

        if buff_l == buff_r == 0:
            continue

            # if buff_l > buff_r:
            #     nl += max(buff_l - nr, 0)
            #     nr = max(nr - buff_l, 0)
            # elif buff_r > buff_l:
            #     nr += max(buff_r - nl, 0)
            #     nl = max(nl - buff_r, 0)
            # else:
        if nr > nl:  # left
            # nr = max(nr - buff_l, 0) + buff_r
            nl += max(buff_l - nr, 0)
            nr = max(nr - buff_l, 0)
        else:
            nr += max(buff_r - nl, 0)
            # nl = max(nl - buff_r, 0) + buff_l
            nl = max(nl - buff_r, 0)

        buff_l = 0
        buff_r = 0

    if nr == nl == 0:
        print('Yes')
    else:
        print('No')


if __name__ == "__main__":
    main()

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)
        M = max(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:
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[1])
    s3.sort(key=lambda x: x[0])
    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:
n=int(input())
m=[]
for i in range(n):
  s=input()
  a,b,t=0,0,0
  # a:左に(がいくつ必要か
  # b:右に)がいくつ必要か
  # t: (のストック
  for j in s:
    if t==0 and j==")":
      a+=1
    elif j=="(":
      t+=1
    elif t>0 and j==")":
      t-=1
  m.append([a,t])
  #[ 左に(がいくつ必要か, 右に)がいくつ必要か ]
m.sort()
r=0 # (のストック
if m[0][0]!=0 or m[-1][-1]!=0:
  print("No")
  exit()
for li in m:
  t+=li[1]-li[0]
  if t<0:
    print("No")
    exit()
if t==0:
  print("Yes")
else:
  print("No")

Submission status: Wrong Answer

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

YES = "Yes"  # type: str
NO = "No"  # type: str


def solve(N: int, S: "List[str]"):

    count = [[] for _ in range(N)]

    for i in range(N):
        r = 0
        l = 0
        for s in S[i]:
            if s == '(':
                l += 1
            else:
                r += 1
        count[i].append(l)
        count[i].append(r)
    
    count_sorted = sorted(enumerate(count),key = lambda x: -(x[1][0]-x[1][1]))

    new_s = []
        
    def isvalid(s):
        stack = []
        mapping = {")": "(", "}": "{", "]": "["}


        for char in s:

            if char in mapping:
                top_element = stack.pop() if stack else '#'
                if mapping[char] != top_element:
                    return False
            else:
                stack.append(char)
        return not stack

    for index,_ in count_sorted:
        new_s.append(S[index])
    
    if isvalid(''.join(new_s)):
        print(YES)
    else:
        print(NO)

    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = [next(tokens) for _ in range(N)]  # type: "List[str]"
    solve(N, S)

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

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

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

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

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

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

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

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
from bisect import bisect_left
import sys
readlines = sys.stdin.buffer.readlines
readline = sys.stdin.buffer.readline


class SegmentTree:
    """
    演算子は要素とセットでモノイドを形成するようなものでなければならない。
    すなわち、結合律が成り立ち単位元が存在する必要がある。

    equalityはsetを高速化するために使う。めんどい場合はNoneにしてもOK
    """
    @classmethod
    def all_identity(cls, operator, equality, identity, size):
        return cls(operator, equality, identity, [identity]*(2 << (size-1).bit_length()))

    @classmethod
    def from_initial_data(cls, operator, equality, identity, data):
        size = 1 << (len(data)-1).bit_length()
        temp = [identity]*(2*size)
        temp[size:size+len(data)] = data
        data = temp

        for i in reversed(range(size)):
            data[i] = operator(data[2*i],data[2*i+1])
        return cls(operator, equality, identity, data)

    # これ使わずファクトリーメソッド使いましょうね
    def __init__(self, operator, equality, identity, data):
        if equality is None:
            equality = lambda a,b: False
        self.op = operator
        self.eq = equality
        self.id = identity
        self.data = data
        self.size = len(data)//2

    def _interval(self, a, b):
        a += self.size
        b += self.size
        ra = self.id
        rb = self.id

        data = self.data
        op = self.op
        while a < b:
            if a & 1:
                ra = op(ra,data[a])
                a += 1
            if b & 1:
                b -= 1
                rb = op(data[b],rb)
            a >>= 1
            b >>= 1
        return op(ra,rb)

    def __getitem__(self, i):
        if isinstance(i, slice):
            return self._interval(
                                    0 if i.start is None else i.start,
                                    self.size if i.stop is None else i.stop)
        elif isinstance(i, int):
            return self.data[i+self.size]

    def __setitem__(self, i, v):
        i += self.size
        data = self.data
        op = self.op
        eq = self.eq
        while i and not eq(data[i],v):
            data[i] = v
            v = op(data[i^1],v) if i & 1 else op(v,data[i^1])
            i >>= 1

    def __iter__(self):
        return self.data[self.size:]

from operator import eq

N = int(readline())

memo = [None]*N

for i,s in enumerate(readlines()):
    s = s.rstrip().decode()
    memo[i] = (min(0,min(accumulate(1 if c =='(' else -1 for c in s))),sum(1 if c =='(' else -1 for c in s))

memo.sort()
def solve():
    min_acc = [v for v,_ in memo]
    delta = [(v,i) for i,(_,v) in enumerate(memo)]
    identity = (-10**7, -1)

    seg = SegmentTree.from_initial_data(max, eq, identity, delta)

    cur = 0
    for cnt in range(N):
        ind = bisect_left(min_acc, -cur)
        d, i = seg[ind:]
        if i < 0:
            return False
        seg[i] = identity
        cur += d
        if cur < 0:
            return False
    return cur == 0

print('Yes' if solve() else 'No')

Submission status: Wrong Answer

Solution code:
N = int(input())
A = 0
B = []
for i in range(N):
  S = input()
  a = 0
  m = 0
  for s in S:
    if s == '(':
      a = a + 1
    else:
      a = a - 1
      if a < m:
        m = a
  if m == 0:
    A += a
  else:
    B.append([m, a])
B.sort()
f = 0
for i in range(len(B)-1, -1, -1):
  if A + B[i][0] >= 0:
    A = A + B[i][1]
  else:
    print("No")
    f = 1
    break
if f == 0:
  print("Yes")

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left

N = int(input())
S = []
for _ in range(N):
    si = input()
    low = 0
    last = 0
    for s in si:
        if s == "(":
            last += 1
        else:
            last -= 1
        low = min(low, last)
    S.append((low, last))

S.sort()

ans = "Yes"
last = 0
while S:
    pos = bisect_left(S, (-last, -10 ** 6))
    if pos >= len(S):
        ans = "No"
        break
    s_low, s_last = S.pop(pos)
    if last + s_low < 0:
        ans = "No"
        break
    last += s_last

if last != 0:
    ans = "No"
print(ans)

Submission status: Wrong Answer

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


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

Submission status: Wrong Answer

Solution code:
n=int(input())
s=[0]*n
for i in range(n):
    ss=list(input())
    s[i]=[1 if sss=="(" else -1 for sss in ss]

import itertools
rui_old = [list(itertools.accumulate(ss)) for ss in s]

while rui_old:
    rui = sorted(rui_old,key=lambda x:x[-1],reverse=True)

    posinomi = [i for i,r in enumerate(rui) if all(rr>=0 for rr in r) ]
    negamo = [i for i in range(len(rui)) if not i in posinomi]
    posi = sum( rui[i][-1] for i in posinomi)
#     print(posinomi,negamo,posi)

    rui=[[rr+posi for rr in rui[i]] for i in negamo]
      
    
    if posi==0 and len(rui)==0:
        print("Yes")
        break
    if posi>0 and len(rui)==0 or rui_old==rui:
        print("No")
        break
    
    rui_old=rui

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-

# import numpy as np
# from itertools import *
# from collections import *

# S = input()
# N = int(input())
# K, N = [int(x) for x in input().split()]

N = int(input())

S = []
score = [(0,0)] * N

for n in range(N):
    S.append(input())
    while "()" in S[n]:
        S[n] = S[n].replace("()", "")

    if len(S[n]) >= 1:
        beg = S[n].count("(")
        end = S[n].count(")")

        if S[n][0] == "(":
            score[n] = (0, beg)
        else:
            score[n] = (-end, beg)
    else:
        score[n] = (0, 0)

cr = 0
for n in range(N):
    if score[n][0] == 0:
        cr += score[n][1]

for n in range(N):
    if score[n][0] != 0:
        cr += score[n][0]
        if cr < 0:
            print("No")
            exit(0)
        cr += score[n][1]

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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
n = int(input())

l = 0
r = 0

for _ in range(n):
  s = input()
  lx = 0
  rdiv = 0 
  for kakko in s:
    if kakko == "(":
      rdiv += 1
    else:
      if rdiv == 0:
        lx += 1
      else:
        rdiv -= 1

  rx = 0
  ldiv = 0
  for kakko in s[::-1]:
    if kakko == ")":
      ldiv += 1
    else:
      if ldiv == 0:
        rx += 1
      else:
        ldiv -= 1
  
  l += lx
  r += rx

if l == r:
  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 minv >= 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 = []
    pos = []
    neg1 = []
    neg2 = []
    tot_v = 0
    for _ in range(N):
        t = input()
        S.append(t)
        v = 0
        min_v = float('inf')
        for c in t:
            if c == '(': v += 1
            else: v -= 1
            min_v = min(min_v, v)
        tot_v += v
        if min_v >=0:
            pos.append([min_v, v])
        else:
            if v > 0:
                neg1.append([v - min_v, min_v, v])
            else:
                neg2.append([min_v, v])

    if tot_v !=  0: return "No"

    u = 0
    for _, v in pos:
        u += v

    neg1.sort(reverse = False, key = lambda x: x[0])

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

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

    return "Yes"


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

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-


def main():
  values = []
  total = 0

  for _ in range(int(input())):
    s = input().strip()
    open_required = len(s)
    close_required = len(s)
    open_close = 0

    for i, c in enumerate(s):
      if c == '(':
        open_required = min(i, open_required)
        open_close += 1
      else:
        close_required = min(len(s) - i - 1, close_required)
        open_close -= 1

    total += open_close
    values.append([open_required, close_required, open_close, 0])

  if total != 0:
    print('No')
    return
  
  if len(values) > 200000:
    print('Yes')
    return

  fvals = values.copy()
  bvals = values

  fvals.sort(key=lambda x: (x[0], -x[2]))
  bvals.sort(key=lambda x: (x[1], x[2]))

  findex = 0
  bindex = 0

  while True:
    while findex < len(fvals) and fvals[findex][3] != 0:
      findex += 1

    while bindex < len(bvals) and bvals[bindex][3] != 0:
      bindex += 1

    if findex >= len(fvals) and bindex >= len(bvals):
      break

    fvals[findex][3] = 1
    bvals[bindex][3] = -1

  values = [v for v in fvals if v[3] == 1] + [v for v in bvals if v[3] == -1][::-1]

  open_close_f = 0
  open_close_b = 0

  for (oreq_f, _, ocval_f, _), (_, creq_b, ocval_b, _) in zip(values, values[::-1]):
    if oreq_f > open_close_f:
      print('No')
      return

    if creq_b > open_close_b:
      print('No')
      return

    open_close_f += ocval_f
    open_close_b -= ocval_b

  print('Yes')


if __name__ == '__main__':
  main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
# sys.setrecursionlimit(10**6)
buff_readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 2**62-1


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


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


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


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


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


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

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


def mt(f):
    import time

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

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

    return wrap


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

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

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

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

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

    return 'No'


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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
lst = []
flg, mr = 0, 10**9
for i in range(N):
    S = input()
    st, r, rall = 0, 0, 0
    for c in S:
        if c == '(':
            st += 1
        else:
            rall += 1
            if st > 0:
                st -= 1
            else:
                r += 1
    pls = len(S)-rall-rall+r
    if pls <= 0 and S[-1] == ')' and flg == 0:
        mr = r
        flg = 1
        continue
    lst.append((r, -pls))
lst.sort()
if lst[0][0] != 0:
    print('No')
    exit()
lcnt = -lst[0][1]
for (r, pls) in lst[1:]:
    lcnt -= r
    if lcnt < 0:
        print('No')
        break
    lcnt -= pls
else:
    if lcnt-mr == 0:
        print('Yes')
    else:
        print('No')

Submission status: Wrong Answer

Solution code:
import itertools

n = int(input())

s = []
for i in range(n):
    s.append(input())

comb_s = list(itertools.combinations(s, len(s)))

def checker(x):
    jud = 1
    ans = ''.join(x)

    if not s:
        return jud

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

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

    return jud

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

    print('No')
    return
main()

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)

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

N = int(input())

left = 0
right = 0

has_z_left = False
has_z_right = False
has_sep = False
ZERO = 0

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

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

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

    R = r

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

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

    L = l

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

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

    if not (L == R and L == 0):
        has_sep = True
    else:
        ZERO += 1

    left += L
    right += R


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

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    D = []
    for i in range(N):
        S = input()
        d = S.count('(') - S.count(')')
        m = 0
        p = 0
        for c in S:
            if c == '(':
                p += 1
            else:
                p -= 1
            m = min(m, p)
        D.append((d, m))
    if sum(map(lambda x: x[0], D)) != 0:
        print('No')
    else:
        D.sort(key=lambda x: x[1], reverse=True)
        p = 0
        ok = True
        for i in range(N):
            if p + D[i][1] < 0:
                ok = False
            p += D[i][0]
        print('Yes' if ok else 'No')


if __name__ == '__main__':
    main()

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()
  print('Yes')

Submission status: Wrong Answer

Solution code:
number=int(input())
x=[]
i=1
while i<=number:
    i+=1
    x.append(input())
y=[]#）
z=[]#（
#y_z=[]#)>(
wholey=0
wholez=0
ally=0
allz=0
for each in x:
    caly=0
    calz=0
    for ch in each:
        if ch=='(':
            caly+=1
        elif ch==')':
            if caly<=0:
                calz+=1
            else:
                caly-=1
    if caly==0 and calz==0:
        continue;
    elif caly==0:
        wholez += calz
    elif calz==0:
        wholey += caly
    else:
        y.append(caly)
        z.append(calz)
    ally += caly
    allz += calz

if  wholez!=0 and wholez!=0 and ally==allz:
    index=0
    y2=[]
    z2=[]
    y3=[]
    z3=[]
    while index<len(y):
        if y[index]>=z[index]:
            y2.append(y[index])
            z2.append(z[index])
        else:
            y3.append(y[index])
            z3.append(z[index])
        index+=1
    possible=False
    if len(z2)!=0:
        while(True):
            index=0
            flag=0
            while index<len(z2):
                if z2[index]<=wholey:
                    wholey+=y2[index]-z2[index]
                    flag=1
                    del z2[index]
                else:
                    index+=1
            if flag==0:
                print('No')
                break
            elif len(z2)==0:
                possible=True
                break
    else:
        possible=True
    if possible and len(y3)!=0:
        while (True):
            index = 0
            flag=0
            while index < len(y3):
                if y3[index] <=wholez:
                    wholez += z3[index] - y3[index]
                    flag=1
                    del y3[index]
                else:
                    index += 1
            if flag==0:
                print('No')
                possible=False
                break
            elif len(y3) == 0:
                break
    if possible:
        print('Yes')
else:
    print('No')

Submission status: Wrong Answer

Solution code:
N = int(input())

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

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

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

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

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

Submission status: Wrong Answer

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n = int(input())
    l = 0
    r = 0

    for i in range(n):
        s = input()
        cl = 0
        cr = 0
        for ch in s:
            if ch == "(":
                cl += 1
            else:
                if cl > 0:
                    cl -= 1
                else:
                    cr += 1
        if l > 0:
            l -= cr
            cr = 0
            if l < 0:
                r -= l
                l = 0
        if r > 0:
            r -= cl
            cl = 0
            if r < 0:
                l -= r
                r = 0
        l += cl
        r += cr

    if l == r == 0:
        print("Yes")
    else:
        print("No")


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
s_s = []
for i in range(n):
  l = 0
  r = 0
  cur = 0
  s = input()
  for j in s:
    if j == '(':
      l += 1    
    else:
      if l >= 1:
        l -= 1
      else:
        r += 1
  s_s.append( (l, r) )

s_s.sort(key=lambda ss: ss[1])
#print(s_s)

failed = False
b = 0
ll = 0
rr = 0
for s in s_s:
  b -= s[1]
  if b < 0:
    failed = True
    break
  b += s[0]

if failed:
  ans = 'No'
else:
  if b == 0:
    ans = 'Yes'
  else:
    ans = 'No'

print(ans)

Submission status: Wrong Answer

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

if ll==[]:
    if l==r:
        print("Yes")
    else:
        print("No")
    exit()
else:
    if l*r==0:
        print("No")
        exit()

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

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

Submission status: Wrong Answer

Solution code:
import sys

N = int(input())
left = 0
right = 0
mid_right = 0
mid_left = 0
mid = 0

for _ in range(N):
	s = input()
	L = len(s)
	while True:
		s = s.replace('()', '')
		tmp = len(s)
		if tmp == L:
			break
		else:
			L = tmp
	
	if s:
		if L == 1:
			if s == '(':
				left += 1
			else:
				right += 1
		elif L > 1:
			if s[0] == s[-1]:
				if s[0] == '(':
					left += L
				else:
					right += L
			else:
				mid = 1
				for i in range(L):
					if s[i] == '(':
						mid_right += i
						mid_left += (L - i)
						break

if mid:
	if (right == 0) and (left == 0):
		print('No')
	else:
		if (mid_left + left) == (mid_right + right):
			print('Yes')
		else:
			print('No')
else:
	if right == left:
		print('Yes')
	else:
		print('No')

Submission status: Wrong Answer

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

def check(s):
    c = 0
    ok = True
    for x in s:
        if x == '(':
            c+=1
        else:
            c-=1
        if c < 0:
            ok = False
    if ok:
        return c==0, c
    return False, c

S = []
for i in range(N):
    ok, c = check(S0[i])
    if not ok:
        S.append(c)

print(S)
if sum(S) != 0:
    print("No")
else:
    print("Yes")