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())
start = 0
end = 0
left = 0
double = []
right = 0
for i in range(n):
    s = str(input())
    kienaileft = 0
    kienairight = 0
    for j in range(len(s)):
        if s[j] == ")":
            kienaileft += 1
        else:
            break
    for j in range(len(s)):
        if s[-(j+1)] == "(":
            kienairight += 1
        else:
            break
    nowleft = 0
    nowright = 0
    for j in range(kienaileft,len(s)-kienairight):
        if s[j] == ")":
            nowleft += 1
        else:
            nowright += 1
    num = min(nowleft,nowright)
    kienaileft += nowleft -num
    kienairight += nowright -num
    if kienaileft != 0:
        if kienairight != 0:
            double.append([kienaileft,kienairight])
        else:
            left += kienaileft
    else:
        if kienairight != 0:
            right += kienairight
  # print(left,double,right)
if left + sum([double[i][0] for i in range(len(double))]) != sum([double[i][1] for i in range(len(double))]) + right:
    print("No")
    exit()
if len(double) != 0:
    if not left or not right:
        print("No")
        exit()
else:
    if left == right:
        print("Yes")
        exit()
double.sort(key=lambda x:x[1]+x[0])
double.sort()
double.sort(key=lambda x:x[0]-x[1])
now = left
for a,b in double:
    if now < a:
        print("No")
        exit()
    now += (b-a)
print("Yes")

Submission status: Wrong Answer

Solution code:
import bisect
import copy
import heapq
import sys
import itertools
import math
import queue
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
# mod = 10 ** 9 + 7
mod = 998244353 

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]
def init_dp1(init, N): return [init for _ in range(N)]
def init_dp2(init, N, M): return [[init for _ in range(M)] for _ in range(N)]


class V:
    def __init__(self, f, v=None):
        self.f = f
        self.v = v
 
    def __str__(self):
        return str(self.v)
 
    def ud(self, n):
        if n is None:
            return

        if self.v is None:
            self.v = n
            return
        self.v = self.f(self.v, n) 


def f(S):
    l = 0
    r = 0
    for s in S:
        if s == ")":
            if l > 0:
                l -= 1
            else:
                r += 1
        else:
            l += 1
    return (l, r)


