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, 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
for l,r in S:
  if l > 0 or r > 0:count += 1
  lsum += l
  rsum += r
if lsum == rsum and (count == 0 or count >= 2):
  print("Yes")
else:
  print("No")

Submission status: Wrong Answer

Solution code:
# m = 998244353
#
# def comb(idx, _m, _k, m, k, tb):
#     if idx == 0:
#         return 1
#
#     if k < 0 or m < 0:
#         return 0
#
#     if k == 0:
#         return comb(idx, )
#
#     if (idx, k, m) in tb:
#         return tb[(idx, k, m)]
#
#     a = comb(idx - 1, _m - 1, _k, m, k, tb) % m
#     b = comb(idx - 1, _m, _k - 1, m, k, tb) % m
#
#     tb[(idx, m, k)] = (l + r) % m
#     return tb[(idx, m, k)]
#
# def main():
#     n, m, k = tuple([int(e) for e in input().split()])
#     print(comb(n, m, k, {}))

def main():
    n = int(input())
    s = []
    for i in range(n):
        s1 = input()
        s.append(s1)
    s.sort()

    o = 0
    s = ''.join(s)
    for i in range(len(s)):
        if s[i] == '(':
            o += 1
        else:
            o -= 1
        if o < 0:
            break
    if o != 0:
        print('No')
    else:
        print('Yes')


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
import sys
sys.setrecursionlimit(10**9)
from collections import deque
import heapq
from itertools import combinations
import bisect

n=int(input())
l=[]
for i in range(n):
    l.append(list(input()))

p=0
q=0
for i in range(n):
    for j in l[i]:
        if j=='(':
            p+=1
        else:
            q+=1
if p!=q:
    print('No')
    exit()
pl=[]
ql=[]
ml=[]
for i in range(n):
    a=l[i]
    p=0
    q=0
    for j in a:
        if j=='(':
            p+=1
        else:
            q+=1
    if p>q:
        pl.append(a)
    elif p<q:
        ql.append(a)
    else:
        ml.append(a)
if pl:
    pl.sort()
if ql:
    ql.sort()
if ml:
    ml.sort()
if pl:
    if pl[0][0]==')':
        print('No')
        exit()
else:
    if ml[0][0]==')':
        print('No')
        exit()

if ql:
    if ql[-1][-1]=='(':
        print('No')
        exit()
else:
    if ml[-1][-1]=='(':
        print('No')
        exit()

if pl:
    pp=[]
    for i in pl:
        d=0
        t=0
        for j in i:
            if j=='(':
                d+=1
            else:
                d-=1
            t=max(t,-d)
        pp.append([t,d])
    pp.sort(key=lambda x: x[0]*(10**6)-x[1])
    d=0
    for a,b in pp:
        if d<b:
            print('No')
            exit()
        d+=a-b
if ql:
    pp=[]
    for i in ql:
        d=0
        t=0
        for j in range(len(i)):
            if i[len(i)-1-j]==')':
                d+=1
            else:
                d-=1
            t=max(t,-d)
        pp.append([t,d])
    pp.sort(key=lambda x: x[0]*(10**6)-x[1])
    d=0
    for a,b in pp:
        if d<b:
            print('No')
            exit()
        d+=a-b

print('Yes')

Submission status: Wrong Answer

Solution code:
N = int(input())
li = []

for i in range(N):
    S = input()

    memo = 0
    memo2 = -10**10
    for j in range(len(S)):
        if S[j] == "(":
            memo -= 1
        else:
            memo += 1
        memo2 = max(memo,memo2)
    
    li.append([memo2,S])

li = sorted(li,key=lambda x:x[1])

# print(li)

cnt = 0
for i in range(len(li)):
    cnt += li[i][0]
    if cnt > 0:
        print("No")
        break
