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:
N = int(input())
S = [input() for _ in range(N)]

both_list = []
left_list = []
right_list = []
both_count = 0
left_count = 0
right_count = 0
left_all = 0
right_all = 0

counts = [[0, 0] for _ in range(N)]

for i, Si in enumerate(S):
  left = 0
  right = 0
  for c in Si:
    if c == '(':
      left += 1
    else:
      if left == 0:
        right += 1
      else:
        left -= 1
        
  counts[i][0] = left
  counts[i][1] = right
  left_all += left
  right_all += right
  if left * right > 0:
    both_list.append(i)
    both_count += 1
  elif left > 0:
    left_list.append(i)
    left_count += 1
  elif right > 0:
    right_list.append(i)
    right_count += 1
    
if both_count + left_count + right_count == 0:
  print('Yes')
elif left_count * right_count == 0:
  print('No')
elif both_count == 0:
  if left_all == right_all:
    print('Yes')
  else:
    print('No')
else:
  if left_all != right_all:
    print('No')
  else:
    print('Yes')

Submission status: Wrong Answer

Solution code:
import bisect

n=int(input())
opens=0
closes=0
ls=[]
rs=[]
for _ in range(n):
  s=input()
  cnt1=0
  cnt2=0
  for i in range(len(s)):
    if s[i]=='(':
      cnt1+=1
    else:
      if cnt1==0:
        cnt2+=1
      else:
        cnt1-=1
  if cnt2==0:
    opens+=cnt1
  elif cnt1==0:
    closes+=cnt2
  else:
    ls.append(cnt2)
    rs.append(cnt1)
ls=sorted(ls)
rs=sorted(rs)
lefts=sum(ls)
rights=sum(rs)
if opens-closes!=lefts-rights:
  print('No')
else:
  flag=False
  if len(ls)==0:
    flag=True
  for a in ls:
    if opens<a or closes<a+(rights-lefts):
      continue
    pos=bisect.bisect_right(rs,a+(rights-lefts))
    if pos!=0:
      flag=True
      break
  for d in rs:
    if opens<d or closes<d+(lefts-rights):
      continue
    pos=bisect.bisect_right(ls,d+(lefts-rights))
    if pos!=0:
      flag=True
      break
  if flag==True:
    print('Yes')
  else:
    print('No')

Submission status: Wrong Answer

Solution code:
n = int(input())
left=[]
right=[]
for i in range(n):
    s = input()
    l = len(s)
    a=0
    b=0
    a1=0
    b1=0
    for j in range(l):
        if s[j]==')':
            a1+=1
        else:
            a1-=1
        a=max(a1,a)
    for j in range(l):
        if s[l-1-j]=='(':
            b1+=1
        else:
            b1-=1
        b = max(b1,b)
    if a>b:
        right.append((a,b))
    else:
        left.append((a,b))
right.sort(key = lambda x:x[1])
left.sort(key = lambda x:x[0])
all = left+right

if all[0][0]>0:
    print('No')
    exit()
st = all[0][1]
for i in range(1,n):
    st-=all[i][0]
    if st<0:
        print('No')
        exit()
    st+=all[i][1]
if st>0:
    print('No')
else:
    print('Yes')

Submission status: Wrong Answer

Solution code:
n = int(input())
left=[]
right=[]
cent_l=[]
cent_r=[]
for i in range(n):
    x = [0]*3
    s = input()
    l = len(s)
    dir=1
    st=0
    c=0
    for j in range(l):
        if j==l-1:
            if dir == 1:
                if s[j]=='(':
                    st+=1
                    x[2]=st
                else:
                    st-=1
                    x[2]=st
            else:
                if s[j]==')':
                    st-=1
                    x[2]=st
                else:
                    x[0]+=st
                    x[2]=1
        elif dir==1:
            if s[j]==')':
                dir=0
                st-=1
            else:
                st+=1
        else:
            if s[j]=='(':
                dir = 1
                if c==0:
                    x[0]=st
                    c=1
                else:
                    x[1]+=st
                st=0
            else:
                st-=1
    if x[1]<0:
        x[0]+=x[1]
    else:
        x[2]+=x[1]
    if x[0]==0:
        left.append(x[2])
    elif x[2]==0:
        right.append(x[0])
    else:
        cent_l.append(x[0])
        cent_r.append(x[2])