def main():
    N = int(input())
    S = list(input().strip() for _ in range(N))

    l_0 = set()
    r_0 = set()
    F = map(f, S)
    L = []
    R = []
    for i, (l, r) in enumerate(F):
        if l == 0 and len(l_0) < 2:
            l_0.add(i)
        if r == 0 and len(r_0) < 2:
            r_0.add(i)
        
        if l <= r:
            L.append((l, r))
        else:
            R.append((l, r))


    if len(l_0) == 1 and len(r_0) == 1:
        if l_0 == r_0:
            print("No")
            return

    r_n = 0
    for l, r in L:
        if l > r_n:
            print("No")
            return 
        r_n += r - l

    print("Yes")


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    D = []
    for i in range(N):
        S = input()
        m = 0
        p = 0
        for c in S:
            if c == '(':
                p += 1
            else:
                p -= 1
            m = min(m, p)
        D.append((p, 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:
import heapq
import sys

#input = sys.stdin.readline

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

    data = [0]*N
    for i in range(N):
        S = list(str(input()))
        s = 0
        m = 0
        for j in range(len(S)):
            if S[j] == "(":
                s += 1
            else:
                s -= 1
                m = min(m,s)
        data[i] = (-m,-s)


    heapq.heapify(data)
    x = 0
    valid = []
    heapq.heapify(valid)

    det = 0

###
#print("data",data)
#print("valid",valid)
#print(x)
###

    while data or valid:
        while data and x - data[0][0] >= 0:
            y = heapq.heappop(data)
            heapq.heappush(valid,(y[1],y[0]))
    
        while valid and x >= 0:
            z = heapq.heappop(valid)
            x -= z[0]
    
        if data and x - data[0][0] < 0:
            det = -1
            break

    if det == 0 and x == 0 and valid == []:
        print("Yes")
    else:
        print("No")

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
A = []
for i in range(n):
    s = input()
    p = 0
    q = 0
    for j in range(len(s)):
        if s[j]=='(':p+=1
        else:q+=1
    A.append(p-q)
if sum(A)==0:
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

Solution code:
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n = int(input())
S = [input() for i in range(n)]
for idx,s in enumerate(S):
  l,r = 0,0
  for i ,si in enumerate(s):
    if si == "(":
      r += 1
    elif si == ")" and r > 0:
      r -= 1
    else:
      l += 1
  S[idx] = (l,r)
lsum = rsum = 0
lzero = zeror = 0
for l,r in S:
  if l > 0 or r > 0:count += 1
  if l > 0 and r == 0:lzero += 1
  if r > 0 and l == 0:zeror += 1
  lsum += l
  rsum += r
if lsum == rsum and (count == 0 or (lzero and zeror)):
  print("Yes")
else:
  print("No")
# print(S,count,lzero , zeror)

Submission status: Wrong Answer

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

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

tmp = []
for i,s in enumerate(S):
    tmp.append([s.count("(")-s.count(")"),i])

tmp.sort(reverse=True)

a = 0
b = 0
s = ""
for _,i in tmp:
    s += S[i]
print(s)
for i in s:
    if i == "(":
        a += 1
    else:
        b += 1
    if b > a:
        print("No")
        exit()

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

Submission status: Wrong Answer

Solution code:
N=int(input())

slist=[]
for _ in range(N):
  s=input()
  while True:
    s_new=s.replace("()","")
    #print(s,s_new)
    if s_new==s:
      s=s_new
      break
    else:
      s=s_new
  slist.append(s)
#print(slist)

rl_list=[]
for i in range(N):
  s=slist[i]
  l=s.count("(")
  r=s.count(")")
  if l>0 or r>0:
    rl_list.append((l-r,l,r))
rl_list.sort(reverse=True)
#print(rl_list)
  
lsum=rsum=0
lmin=rmin=float("inf")
l0max=r0max=0
for lr,r,l in rl_list:
  rsum+=r
  lsum+=l
  lmin=min(lmin,l)
  rmin=min(rmin,r)
  if l==0:
    l0max=max(l0max,r)
  if r==0:
    r0max=max(r0max,l)
  
if rsum!=lsum:
  print("No")
elif rmin>0 or lmin>0:
  print("No")
else:
  #print(l0max,r0max)
  if r0max>=rl_list[1][1]:
    print("Yes")
  else:
    print("No")

Submission status: Wrong Answer

Solution code:
N=int(input())

L=[]
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
    L.append([Min,cnt])
L.sort(reverse=True)
#print(L)

Sum=0
for i,j in L:
    Sum+=j
if Sum!=0:
    print("No")
else:
    #print("Yes?")
    import heapq
    Q=[]
    heapq.heapify(Q)
    cnt=0
    po=0
    for i in range(10**6+2):
        while po<len(L) and -L[po][0]<=cnt:
            heapq.heappush(Q,(L[po][1],L[po][0]))
            po+=1
        if len(Q)==0:
            if po!=len(L):
                print("No")
                exit()
            else:
                print("Yes")
                exit()
        q0,q1=heapq.heappop(Q)
        cnt+=q0

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
mod = 998244353


def main():
    N = int(input())
    S = []
    for _ in range(N):
        s = input()
        max_depth = 0
        height = 0
        for c in s:
            if c == '(':
                height += 1
            else:
                height -= 1
                max_depth = min(max_depth, height)
        S.append((max_depth, height - max_depth))
    S.sort(key=lambda x: (x[0], x[1]))

    height = 0
    if S[-1][0] != 0:
        print("No")
        return
    while S:
        d, h = S.pop()
        #print("({}, {})".format(d, h))
        if height - d < 0:
            print("No")
            return
        height += d+h
    if height != 0: print("No")
    else: print("Yes")





if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

LEFT = [0]*N
RIGHT = [0]*N


for i in range(N):
    right=0
    left=0
    
    for j in S[i]:
        if j == ")":
            if left>0:
                left -= 1
            else:
                right += 1
        else:
            left += 1
    LEFT[i]+=left
    RIGHT[i]+=right
    
    if right==0 and left>0:
        check1 += 1

    if right>0 and left==0:
        check2 += 1

        
if sum(RIGHT) == sum(LEFT) and check1>0 and check2>0 and check1 == check2:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
def init_max(init_max_val):
    #set_val
    for i in range(n):
        seg_max[i+num_max-1]=init_max_val[i]
    for i in range(num_max-2,-1,-1) :
        seg_max[i]=max(seg_max[2*i+1],seg_max[2*i+2])
    
def update_max(k,x):
    k += num_max-1
    seg_max[k] = x
    while k:
        k = (k-1)//2
        seg_max[k] = max(seg_max[k*2+1],seg_max[k*2+2])
    
def query_max(p,q):
    if q<=p:
        return ide_ele_max
    p += num_max-1
    q += num_max-2
    res=ide_ele_max
    while q-p>1:
        if p&1 == 0:
            res = max(res,seg_max[p])
        if q&1 == 1:
            res = max(res,seg_max[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = max(res,seg_max[p])
    else:
        res = max(max(res,seg_max[p]),seg_max[q])
    return res


n=int(input())

ide_ele_max = (-10**9,-10**9)
num_max =2**(n-1).bit_length()
seg_max=[ide_ele_max]*2*num_max

A=[]#left,over
for i in range(n):
    s=input()
    leftlast=0
    over=0
    for c in s:
        if c=='(':
            leftlast+=1
        else:
            leftlast-=1
            over=min(over,leftlast)
    A.append([leftlast,over])
A.sort(key=lambda x: x[1])

left=[(a[0],idx) for idx,a in enumerate(A)]
over=[a[1] for a in A]

init_max(left)

from bisect import bisect_left
now=0
flag=False
for i in range(n):
    idx=bisect_left(over,-now)
    M=query_max(idx,n-1)
    M,i=M # max,index
    if M<=-10**7:
        flag=True
        break
    update_max(i,(-10**9,0))
    now+=M

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

Submission status: Wrong Answer

Solution code:
import heapq

N = int(input())
S = [input() for _ in range(N)]
B1 = []
B2 = []
for s in S:
    ncl = nop = 0
    for c in s:
        if c=='(':
            nop+=1
        else:
            if nop>0: nop-=1
            else: ncl+=1

    if nop-ncl>=0:
        B1.append((nop-ncl, ncl))
    else:
        B2.append((nop-ncl, ncl))

#print(B)
    
B1 = sorted(B1, key=lambda x:x[1])
B2 = sorted(B2, key=lambda x:-x[1])
N1 = len(B1)
h = []
x = 0
ib = 0
while True:
    while ib<N1:
        b = B1[ib]
        if b[1]>x: break
        heapq.heappush(h, (-b[0]*10000000-b[1], b[0], b[1]))
        ib += 1
    #print(h)

    if len(h)==0:
        break

    c = heapq.heappop(h)
    if c[2]>x:
        print('No')
        exit()
        
    x += c[1]


if ib<N1:
    print('No')
    exit()

for b in B2:
    if b[1]>x:
        print('No')
        exit()
    x+=b[0]
    
print('Yes' if x==0 else '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]),-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 networkx as nx

N = input().split()
A = list(map(str, input().split()))

I = list()
O = list()
for s in A:
  a = 0
  for c in s:
    if(c==')'):
      ++a
    else:
      --a
  I.append(a)
  a = 0
  for c in reversed(s):
    if(c=='('):
      ++a
    else:
      --a
  O.append(a)

if nx.algorithms.graphical.is_digraphical(I, O):
  print("Yes")

Submission status: Wrong Answer

Solution code:
def examA():
    S = SI()
    T = SI()
    if S==T[:len(S)]:
        if len(S)+1==len(T):
            print("Yes")
            return
    print("No")
    return

def examB():
    A, B, C, K = LI()
    ans = 0
    if A>=K:
        ans = K
    else:
        ans += A
        K -= A
        if K>B:
            K -= B
            ans -= K
    print(ans)
    return

def examC():
    N, M, X = LI()
    C = [LI()for _ in range(N)]
    loop = 2**N
    ans = inf
    for l in range(loop):
        cur = 0
        A = [0]*M
        for j in range(N):
            if (1<<j)&l>0:
                cur += C[j][0]
                for k in range(M):
                    A[k] += C[j][k+1]
        flag = True
        for i in range(M):
            if A[i]<X:
                flag = False
                break
        if flag:
            ans = min(ans,cur)
    if ans==inf:
        print(-1)
        return
    print(ans)
    return

def examD():
    N, K = LI()
    A = LI()
    locat_doubling = [[0]*N for _ in range(100)]
    for i in range(N):
        locat_doubling[0][i] = i
        locat_doubling[1][i] = A[i]-1
    for k in range(2,100):
        for i in range(N):
            locat_doubling[k][i] = locat_doubling[k-1][locat_doubling[k-1][i]]
    #print(locat_doubling)
    ans = [i for i in range(N)]
    for k in range(100):
        for i in range(N):
            if K&(1<<k)>0:
                ans[i] = locat_doubling[k+1][ans[i]]
    print(ans[0]+1)
    return

def examE():
    class combination():
        # 素数のmod取るときのみ　速い
        def __init__(self, n, mod):
            self.n = n
            self.mod = mod
            self.fac = [1] * (n + 1)
            self.inv = [1] * (n + 1)
            for j in range(1, n + 1):
                self.fac[j] = self.fac[j - 1] * j % mod

            self.inv[n] = pow(self.fac[n], mod - 2, mod)
            for j in range(n - 1, -1, -1):
                self.inv[j] = self.inv[j + 1] * (j + 1) % mod

        def comb(self, n, r):
            if r > n or n < 0 or r < 0:
                return 0
            return self.fac[n] * self.inv[n - r] * self.inv[r] % self.mod
    N, M, K = LI()
    C = combination(N,mod2)
    ans = 0
    for i in range(N):
        if i>K:
            break
        cur = C.comb(N-1,i) * M * pow((M - 1), N - i - 1, mod2) % mod2
        #print(cur)
        ans += cur
        ans %= mod2
    print(ans)
    return

def examF():
    N = I()
    LRC = [[0,0,0]for _ in range(N)]
    flag_l = False; flag_r = False
    C = 0
    for i in range(N):
        S = SI()
        cur = 0
        l = 0
        for s in S:
            if s==")":
                cur += 1
            else:
                cur -= 1
            if cur>l:
                l = cur
        LRC[i][0] = l
        if l==0:
            flag_l = True
        cur = 0
        r = 0
        for s in S[::-1]:
            if s=="(":
                cur += 1
            else:
                cur -= 1
            if cur>r:
                r = cur
        LRC[i][1] = r
        if r==0:
            flag_r = True
        LRC[i][2] = l-r
        C += l-r
    if (not flag_l) or (not flag_r):
        print("No")
        return
    if C!=0:
        print("No")
        return
    #print(LRC)
    LRC.sort(key=lambda x:x[1])
    A = [0]*N
    B = [0]*N
    #print(LRC)
    for i in range(N):
        A[i] = LRC[i][2]
        B[i] = LRC[i][0]
    now = 0
    for i in range(N):
        ne = bisect.bisect_right(B,now)-1
        now += A[ne]
        #print(now,ne)
        A[ne] = 0
    if random.random()>0.5:
        print("No")
        return
    print("Yes")
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examF()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn

5
))))(((((
(((
))))))((
)((
)
"""

Submission status: Wrong Answer

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

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

def iterate_tokens():
    for line in sys.stdin:
        for word in line.split():
            yield word

def solve(N: int):
    tokens = iterate_tokens()
    left_rights = deque([(0, 0)])
    left_all = 0
    right_all = 0
    for _ in range(N):

        #print("all", left_all, right_all)

        s = next(tokens)
        left = 0
        right = 0
        for ss in s:
            #print(ss)
            #print(left, right)
            if ss == ")":
                if right > 0:
                    right -= 1
                else:
                    left += 1
            else:
                right += 1

        # print(left, right)
        length = len(left_rights)
        for _ in range(length):
            left_right = left_rights.popleft()

            if max(0, left_right[0] - right) + left + max(0, right - left_right[0]) + left_right[1] > max(0, left_right[1] - left) + right + max(0, left - left_right[1]) + left_right[0]:
                left_rights.append((max(0, left_right[1] - left) + right, max(0, left - left_right[1]) + left_right[0]))
            elif max(0, left_right[0] - right) + left + max(0, right - left_right[0]) + left_right[1] == max(0, left_right[1] - left) + right + max(0, left - left_right[1]) + left_right[0]:
                left_rights.append((max(0, left_right[1] - left) + right, max(0, left - left_right[1]) + left_right[0]))
                left_rights.append((max(0, left_right[0] - right) + left, max(0, right - left_right[0]) + left_right[1]))
            else:
                left_rights.append((max(0, left_right[0] - right) + left, max(0, right - left_right[0]) + left_right[1]))
            #print(new_left_all_right, new_right_all_right)



            #print(new_left_all_left, new_right_all_left)

    if (0, 0) in left_rights:
        print(YES)
    else:
        print(NO)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    solve(N)

if __name__ == '__main__':
    main()

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], -x[0]))
    s3.sort(key=lambda x: (x[0], -x[1]))
    cnt = 0
    for i, j in s2:
        if cnt+i < 0:
            print("No")
            return
        cnt += j
    for i, j in s3:
        if cnt+i < 0:
            print("No")
            return
        cnt += j
    if cnt != 0:
        print("No")
        return
    print("Yes")


main()

Submission status: Wrong Answer

Solution code:
import random

r = random.randint(0,1)

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

Submission status: Wrong Answer

Solution code:
from collections import deque
N = int(input())
A = []
INF = float("inf")
L,R = 0,0
for i in range(N):
    S = input()
    a = [0,0]
    if S!="":
        l,r = 0,0
        for s in S:
            if s=="(":
                r+=1
            else:
                if r>0:
                    r-=1
                else:
                    l+=1
    if l*r == 0:
        L+=l
        R+=r
    else:
        A.append([l,r,0])
A.sort(key=lambda x:(x[0],-x[1]))
ans = "Yes"
Q = deque(A)
K = R
while Q:
    l,r,v = Q.popleft()
    if K<l:
        if v==1:
            ans = "No"
            break
        Q.append([l,r,1])
    else:
        K += r-l
if K!=L:
    ans = "No"
print(ans)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# (と)の数は同じ
N = ir()
S = [[1 if x == '(' else -1 for x in sr()] for _ in range(N)]
bl = True
if sum(sum(x) for x in S) != 0:
    bl = False
S.sort(key=lambda x: sum(x), reverse=True)
cur = 0
for s in S:
    temp = 0
    for x in s:
        temp += x
        if temp < 0:
            break
    else:
        cur += temp
    if cur < 0:
        print('No'); exit()

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

Submission status: Wrong Answer

Solution code:
n = int(input())
R = 0
L = 0
flag = 0
M = []
for _ in range(n):
    s = input()
    right = 0
    left = 0
    for w in s:
        if w == "(":
            left += 1
        if w == ")":
            if left > 0:
                left -= 1
            else:
                right += 1
    if left > 0 and right > 0:
        M.append((right, left))
    elif left == 0 and right > 0:
        R += right
    elif left > 0 and right == 0:
        L += left
ML = 0
MR = 0
for mr, ml in M:
    if MR == 0 and ML == 0:
        MR += mr
        ML += ml
    elif MR == 0:
        if ML > mr:
            ML -= mr
        else:
            ML = 0
            MR += mr - ML
        MR += mr
    elif ML == 0:
        if MR > ml:
            MR -= ml
        else:
            MR = 0
            ML += ml - MR
        ML += ml
    else:
        if ML > mr:
            ML -= mr
            ML += ml
        else:
            mr -= ML
            ML = 0
            ML += ml
            MR += mr

if ML == 0 and MR > 0:
    R += MR
elif MR == 0 and ML > 0:
    L += ML
elif MR > 0 and ML > 0:
    L -= MR
    if L < 0:
        flag = 1
    L += ML


if L != R:
    flag = 1
if flag:
    print("No")
else:
    print("Yes")

Submission status: Wrong Answer

Solution code:
def main():
    from collections import defaultdict
    import sys
    input = sys.stdin.readline

    N = int(input())

    dc = defaultdict(int)
    do = defaultdict(int)

    op = 0
    cl = 0
    for _ in range(N):
        s = input().rstrip()

        if s[0] == '(':
            op += 1
        if s[-1] == ')':
            cl += 1

        open_ = 0
        close_ = 0
        for c in s:
            if c == '(':
                open_ += 1
            else:
                if open_:
                    open_ -= 1
                else:
                    close_ += 1

        if ((close_ or open_) and (close_ != open_)):
            dc[close_] += 1
            do[open_] += 1

    if not dc and not do:
        print('No')
        return

    if not (op % 2 == 0 and cl % 2 == 0):
        print('No')
        return

    for key in {*dc.keys(), *do.keys()}:
        if dc[key] != do[key]:
            print('No')
            return

    print('Yes')


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

N = int(sys.stdin.readline().strip())

S = []
for _ in range(N):
    s_i = sys.stdin.readline().strip()
    S.append(s_i)

# left open bracket, right open bracketの数をキーとしたcount
# ex)
# ")": (0, 1)
# "(": (1, 0)
# "()": (0, 0)
# ")()(": (1, 1)
counts = {}
sum_left = 0
for s_i in S:
    left = 0
    right = 0
    stack = []
    for bracket in s_i:
        if stack:
            if stack[-1] == "(" and bracket == ")":
                stack.pop()
                continue
            elif stack[-1] == ")" and bracket == "(":
                stack.pop()
                continue
        stack.append(bracket)
    
            
    left = stack.count("(")
    right = stack.count(")")
    # print(left, right)
    # sum_bracket += left - right
    c = (left, right)
    if c not in counts:
        counts[c] = 0
    counts[c] += 1

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

pure_left = 0
pure_right = 0
n_left = 0
n_right = 0
for (left, right), count in counts.items():
    if left == 0 and right == 0:
        continue
    if left == 0:
        pure_right += right 
    elif right == 0:
        pure_left += left
    else:
        n_left += left
        n_right += right

if n_left == pure_right and n_right == pure_left:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N = int(input())
S = [input() for _ in range(N)]
X = [[0, 0] for _ in range(N)]
op, cl = 0, 0
for i in range(N):
    for j in S[i]:
        if j == '(':
            op += 1
        else:
            cl += 1
if op == cl:
    for i in range(N):
        n = len(S[i])
        l, r = 0, 0
        ll, rr = 0, 0
        for j in range(n):
            if S[i][j] == ')':
                if l > 0:
                    l -= 1
                else:
                    rr += 1
            else:
                l += 1
        X[i][1] = -rr
        l, r = 0, 0
        for j in range(n, 0, -1):
            if S[i][j-1] == '(':
                if r > 0:
                    r -= 1
                else:
                    ll += 1
            else:
                r += 1
        X[i][0] = ll
    X.sort()
    flg = True
    c = 0
    for i in range(1, N):
        if flg:
            if X[i][1] == 0:
                flg = False
                c = i
    if c == 0:
        print("No")
    else:
        SS = sum(X[_][0] + X[_][1] for _ in range(N))
        if X[0][0] == 0 and SS == 0:
            print("Yes")
        else:
            print("No")
else:
  print("No")

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, Counter, namedtuple, deque
import itertools
import functools
import bisect
import heapq
import math
# MOD = 10**9+7
# MOD = 998244353


def count(s):
    left = right = 0
    for i in range(len(s)):
        if s[i] == "(":
            left += 1
        else:
            if left > 0:
                left -= 1
            else:
                right += 1

    return left, right


n = int(input())
S = [input() for i in range(n)]
A = [count(s) for s in S]
A.sort(key=lambda x: (x[1], x[1]-x[0]))

left_rem = 0
for left, right in A:
    left_rem -= right
    if left_rem < 0:
        print("No")
        exit()
    left_rem += left

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

Submission status: Wrong Answer

Solution code:
N = int(input())
if N == 1:
    st = 0
    S = input()
    for x in S:
        if x == '(':
            st += 1
        else:
            if st > 0:
                st -= 1
            else:
                print('No')
                exit()
    if st == 0:
        print('Yes')
    else:
        print('No')
    exit()
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')