else:
    print("Yes")

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([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 = True, key = lambda x: x[0])
    for min_v, v in neg1:
        if u + min_v < 0:
            return "No"
        else:
            u += v

    neg2.sort(reverse = True, 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:
import sys
from operator import itemgetter

def solve():
    input = sys.stdin.readline
    N = int(input())
    Left = []
    lB = None
    rB = None
    for _ in range(N):
        S = input().strip("\n")
        M = len(S)
        aL, aR = 0, 0
        #自身より左にある"("
        r = 0
        for i in range(M):
            if S[i] == ")":
                if r == 0: aL += 1
                else: r -= 1
            else: r += 1
        aR = r
        if aL == 0: 
            if lB == None: lB = (aL, aR)
            elif aR > lB[1]:
                Left.append(lB)
                lB = (aL, aR)
            else: Left.append((aL, aR))
        elif aR == 0: 
            if rB == None: rB = (aL, aR)
            elif aL > rB[0]:
                Left.append(rB)
                rB = (aL, aR)
            else: Left.append((aL, aR))
        else: Left.append((aL, aR))
    Left.sort(key = itemgetter(1), reverse = True)
    Left.sort(key = itemgetter(0))
    
    #print(Left)
    rightOver = 0
    if lB != None: rightOver += lB[1]
    for i in range(len(Left)):
        rightOver -= Left[i][0]
        if rightOver < 0:
            print("No")
            break
        rightOver += Left[i][1]
    else:
        if rB != None:
            rightOver -= rB[0]
            if rightOver != 0: print("No")
            else: print("Yes")
        else:
            if rightOver == 0: print("Yes")
            else: print("No")

    return  0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
from sys import stdin
input=lambda : stdin.readline().strip()
from math import ceil,sqrt,factorial,gcd
n=int(input())
l=[]
for i in range(n):
	s=input()
	stack=[]
	for i in range(len(s)):
		if s[i]=='(':
			stack.append('(')
		else:
			if len(stack)>0 and stack[-1]=='(':
				stack.pop()
			else:
				stack.append(')')
	if len(stack)>0:
		l.append(''.join(stack))
if len(l)==0:
	print('Yes')
else:
	l.sort()
	stack=[]
	for s in l:
		for i in range(len(s)):
			if s[i]=='(':
				stack.append('(')
			else:
				if len(stack)>0 and stack[-1]=='(':
					stack.pop()
				else:
					stack.append(')')
	if len(stack)==0:
		print('Yes')
	else:
		print('No')

Submission status: Wrong Answer

Solution code:
import sys
n = int(input())
s = [input() for _ in range(n)]
cnts = []
mins = []
plus = []
minus = []
sm = 0
for i in range(n):
    cnt = 0
    mn = 0
    mx = 0
    for c in s[i]:
        if c == '(':
            cnt+=1
        else: cnt-=1
        mn = min(cnt, mn)
        mx = max(cnt, mx)
    cnts.append(abs(cnt))
    if cnt>0:
        plus.append(i)
        mins.append(abs(mn))
    else:
        minus.append(i)
        mins.append(abs(mx))
    sm+=cnt
if(sm != 0):
    print('No')
    sys.exit()

plus.sort(key = lambda x:mins[x])
minus.sort(key = lambda x:mins[x])
now = 0
que = []
r = 0
while r<len(plus) and mins[plus[r]]<=now:
    que.append(plus[r])
    r+=1
for i in range(len(plus)):
    if(len(que)==0):
        print('No')
        sys.exit()
    j = que.pop()
    now+=cnts[j]
    while r<len(plus) and mins[plus[r]]<=now:
        que.append(plus[r])
        r+=1

plus = minus
now = 0
que = []
r = 0
while r<len(plus) and mins[plus[r]]<=now:
    que.append(plus[r])
    r+=1
for i in range(len(plus)):
    if(len(que)==0):
        print('No')
        sys.exit()
    j = que.pop()
    now+=cnts[j]
    while r<len(plus) and mins[plus[r]]<=now:
        que.append(plus[r])
        r+=1
print('Yes')

Submission status: Wrong Answer

Solution code:
from __future__ import division, print_function
import sys
if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip

import os, sys, bisect, copy
from collections import defaultdict, Counter, deque
#from functools import lru_cache   #use @lru_cache(None)
if os.path.exists('in.txt'): sys.stdin=open('in.txt','r')
if os.path.exists('out.txt'): sys.stdout=open('out.txt', 'w')
#
def input(): return sys.stdin.readline()
def mapi(arg=0): return map(int if arg==0 else str,input().split())
#------------------------------------------------------------------

n = int(input())
a = []
mp = defaultdict(int)
for i in range(n):
    s = input().strip()
    bal = 0
    neg = 0
    for j in s:
        if bal<0 and j=="(":
            neg+=bal
        if j=="(":
            bal+=1
        else:bal-=1
    mp[neg]+=1
    mp[bal]+=1
f = 1
#print(mp)
for i in mp.keys():
    if mp[-i]!=mp[i]:
        f = 0
        break
if f:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
import sys
N = int(input())
brackets = []
def change(S):
    left = 0
    right = 0
    cnt = 0
    SUM = 0
    for i in S:
        if i == '(':
            left += 1
            SUM += 1
        else:
            if left > 0:
                left -= 1
                cnt += 1
            right += 1
            SUM += 1
            
    return (right - cnt, -1 * (SUM - right - cnt))

for _ in range(N):
    brackets.append(change(input()))

brackets.sort()

cnt = 0
for b in brackets:
    cnt -= b[0]
    if cnt < 0:
        print('No')
        sys.exit()
    cnt -= b[1]
if cnt == 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 iterate_tokens():
    for line in sys.stdin:
        for word in line.split():
            yield word

def solve(N: int):
    tokens = iterate_tokens()
    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)

        new_left_all_right = max(0, left_all - right) + left
        new_right_all_right = max(0, right - left_all) + right_all

        #print(new_left_all_right, new_right_all_right)

        new_left_all_left = max(0, right_all - left) + right
        new_right_all_left = max(0, left - right_all) + left_all

        #print(new_left_all_left, new_right_all_left)

        if new_left_all_right + new_right_all_right > new_left_all_left + new_right_all_left:
            left_all = new_left_all_left
            right_all = new_right_all_left
        else:
            left_all = new_left_all_right
            right_all = new_right_all_right
    if left_all == 0 and right_all == 0:
        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:
n = int(input())
s = ''
ss_dic = {}
dic = {}
for i in range(n):
    a = input()
    if ')' in a:
        ss_dic[i] = a
        dic[i] = a.index(')')
    else:
        s += a

for key, value in sorted(dic.items(), key=lambda x: x[1], reverse=True):
    s += ss_dic[key]
cnt = 0
flag = True
for i in range(len(s)):
    if s[i] == '(':
        cnt += 1
    else:
        cnt -= 1
    if cnt < 0:
        print('No')
        flag = False
        break
if flag and cnt == 0:
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

n = int(sys.stdin.readline().rstrip())
S = sys.stdin.read().split()

def main():
    for i in range(n):
        s = S[i]
        t = ''
        for c in s:
            if not t:
                t += c
            else:
                if t[-1] == '(' and c == ')':
                    t = t[:-1]
                else:
                    t += c
        S[i] = t
    
    res = deque(S[0])
    for s in S[1:]:
        if not s: continue
        l = len(s)
        if s[0] == ')':
            for i in range(l):
                if res and res[-1] == '(' and s[i] == ')':
                    res.pop()
                else:
                    for j in range(i, l):
                        res.append(s[j])
                    break
        else:
            for i in range(l-1, -1, -1):
                if res and res[0] == ')' and s[-1] == '(':
                    res.popleft()
                else:
                    for j in range(i, -1, -1):
                        res.appendleft(s[j])
                    break
    print('Yes' if not res else 'No')            
        
if __name__ == '__main__':
    main()

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):
        if min_acc[-1] < -cur:
            return False
        ind = bisect_left(min_acc, -cur)
        d, i = seg[ind:]
        seg[i] = identity
        cur += d
        if (d,i) == identity or cur < 0:
            return False
    return cur == 0

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