if sum(left)>=sum(cent_l) and sum(right)>=sum(cent_r) and sum(left)+sum(cent_r)==sum(right)+sum(cent_l):
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

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

import sys, heapq
sys.setrecursionlimit(300000)

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

def solve(N: int, S: "List[str]"):
    tmp = []
    for i in range(N):
        cur = 0
        mn = 0
        for c in S[i]:
            if c == '(':
                cur += 1
            else:
                cur -= 1
                mn = min(mn, cur)
        tmp.append((mn, cur))

    tmp.sort(key=lambda x: (x[1] < 0, x[0], x[1]))
    #print(tmp)

    cur = 0
    for mn, cnt in tmp:
        if abs(mn) > cur:
            print(NO)
            return
        cur += cnt

    #print(cur)
    if cur == 0:
        ret = YES
    else:
        ret = NO
    print(ret)
    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:
N=int(input())
R=0
L=0
EdgeLeft=0
EdgeRight=0
for i in range(N):
    S=input()
    if S[0]=="(":
        if S[-1]==")" and EdgeLeft==1:
            EdgeRight=1
        else:
            EdgeLeft=1
    if S[0]!="(" and S[-1]==")":
        EdgeRight=1
    for s in S:
        if s=="(":
            R+=1
        else:
            L+=1
if (EdgeRight + EdgeLeft)>=2 and R==L:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
N=int(input())
L=[[0,0,0] for i in range(N)]
R=0
L=0
EdgeLeft=0
EdgeRight=0
for i in range(N):
    S=input()
    if S[0]=="(":
        if S[-1]==")" and EdgeLeft==1:
            EdgeRight=1
        else:
            EdgeLeft=1
    if S[0]!="(" and S[-1]==")":
        EdgeRight=1
    for s in S:
        if s=="(":
            R+=1
        else:
            L+=1
if (EdgeRight + EdgeLeft)>=2 and R==L:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
N=int(input())
L=[[0,0,0] for i in range(N)]
R=0
L=0
EdgeLeft=0
EdgeRight=0
EdgeLeftRight=0
for i in range(N):
    S=input()
    if S[0]=="(":
        if S[-1]==")":
            if EdgeLeftRight>=1:
                EdgeLeftRight=2
            else:
                EdgeLeftRight=1
        else:
            EdgeLeft=1
    if S[0]!="(" and S[-1]==")":
        EdgeRight=1
    for s in S:
        if s=="(":
            R+=1
        else:
            L+=1
if (EdgeLeftRight + EdgeLeft + EdgeRight)>=2 and R==L:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
N=int(input())
L=[[0,0,0] for i in range(N)]
R=0
L=0
EdgeLeft=0
EdgeRight=0
EdgeLeftRight=0
for i in range(N):
    S=input()
    if S[0]=="(":
        if S[-1]==")":
            EdgeLeftRight=1
        else:
            EdgeLeft=1
    if S[0]!="(" and S[-1]==")":
        EdgeRight=1
    for s in S:
        if s=="(":
            R+=1
        else:
            L+=1
if (EdgeLeftRight + EdgeLeft + EdgeRight)>=2 and R==L:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

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

n=int(input())
s=[input() for _ in range(n)]
p=[];m=[]
for si in s:
    cnt=0;a=0;b=0
    for i in range(len(si)):
        if si[i]==")":
            cnt+=1
        else:
            cnt-=1
        a=max(a,cnt)
    cnt=0
    for i in range(len(si)-1,-1,-1):
        if si[i]=="(":
            cnt+=1
        else:
            cnt-=1
        b=max(b,cnt)
    if b-a>=0:
        p.append((a,si))
    else:
        m.append((-b,si))
p.sort();m.sort()
ss=""

for _,si in p:
    ss+=si
for _,s in m:
    ss+=si
cnt=0
for i in range(len(ss)):
    if ss[i]=="(":
        cnt+=1
    else:
        cnt-=1
    if cnt<0:
        print("No")
        exit()
if cnt:
    print("No")
else:
    print("Yes")

Submission status: Wrong Answer