Submission status: Wrong Answer

Solution code:
n = int(input())

s_list = []
for _ in range(n):
    s = input()
    l = len(s)
    score = 0
    for i in range(l):
        score += (l - i) * (1 if s[i] == "(" else -1)
    s_list.append((score, s))
s_list.sort(reverse=True)

ans = "Yes"
temp = 0
for _, s in s_list:
    for c in s:
        if c == "(":
            temp += 1
        else:
            temp -= 1
            if temp < 0:
                break
if temp != 0:
    ans = "No"
print(ans)

Submission status: Wrong Answer

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

def solve():
    from collections import Counter
    zo = []
    zc = []
    co = Counter()
    cc = Counter()
    for i,s in enumerate(S):
        op = 0
        for c in s:
            if c=='(':
                op += 1
            else:
                if op: op -= 1
        cl = 0
        for c in s[::-1]:
            if c==')':
                cl += 1
            else:
                if cl: cl -= 1
        if op==0:
            zo.append(i)
        if cl==0:
            zc.append(i)
        co[op] += 1
        cc[cl] += 1

    if co != cc :
        print('No')
    else:
        if len(zo)==0 or len(zc)==0:
            print('No')
        elif len(zo) >= 2 or len(zc) >= 2:
            print('Yes')
        else:
            assert len(zo)==1 and len(zc)==1
            print('Yes' if zo[0] != zc[0] else 'No')
solve()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

def main():  
    N = int(input())
    flag1 = False
    flag2 = False
    left = 0
    right = 0
    for _ in range(N):
        s = input()
        stack = ['-']
        for t in s:
            if t == '(':
                stack.append(t)
            else:
                if stack[-1] == '(':
                    stack.pop()
                else:
                    stack.append(')')
        if len(stack) == 1:
            continue
        elif stack[1] == '(':
            flag1 = True
            left += len(stack) - 1
        elif len(stack) >= 3  and stack[1] == ')' and stack[-1] == '(':
            for i in range(len(stack)):
                if stack[i] == '(':
                    s = i
                    break
            left += len(stack) - s
            right += s - 1
        else:
            flag2 = True
            right += len(stack) - 1
    if (right == left == 0) or (flag1 and flag2 and right == left):
        print('Yes')
    else:
        print('No') 
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
data = []
le,ri = 0,0
for i in range(n):
    s = input()
    left,right = 0,0 #left (
    for j in s:
        if j == "(":
            left += 1
        else:
            if left > 0:
                left -= 1
            else:
                right += 1
    le += left
    ri += right
    data.append([left,right])

if le != ri: #閉じない
    print("No")
    exit()
if le == ri == 0: #全部それぞれで完結
    print("Yes")
    exit()

check1,check2,check3 = False,False,True
data.sort(key=lambda z:z[1])
now = 0
for x,y in data:
    if x > 0 and y == 0:
        check1 = True
    if x == 0 and y > 0:
        check2 = True
    now -= y
    if now < 0:
        check3 = False
        break
    now += x
print("Yes" if check1 and check2 and check3 else "No")

Submission status: Wrong Answer

Solution code:
class SegTree:
    def __init__(self, init_val, ide_ele, segfunc):
        self.n = len(init_val)
        self.num =2**(self.n-1).bit_length()
        self.ide_ele = ide_ele
        self.seg = [[self.ide_ele, i] for i in range (2*self.num)]
        self.segfunc = segfunc
        
        #set_val
        for i in range(self.n):
            self.seg[i+self.num-1] = init_val[i]    
        #built
        for i in range(self.num-2,-1,-1) :
            self.seg[i] = segfunc(self.seg[2*i+1], self.seg[2*i+2]) 
    
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k+1:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])
    
    def query(self, p, q):
        if q<=p:
            return self.ide_ele,0
        p += self.num-1
        q += self.num-2
        res = [self.ide_ele, self.ide_ele] 
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res

def Int():
    return int(input())
def Ints():
    return map(int,input().split())
def IntList():
    return list(Ints())
def IntMat(N):
    return [IntList() for i in range(N)]

import sys
sys.setrecursionlimit(4100000)
rl = sys.stdin.readline

N = Int()
Sum = 0

A = []

for i in range(N):
    s = input()
    now = 0
    minimum = 0
    for j in s:
        if j=='(':
            now += 1
        else:
            now -= 1
        minimum = min(minimum,now)
    Sum += now
    A.append([minimum,now])