Solution code:
#atcoder template
def main():
    import sys
    imput = sys.stdin.readline
    #ここにコード
    #input
    from collections import Counter
    import numpy as np
    N = int(input())

    dp = []
    for i in range(N):
        S = str(input())
        l = len(S)
        S = S.replace("()", "", l//2+1)
        T = Counter(S)
        x = T["("]
        y = T[")"]
        if x**2 + y**2 != 0:
            dp.append([x, y])

    #output
    m = len(dp)
    if m == 1:
        print("No")
        exit()

    dp = np.array(dp)
    dp = sum(dp)
    left = dp[0]
    right = dp[1]
    # %%
    if left == right:
        print("Yes")
    else:
        print("No")

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from itertools import chain

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

open_close = 0
for key, last, low in chain(zenhan, kouhan):
    if open_close + low < 0:
        ans = "No"
        break
    else:
        open_close += last
else:
    if open_close:
        ans = "No"
    else:
        ans = "Yes"
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import chain

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

open_close = 0
for key, last, low in chain(zenhan, kouhan):
    if open_close + low < 0:
        ans = "No"
        break
    else:
        open_close += last
else:
    if open_close:
        ans = "No"
    else:
        ans = "Yes"
print(ans)

Submission status: Wrong Answer

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

plus = []
minus = []

for s in S:
    left, right = 0, 0
    tmp, min_tmp = 0, 0
    for ss in s:
        if ss == "(":
            left += 1
            tmp += 1
        else:
            right += 1
            tmp -= 1
        min_tmp = min(min_tmp, tmp)
    if left >= right:
        plus.append([left, right, min_tmp])
    else:
        minus.append(s[::-1])

S = minus
minus = []

for s in S:
    left, right = 0, 0
    tmp, min_tmp = 0, 0
    for ss in s:
        if ss == ")":
            left += 1
            tmp += 1
        else:
            right += 1
            tmp -= 1
        min_tmp = min(min_tmp, tmp)
    minus.append([right, left, min_tmp])

plus.sort(key = lambda x: - x[2])
minus.sort(key = lambda x: x[2])
#print(plus, minus)

cnt = 0
for l, r, m in plus + minus:
    if cnt + m < 0:
        print("No")
        exit()
    cnt += l - r

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

Submission status: Wrong Answer

Solution code:
#atcoder template
def main():
    import sys
    imput = sys.stdin.readline
    #ここにコード
    #input
    from collections import Counter
    N = int(input())

    dp = []
    for i in range(N):
        S = str(input())
        S = S.replace("()", "", N//2+1)
        T = Counter(S)
        x = T["("]
        y = T[")"]
        if x**2 + y**2 != 0:
            dp.append([x, y])

    #output
    left = 0
    right = 0
    l = len(dp)
    if l == 1:
        print("No")
        exit()

    for i in range(l):
        left += dp[i][0]
        right += dp[i][1]
        
    # %%

    if left == right:
        print("Yes")
    else:
        print("No")

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N=int(input())
L=[]
Sum=0
F=0
for i in range(N):
    s=input()
    Min=0
    cnt=0
    for j in range(len(s)):
        if s[j]=="(":
            cnt+=1
        else:
            cnt-=1
            if Min>=cnt:
                Min=cnt
    if cnt>0:
        L.append([-Min,-cnt])
    else:
        if Min==cnt and cnt<0:
            F=1
    Sum+=cnt
if Sum!=0:
    print("No")
else:
    L.sort()
    Sum=0
    for Min,cnt in L:
        if Sum-Min>=0:
            Sum-=cnt
        else:
            print("No")
            exit()
    if F==1:
        print("Yes")
    else:
        print("No")
    #print(L)

Submission status: Wrong Answer

Solution code:
N=int(input())
L=[]
Sum=0
F=0
for i in range(N):
    s=input()
    Min=0
    cnt=0
    for j in range(len(s)):
        if s[j]=="(":
            cnt+=1
        else:
            cnt-=1
            if Min>=cnt:
                Min=cnt
    if cnt>0:
        L.append([-Min,-cnt])
    else:
        if Min==cnt:
            F=1
    Sum+=cnt
if Sum!=0:
    print("No")
else:
    L.sort()
    Sum=0
    for Min,cnt in L:
        if Sum-Min>=0:
            Sum-=cnt
        else:
            print("No")
            exit()
    if F==1:
        print("Yes")
    else:
        print("No")
    #print(L)

Submission status: Wrong Answer

Solution code:
N=int(input())
L=[]
Sum=0
F=0
for i in range(N):
    s=input()
    Min=0
    cnt=0
    for j in range(len(s)):
        if s[j]=="(":
            cnt+=1
        else:
            cnt-=1
            if Min>=cnt:
                Min=cnt
    if cnt>=0:
        L.append([-Min,-cnt])
    else:
        if Min==cnt:
            F=1
    Sum+=cnt
if Sum!=0:
    print("No")
else:
    L.sort()
    Sum=0
    for Min,cnt in L:
        if Sum-Min>=0:
            Sum-=cnt
        else:
            print("No")
            exit()
    if F==1:
        print("Yes")
    else:
        print("No")
    #print(L)

Submission status: Wrong Answer

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


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

n = I()
A = []
B = []
for _ in range(n):
    s = S()
    ret = 0
    ret2 = 0
    for i in s:
        if ret and i == ')':
            ret -= 1
        elif i == '(':
            ret += 1
        else:
            ret2 += 1
    if ret2 > ret:
        A += [(ret, ret2)]
    else:
        B += [(ret, ret2)]

A.sort()
B.sort(key=lambda x:x[1])
L = A + B
now = 0
for x, y in L:
    if x > now:
        print('No')
        exit()
    now = now - x + y

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

Submission status: Wrong Answer

Solution code:
import sys
import heapq
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

N = int(input())

good_list = []
bad_list = []
zero_list = []
total = 0
for i in range(N):
  s = input()
  high = 0
  left_base = 0
  for i in s:
    if i == "(":
      high += 1
    else:
      high -= 1
      left_base = min(left_base,high)
  high_right = 0
  right_base = 0
  for i in s[::-1]:
    if i == ")":
      high_right += 1
    else:
      high_right -= 1
      right_base = min(right_base,high_right)
  if high < 0:
    bad_list.append((right_base,high_right))
  elif high == 0:
    zero_list.append((left_base,high))
  else:
    good_list.append((left_base,high))
  total += high

good_list = sorted(good_list)
bad_list = sorted(bad_list)

high = 0
for need,increase in good_list:
  if high < need:
      total = 114
  else:
      high += increase

for m,M in zero_list:
  if m >= high or M >= high:
      total = 514

for need,increase in bad_list:
  if high < need:
      total = 1919
  else:
      high -= increase

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

Submission status: Wrong Answer

Solution code:
import sys
import heapq
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

N = int(input())

good_list = []
bad_list = []
zero_list = []
total = 0
for i in range(N):
  s = input()
  high = 0
  left_base = 0
  for i in s:
    if i == "(":
      high += 1
    else:
      high -= 1
      left_base = min(left_base,high)
  high_right = 0
  right_base = 0
  for i in s[::-1]:
    if i == ")":
      high_right += 1
    else:
      high_right -= 1
      right_base = min(right_base,high_right)
  if high < 0:
    bad_list.append((right_base,high_right))
  elif high == 0:
    zero_list.append((left_base,high))
  else:
    good_list.append((left_base,high))
  total += high

good_list = sorted(good_list)
bad_list = sorted(bad_list)

high = 0
for need,increase in good_list:
  if high < need:
      total = 114
  else:
      high += increase

for m,M in zero_list:
  if m >= high or M >= high:
      total = 514

for need,increase in bad_list:
  if high < need:
      total = 1919
  else:
      high -= increase

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

Submission status: Wrong Answer

Solution code:
N = int(input())

good_list = []
bad_list = []
zero_list = []
total = 0
for i in range(N):
  s = input()
  high = 0
  left_base = 0
  for i in s:
    if i == "(":
      high += 1
    else:
      high -= 1
      left_base = min(left_base,high)
  high_right = 0
  right_base = 0
  for i in s[::-1]:
    if i == ")":
      high_right += 1
    else:
      high_right -= 1
      right_base = min(right_base,high_right)
  if high < 0:
    bad_list.append((right_base,high_right))
  elif high == 0:
    zero_list.append((left_base,high))
  else:
    good_list.append((left_base,high))
  total += high

good_list = sorted(good_list)
bad_list = sorted(bad_list)

high = 0
for need,increase in good_list:
  if high < need:
      total = 114
  else:
      high += increase

for m,M in zero_list:
  if m >= high or M >= high:
      total = 514

for need,increase in bad_list:
  if high < need:
      total = 1919
  else:
      high -= increase

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

Submission status: Wrong Answer

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

# process
T = []
for s in S:
    while '()' in s:
        s = s.replace('()', '')
    T.append(s)

l1 = []
l2 = []
for t in T:
    op = t.find('(')
    if op < 0:
        op = len(t)
    cl = len(t) - op
    
    if cl+op != 0:
        if cl <= op:
            l1.append((cl, op))
        else:
            l2.append((op, cl))

l1.sort()
l2.sort(reverse=True)

result = False
x = 0
if len(l1)+len(l2) == 0:
    result = True
elif len(l1)>0 and len(l2)>0 and l1[0][0]+l2[-1][0] == 0:
    for cl, op in l1:
        x += op-cl
        if x < 0:
            break
    if x >= 0:
        for op, cl in l2:
            x += op-cl
            if x < 0:
                break

        if x == 0:
            result = True

# output
print("Yes" if result else "No")

Submission status: Wrong Answer

Solution code:
N = int(input())
As = []
Bs = []

for _ in range(N):
  c = 0
  m = 0
  for s in input():
    if s == '(':
      c += 1
    elif s == ')':
      c -= 1
    m = min(m, c)
  if c >= 0:
    As.append((-m, c - m))
  else:
    Bs.append((-m, c - m))

As.sort(key=lambda x: x[0])
Bs.sort(key=lambda x: x[1], reverse=True)

f = True
c = 0
for (l, r) in As:
  if c < l:
    f = False
    break
  c += r - l
if f:
  for (l, r) in Bs:
    if c < l:
      f = False
      break
  c += r - l

f = f and (c == 0)

if f:
  print('Yes')
else:
  print('No')

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

def is_bracket_string(str):
  dir = 0
  for c in str:
    dir +=  ( -1  if c == '(' else +1 )
    if 0 < dir:
      return False
  return (dir == 0)

def check_all(strs):
  targets = []
  dirs = []
  for s in strs:
    dir = len(s) - 2 * s.count('(')
    if dir != 0 or not is_bracket_string(s):
      targets.append(s)
      dirs.append(dir)

  if sum(dirs) != 0:
    return False

  if len(targets) == 1:
    return False

  sorted_strs = [ s for (dir, s) in sorted(zip(dirs, targets), key=lambda x:x[0]) ]
  cat_str = ''.join(sorted_strs)
  return is_bracket_string(cat_str)


#
#
n = int(input())

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

if check_all(strs):
  print("Yes")
else:
  print("No")

Submission status: Wrong Answer

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

# process
T = []
for s in S:
    while '()' in s:
        s = s.replace('()', '')
    T.append(s)

l1 = []
l2 = []
for t in T:
    op = t.find('(')
    if op < 0:
        op = len(t)
    cl = len(t) - op
    
    if cl+op != 0:
        if cl <= op:
            l1.append((cl, op))
        else:
            l2.append((op, cl))

l1.sort()
l2.sort(reverse=True)

result = False
x = 0
if len(l1)+len(l2) == 0:
    result = True
elif len(l1)>0 and len(l2)>0 and l1[0][0]+l2[-1][0] == 0:
    for a, b in l1:
        x += b-a
    for b, a in l2:
        x += b-a

    if x == 0:
        result = True

# output
print("Yes" if result else "No")

Submission status: Wrong Answer

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

# process
l1 = []
l2 = []
for s in S:
    a = 0
    b = 0
    for c in s:
        if c == '(':
            b += 1
        else:
            b -= 1
        if b == -1:
            b = 0
            a += 1
    
    # print((a,b))
    if a+b != 0:
        if a <= b:
            l1.append((a, b))
        else:
            l2.append((b, a))

l1.sort()
l2.sort(reverse=True)

result = False
x = 0
if len(l1)+len(l2) == 0:
    result = True
elif len(l1)>0 and len(l2)>0 and l1[0][0]+l2[-1][0] == 0:
    for a, b in l1:
        x += b-a
    for b, a in l2:
        x += b-a

    if x == 0:
        result = True

# output
print("Yes" if result else "No")

Submission status: Wrong Answer

Solution code:
N = int(input())
S_s = [input() for _ in range(N)]
S_data = []
for S in S_s:
    life = 0
    A=0
    for c in S:
        if c == '(':
            life += 1
        else:
            if life > 0:
                life -= 1
            else:
                A += 1
    S_data.append(tuple([A,life]))
S_data.sort()
S_data = tuple(S_data)
life = 0
answer = True
for S_datum in S_data:
    life -= S_datum[0]
    if life < 0:
        answer = False
        break
    life += S_datum[1]
else:
    if life != 0:
        answer = False

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

Submission status: Wrong Answer

Solution code:
#from collections import defaultdict, deque
#import itertools
#import numpy as np
#import re

def main():
    N = int(input())
    SS = []
    for _ in range(N):
        SS.append(input())
    S = []
    for s in SS:
        while '()' in s:
            s = s.replace('()', '')
        S.append(s)
    #print(S)
    S = [s for s in S if s != '']
    sum_op = 0
    sum_cl = 0
    S_both_op = []
    S_both_cl = []
    for s in S:
        if not ')' in s:
            sum_op += len(s)
        elif not '(' in s:
            sum_cl += len(s)
        else:
            pos = s.find('(')
            if pos <= len(s) - pos:
                S_both_op.append((pos, len(s)-pos))  #closeのほうが少ない、'))((('など -> (2,3)
            else:
                S_both_cl.append((pos, len(s)-pos))  #closeのほうが多い、')))(('など -> (3,2)

    # S_both_opは、耐えられる中でより伸ばす順にしたほうがいい？
    S_both_op.sort(key=lambda x: (x[0], x[0]-x[1]))  #closeの数が小さい順にsortかつclose-openが小さい=伸ばす側にsort
    S_both_cl.sort(key=lambda x: (x[0], x[0]-x[1]))  #これもcloseの数が小さい順にsortかつclose-openが小さい=伸ばす側にsort

    for p in S_both_op:
        sum_op -= p[0]
        if(sum_op < 0 ):
            print('No')
            exit()
        sum_op += p[1]
    for p in S_both_cl:
        sum_op -= p[0]
        if(sum_op < 0 ):
            print('No')
            exit()
        sum_op += p[1]
    
    if sum_op == sum_cl:
        print('Yes')
    else:
        print('No')

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    SS = []
    for _ in range(N):
        SS.append(input())
    S = []
    for s in SS:
        while '()' in s:
            s = s.replace('()', '')
        S.append(s)
    #print(S)
    S = [s for s in S if s != '']
    sum_op = 0
    sum_cl = 0
    S_both_op = []
    S_both_cl = []
    for s in S:
        if not ')' in s:
            sum_op += len(s)
        elif not '(' in s:
            sum_cl += len(s)
        else:
            pos = s.find('(')
            if pos <= len(s) - pos:
                S_both_op.append((pos, len(s)-pos))  #closeのほうが少ない、'))((('など -> (2,3)
            else:
                S_both_cl.append((pos, len(s)-pos))  #closeのほうが多い、')))(('など -> (3,2)

    # S_both_opは、耐えられる中でより伸ばす順にしたほうがいい？
    S_both_op.sort(key=lambda x: x[0])  #closeの数が小さい順にsort
    S_both_cl.sort(key=lambda x: x[0])  #これもcloseの数が小さい順にsort

    for p in S_both_op:
        sum_op -= p[0]
        if(sum_op < 0 ):
            print('No')
            exit()
        sum_op += p[1]
    for p in S_both_cl:
        sum_op -= p[0]
        if(sum_op < 0 ):
            print('No')
            exit()
        sum_op += p[1]
    
    if sum_op == sum_cl:
        print('Yes')
    else:
        print('No')

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N=int(input())
L=[]
Sum=0
for i in range(N):
    s=input()
    Min=0
    cnt=0
    for j in range(len(s)):
        if s[j]=="(":
            cnt+=1
        else:
            cnt-=1
            if Min>=cnt:
                Min=cnt
    if cnt>=0:
        L.append([-Min,-cnt])
    Sum+=cnt
if Sum!=0:
    print("No")
else:
    L.sort()
    Sum=0
    for Min,cnt in L:
        if Sum-Min>=0:
            Sum-=cnt
        else:
            print("No")
            exit()
    print("Yes")
    #print(L)

Submission status: Wrong Answer

Solution code:
N=int(input())
L=[]
Sum=0
for i in range(N):
    s=input()
    Min=0
    cnt=0
    for j in range(len(s)):
        if s[j]=="(":
            cnt+=1
        else:
            cnt-=1
            if Min>=cnt:
                Min=cnt
    if cnt>=0:
        L.append([-Min,-cnt])
    Sum+=cnt
if Sum!=0:
    print("No")
else:
    L.sort()
    Sum=0
    for Min,cnt in L:
        if Sum-Min>=0:
            Sum-cnt
        else:
            print("No")
            exit()
    print("Yes")
    #print(L)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3


def countpars(s):
    lc = 0
    rc = 0
    for ch in s:
        if ch == '(':
            lc += 1
        else:
            if lc > 0:
                lc -= 1
            else:
                rc += 1
    return (lc, rc)


n = int(input())

ssl = []
ssr = []
for i in range(n):
    (clc, crc) = countpars(input())
    if clc >= crc:
        ssl.append((clc, crc))
    else:
        ssr.append((clc, crc))

ssl.sort(key=lambda x: x[1])
ssr.sort(key=lambda x: x[1], reverse=True)

lc = 0
rc = 0

for (clc, crc) in ssl:
    lc -= crc
    if lc < 0:
        print('No')
        exit()

    lc += clc

for (clc, crc) in ssr:
    lc -= crc
    if lc < 0:
        print('No')
        exit()
    lc += clc
        

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

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3


def countpars(s):
    lc = 0
    rc = 0
    for ch in s:
        if ch == '(':
            lc += 1
        else:
            if lc > 0:
                lc -= 1
            else:
                rc += 1
    return (lc, rc)


n = int(input())

ssl = []
ssr = []
for i in range(n):
    (clc, crc) = countpars(input())
    if clc >= crc:
        ssl.append((clc, crc))
    else:
        ssr.append((clc, crc))

ssl.sort(key=lambda x: x[1])

lc = 0
rc = 0

for (clc, crc) in ssl:
    lc -= crc
    if lc < 0:
        print('No')
        exit()

    lc += clc

for (clc, crc) in ssr:
    lc -= crc - clc
    if lc < 0:
        print('No')
        exit()


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

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3

def countpars(s):
    lc = 0
    rc = 0
    for ch in s:
        if ch == '(':
            lc += 1
        else:
            if lc > 0:
                lc -= 1
            else:
                rc += 1
    return (lc, rc)


n = int(input())

rc = 0
lc = 0
for i in range(n):
    (clc, crc) = countpars(input())
    fl = min(clc, rc)
    fr = min(crc, lc)
    if fl >= fr:
        #from left
        if clc >= rc:
            nlc = lc + clc - rc
            nrc = crc
        else:
            nrc = rc - clc + crc
    else:
        #from right
        if crc >= lc:
            nlc = clc            
            nrc = rc + crc - lc
        else:
            nlc = lc - crc + clc
    (lc, rc) = (nlc, nrc)

if rc == 0 and lc == 0:
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

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

N = int(input())
S = [input()[:-1] for _ in range(N)]
rl1, rl2 = [], []

for Si in S:
    l, r = 0, 0
    
    for i in range(len(Si)):
        if Si[i]=='(':
            l += 1
        else:
            if l==0:
                r += 1
            else:
                l -= 1
    
    if l-r>=0:
        rl1.append((r, l))
    else:
        rl2.append((r, l))
    
rl1.sort(key=lambda t: t[0])
rl2.sort(key=lambda t: t[1], reverse=True)
rl3 = rl1+rl2
bal = 0

for r, l in rl3:
    bal -= r
    
    if bal<0:
        print(-1)
        exit()
    
    bal += l

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

Submission status: Wrong Answer

Solution code:
n=int(input())
A=[]
for i in range(n):
    s=input()
    l=0
    o=0
    for c in s:
        if c=='(':
            l+=1
        else:
            l-=1
            o=min(o,l)
    A.append((l,o))
A.sort(key=lambda x:-10**9 if x[1]==0 else x[1] if x[0]>=0 else 10**7+x[1]-x[0])
last=0
for l,o in A:
    if last+o<0:
        print("No")
        exit(0)
    last+=l
print("Yes" if last==0 else "No")