#print(A)
A.sort()
Min = []
Now = []
c = 0
for (i,j) in A:
    Min.append(i)
    Now.append([j,c])
    c += 1
    
if Sum!=0:
    print('No')
    sys.exit()

INF = 10**15
ide_ele = -INF
Seg = SegTree(Now,ide_ele,max)

import bisect

count = 0
now = 0

#print(Min)
#print(Now)

while count < N:
    i = bisect.bisect_left(Min,-now)
    #print(i,N)
    j,k = Seg.query(i, N)
    
    #print(j)
    now += j
    Seg.update(k,[-INF,k])
    
    if now<0:
        print('No')
        sys.exit()
    count += 1
    
print('Yes')

Submission status: Wrong Answer

Solution code:
N, = map(int, input().split())
X = []
for _ in range(N):
    s = input().strip()
    a, b = 0, 0
    for c in s:
        if c == "(":
            a += 1
        else:
            if a > 0:
                a -= 1
            else:
                b += 1
    X.append((a, b))
X.sort(key=lambda x:x[0]-x[1])
s = 0
stack = []
while X:
    a, b = X.pop()
    if b > s:
        stack.append((a, b))
        continue
    s += a-b
    while stack:
        a, b = stack[-1]
        if b <= s:
            s += a-b
            stack.pop()
            continue
        break
while stack:
    a, b = stack[-1]
    if b <= s:
        s += a-b
        stack.pop()
        continue
    break
if len(stack) > 0 or s != 0:
    print("No")
else:
    print("Yes")

Submission status: Wrong Answer

Solution code:
import sys
from operator import itemgetter

def solve():
    input = sys.stdin.readline
    N = int(input())
    Left = []
    lB = None
    rB = None
    for _ in range(N):
        S = input().strip("\n")
        M = len(S)
        aL, aR = 0, 0
        #自身より左にある"("
        r = 0
        for i in range(M):
            if S[i] == ")":
                if r == 0: aL += 1
                else: r -= 1
            else: r += 1
        aR = r
        if aL == 0: 
            if lB == None: lB = (aL, aR)
            elif aR > lB[1]:
                Left.append(lB)
                lB = (aL, aR)
        elif aR == 0: 
            if rB == None: rB = (aL, aR)
            elif aL > rB[0]:
                Left.append(rB)
                rB = (aL, aR)
        else: Left.append((aL, aR))
    Left.sort(key = itemgetter(1), reverse = True)
    Left.sort(key = itemgetter(0))
    
    #print(Left)
    rightOver = 0
    if lB != None: rightOver += lB[1]
    for i in range(len(Left)):
        rightOver -= Left[i][0]
        if rightOver < 0:
            print("No")
            break
        rightOver += Left[i][1]
    else:
        if rB != None:
            rightOver -= rB[0]
            if rightOver != 0: print("No")
            else: print("Yes")
        else:
            if rightOver == 0: print("Yes")
            else: print("No")

    return  0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
import sys
n = int(input())
s = [input() for _ in range(n)]
cnts = []
mins = []
plus = []
minus = []
sm = 0
for i in range(n):
    cnt = 0
    mn = 0
    mx = 0
    for c in s[i]:
        if c == '(':
            cnt+=1
        else: cnt-=1
        mn = min(cnt, mn)
        mx = max(cnt, mx)
    cnts.append(abs(cnt))
    if cnt>0:
        plus.append(i)
        mins.append(-mn)
    else:
        minus.append(i)
        mins.append(mx)
    sm+=cnt
if(sm != 0):
    print('No')
    sys.exit()

plus.sort(key = lambda x:mins[x])
minus.sort(key = lambda x:mins[x])
now = 0
que = []
r = 0
while r<len(plus) and mins[plus[r]]<=now:
    que.append(plus[r])
    r+=1
for i in range(len(plus)):
    if(len(que)==0):
        print('No')
        sys.exit()
    j = que.pop()
    now+=cnts[j]
    while r<len(plus) and mins[plus[r]]<=now:
        que.append(plus[r])
        r+=1

plus = minus
now = 0
que = []
r = 0
while r<len(plus) and mins[plus[r]]<=now:
    que.append(plus[r])
    r+=1
for i in range(len(plus)):
    if(len(que)==0):
        print('No')
        sys.exit()
    j = que.pop()
    now+=cnts[j]
    while r<len(plus) and mins[plus[r]]<=now:
        que.append(plus[r])
        r+=1
print('Yes')

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    Ss = [input() for _ in range(n)]
    for i in range(n):
        x = 0
        l = len(Ss[i])
        while x < l-1:
            if Ss[i][x] == "(" and Ss[i][x+1] == ")":
                Ss[i] = Ss[i][:x] + Ss[i][x+2:]
                x -= 2
            x += 1
            l = len(Ss[i])
#    for i in range(n):
#        print(Ss[i])
    Ts = []
    for i in range(n):
        if len(Ss[i]) > 0:
            Ts.append(Ss[i])
    m = len(Ts)
#    for i in range(m):
#        print(Ts[i])
    if m == 0:
        print("Yes")
    else:
        U = [[0, 0] for _ in range(m)]
        for i in range(m):
            for c in Ts[i]:
                if c == "(":
                    U[i][1] += 1
                else:
                    U[i][0] += 1
#        print(U)
        R, L = 0, 0
        P = 0
        for i in range(m):
            if U[i][0] == 0:
                R += U[i][1]
            elif U[i][1] == 0:
                L += U[i][0]
            else:
                P += U[i][1] - U[i][0]
        if R + P == L and (R > 0 or L > 0):
            print("Yes")
        else:
            print("No")


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
s = []
for i in range(n):
    temp = input()
    count = 0
    min_count = 0
    for j in temp:
        if j == "(":
            count += 1
        else:
            count -= 1
            min_count = min(min_count, count)
    s.append([count, min_count])
sum_count = sum([s[i][0] for i in range(n)])
if sum_count != 0:
    print("No")
else:
    s2 = [s[i] for i in range(n) if s[i][0] > 0]
    s3 = [s[i] for i in range(n) if s[i][0] <= 0]
    s2.sort(key = lambda x: x[1], reverse = True)
    s3.sort(key = lambda x: x[1], reverse = True)
    flag = True
    count = 0
    for i in range(len(s2)):
        if count + s2[i][1] < 0:
            flag = False
            break
        else:
            count += s2[i][0]
    for i in range(len(s3)):
        if count + s3[i][1] < 0:
            flag = False
            break
        else:
            count += s3[i][0]
    if flag == True:
        print("Yes")
    else:
        print("No")

Submission status: Wrong Answer

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

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

def calc(S):
    now = 0
    ret = 0
    for s in S:
        if s == '(':
            now += 1
        else:
            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:
N = int(input())

S = [input() for _ in range(N)]
for i in range(N):
    while S[i] != S[i].replace("()",""):
        S[i] = S[i].replace("()","")
ls = [[0,0] for _ in range(N)]
for i in range(N):
    for s in S[i]:
        if s == "(":
            ls[i][0] += 1
        if s == ")":
            ls[i][1] += 1

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

if ls[0][1] > 0 or ls[-1][0] > 0:
    print('No')
    exit()
else:
    sum = 0
    for i in range(len(ls)-1):
        sum += ls[i][0]-ls[i+1][1]
        if sum < 0:
            print('No')
            exit()
    if sum == 0:
        print("Yes")
    else:
        print("No")

Submission status: Wrong Answer

Solution code:
n,*s=open(0)
n=int(n)
f=g=h=a=b=m=0
for t in s:
    c=l=r=d=0
    for u in t[:-1]:
        if u=='(':
            if d<0:d=0
            d+=1
            r+=1
        else:
            d-=1
            if d>=0:c+=1
            l+=1
        m+=1
    x=r-c
    y=l-c
    if x==y==0:h+=1
    elif x==0:f=1
    elif y==0:g=1
    a+=x
    b+=y
if (f and g or h and (f or g) or h > 1) and a==b and a+b<m:
    print('Yes')
else:
    print('No')