Problem:


Score : 600 points

Problem Statement

A bracket sequence is a string that is one of the following:

An empty string;

The concatenation of (, A, and ) in this order, for some bracket sequence A ;

The concatenation of A and B in this order, for some non-empty bracket sequences A and B /

Given are N strings S_i. Can a bracket sequence be formed by concatenating all the N strings in some order?

Constraints

1 \leq N \leq 10^6

The total length of the strings S_i is at most 10^6.

S_i is a non-empty string consisting of ( and ).

Input

Input is given from Standard Input in the following format:

N
S_1
:
S_N

Output

If a bracket sequence can be formed by concatenating all the N strings in some order, print Yes; otherwise, print No.

Sample Input 1

2
)
(()

Sample Output 1

Yes

Concatenating (() and ) in this order forms a bracket sequence.

Sample Input 2

2
)(
()

Sample Output 2

No

Sample Input 3

4
((()))
((((((
))))))
()()()

Sample Output 3

Yes

Sample Input 4

3
(((
)
)

Sample Output 4

No



Sample input:
2
)
(()


Sample output:
Yes

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# vim: set fileencoding=utf-8

# pylint: disable=unused-import, invalid-name, missing-docstring, bad-continuation


"""Module docstring
"""

import functools
import heapq
import itertools
import logging
import math
import random
import string
import sys
from argparse import ArgumentParser
from collections import defaultdict, deque
from copy import deepcopy
from typing import Dict, List, Optional, Set, Tuple


def solve(values: List[str]) -> bool:
    counts = defaultdict(int)
    total_closing = 0
    total_opening = 0
    for v in values:
        opening = 0
        closing = 0
        for c in v:
            if c == ")":
                if opening == 0:
                    closing += 1
                else:
                    opening -= 1
            if c == "(":
                opening += 1
        if closing + opening != 0:
            if (opening, closing) in counts:
                counts[(opening, closing)] -= 1
            else:
                counts[(closing, opening)] += 1
        total_opening += opening
        total_closing += closing
    LOG.debug((counts))
    LOG.debug((total_opening, total_closing))
    if sum(counts.values()) == 0:
        return True
    for closing, opening in counts:
        if closing == total_closing - opening and opening == total_opening - closing:
            return True
    # for (opening, closing), nb in counts.items():
    return False


def do_job():
    "Do the work"
    LOG.debug("Start working")
    # first line is number of test cases
    N = int(input())
    values = []
    for _ in range(N):
        values.append(input().strip())
    result = solve(values)
    print("Yes" if result else "No")


def print_output(testcase: int, result) -> None:
    "Formats and print result"
    if result is None:
        result = "IMPOSSIBLE"
    print("Case #{}: {}".format(testcase + 1, result))
    # 6 digits float precision {:.6f} (6 is the default value)
    # print("Case #{}: {:f}".format(testcase + 1, result))


def configure_log() -> None:
    "Configure the log output"
    log_formatter = logging.Formatter("%(lineno)d - " "%(message)s")
    handler = logging.StreamHandler(sys.stdout)
    handler.setFormatter(log_formatter)
    LOG.addHandler(handler)


LOG = None
# for interactive call: do not add multiple times the handler
if not LOG:
    LOG = logging.getLogger("template")
    configure_log()


def main(argv=None):
    "Program wrapper."
    if argv is None:
        argv = sys.argv[1:]
    parser = ArgumentParser()
    parser.add_argument(
        "-v",
        "--verbose",
        dest="verbose",
        action="store_true",
        default=False,
        help="run as verbose mode",
    )
    args = parser.parse_args(argv)
    if args.verbose:
        LOG.setLevel(logging.DEBUG)
    do_job()
    return 0


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    sys.exit(main())


class memoized:
    """Decorator that caches a function's return value each time it is called.
    If called later with the same arguments, the cached value is returned, and
    not re-evaluated.
    """

    def __init__(self, func):
        self.func = func
        self.cache = {}

    def __call__(self, *args):
        try:
            return self.cache[args]
        except KeyError:
            value = self.func(*args)
            self.cache[args] = value
            return value
        except TypeError:
            # uncachable -- for instance, passing a list as an argument.
            # Better to not cache than to blow up entirely.
            return self.func(*args)

    def __repr__(self):
        """Return the function's docstring."""
        return self.func.__doc__

    def __get__(self, obj, objtype):
        """Support instance methods."""
        return functools.partial(self.__call__, obj)

Submission status: Wrong Answer

Solution code:
N = int(input())

S = [input() for i in range(N)]

T = []

for i in range(N):
    count1 = 0
    count2 = 0
    count = 0
    for j in range(len(S[i])):
        if S[i][j]=="(":
            count += 1
        else:
            count -= 1
        count1 = max(count1,-count)
    count = 0
    for j in range(len(S[i])):
        if S[i][len(S[i])-j-1]=="(":
            count += 1
        else:
            count -= 1
        count2 = max(count2,count)

    T.append((count1,count2))
flag1 = False
flag2 = False
count0 = 0
for i in range(N):
    if T[i][0]==0 and T[i][1]==0:
        count0 += 1
    elif T[i][0]==0 and T[i][1]!=0:
        flag1 = True
    elif T[i][0]!=0 and T[i][1]==0:
        flag2 = True

if (flag1 and flag2) or count0>=2 or (flag1 and count0==1) or (flag2 and count0==1):
    count1=0
    count2=0
    for i in range(N):
        count1 += T[i][0]
        count2 += T[i][1]
    if count1==count2:
        print("Yes")
    else:
        print("No")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
import heapq
import sys
input = sys.stdin.readline
n = int(input())
sss = [input()[:-1] for _ in range(n)]

a = []
b = []
ss = 0
ii = 0
for i in sss:
    mi = 0
    ma = 0
    s = 0
    for j in i:
        if j == "(":
            s += 1
        else:
            s -= 1
        mi = min(mi, s)
        ma = max(ma, s)
    ss += s
    if s >= 0:
        a.append([-s, mi, ma, ii])
    else:
        b.append([s, mi - s, ma - s, ii])
    ii += 1


if ss != 0:
    print("No")
    exit()
a.sort(reverse=1, key=lambda x: x[1])
b.sort(reverse=1, key=lambda x: x[1])


def ok1(a):
    s = 0
    heap = []
    i = 0
    while True:
        while i < len(a) and a[i][1] + s >= 0:
            heapq.heappush(heap, a[i])
            i += 1
        if i < len(a) and not heap:
            print("No")
            exit()
        if not heap:
            break
        s += heapq.heappop(heap)[0]


def ok(a):
    s = 0
    heap = []
    i = 0
    while True:
        while i < len(a) and a[i][1] + s >= 0:
            heapq.heappush(heap, a[i])
            i += 1
        if i < len(a) and not heap:
            print("No")
            exit()
        if not heap:
            break
        s += heapq.heappop(heap)[0]

ok1(a)
ok(b)
print("Yes")

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[0], x[1]), reverse=True)
    #print(tmp)

    cur = 0
    idx = 0
    q = []
    count = 0
    while count < N:
        while idx < N and cur + tmp[idx][0] >= 0:
            heapq.heappush(q, (-tmp[idx][1], -tmp[idx][0]))
            idx += 1
        if len(q) == 0:
            print(NO)
            return
        #print(count, q)
        cnt, mn = heapq.heappop(q)
        cnt, mn = -cnt, -mn
        #print(cnt, mn)
        if cur + mn < 0:
            print(NO)
            return
        cur += cnt
        count += 1

    #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())
s = [list(input()) for _ in range(n)]

bs = []
for si in s:
    li, ri = 0, 0
    for c in si:
        if c == '(':
            li += 1
        elif c == ')' and li == 0:
            ri += 1
        elif c == ')' and 0 < li:
            li -= 1
    bs.append((ri - li, li, ri))

bs.sort()
bra = 0
ans = "Yes"
for (d, li, ri) in bs:
    bra -= ri
    if bra < 0:
        ans = "No"
        break
    bra += li
if bra != 0:
    ans = "No"
print(ans)

Submission status: Wrong Answer

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

def brancket(s):
    ans = [0, 0]
    l, r = 0, 0
    for i in s:
        if i == ')':
            if r == 0:
                ans[0] += 1
            else:
                r -= 1
        if i == '(':
            r += 1
    ans[1] = r
    return ans

L, R, tl, tr = 0, 0, False, False
for i in S:
    if (a := brancket(i)) != [0, 0]:
        if a[0] == 0:
            tl = True
        if a[1] == 0:
            tr = True
    L += a[0]
    R += a[1]

print('Yes' if tl and tr and L == R else 'No')

Submission status: Wrong Answer

Solution code:
N = int(input())

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

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

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

Submission status: Wrong Answer

Solution code:
#かっこ列とは…( = +1 ) = -1「途中でマイナスにならない」
N = int(input())
AllMinPlus = []
AllMinMinus = []
for n in range(N):
    S = input()
    minkakko = 10000000
    cur = 0
    for s in S:
        if s == "(":
            cur += 1
        else:
            cur -= 1
        minkakko = min(minkakko,cur)
    if cur >= 0:
        AllMinPlus.append((cur,minkakko))
    else:
        AllMinMinus.append((cur,minkakko))
AllMinPlus.sort(key = lambda x:x[1],reverse=True)
AllMinMinus.sort(key = lambda x:x[1])
AllMin = AllMinPlus + AllMinMinus
if sum([x[0] for x in AllMin]) == 0:
    pos = 0
    for a,m in AllMin:
        if pos < -m:
            print("No")
            exit()
        pos += a
        if pos < 0:
            print("No")
            exit()        
    #プラス組のなかでMinが大きい順に積んでいく
    #マイナス組のなかでMinが小さい順に積んでいく
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
import sys
import heapq
hpush = heapq.heappush
hpop = heapq.heappop
input = sys.stdin.readline
N = int(input())
ls = [0] * N
rs = [0] * N
h = []
base = 10 ** 7
for x in range(N):
  S = list(input())[: -1]
  for i in range(len(S)):
    if S[i] == "(": rs[x] += 1
    if S[i] == ")":
      if rs[x]: rs[x] -= 1
      else: ls[x] += 1
  hpush(h, ls[x] * base - rs[x])
if sum(ls) != sum(rs):
  print("No")
  exit(0)
if sum(ls) == 0:
  print("Yes")
  exit(0)
l = 0
r = 0
for i in range(N):
  if ls[i] == 0 and (rs[i] > 0): l = 1
  if rs[i] == 0 and (ls[i] > 0): r = 1
if l & r == 0:
  print("No")
  exit(0)

#print(h)
l = 0
while len(h):
  t = hpop(h)
  x = max(0, t // base)
  y = -t % base
  if l < x:
    print("No")
    exit(0)
  l += y - x
  #print(l)

print("Yes")

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:
#code
N=int(input())
if(N==1):
    s=input()
    mini=+len(s)
    temp=0
    cnt1=0
    cnt2=0
    for i in range(len(s)):
        if(s[i]=='('):
            temp+=1
            cnt1+=1
        else:
            temp-=1
            cnt2+=1
        mini=min(mini,temp)
    if(mini>=0 and cnt1==cnt2):
        print("Yes")
    else:
        print("No")
else:    
    cnt1=0
    cnt2=0
    start=False
    end=False
    for i in range(N):
        s=input()
        for j in range(len(s)):
            if(s[j]=='('):cnt1+=1
            else:cnt2+=1
        if(s[0]=='(' and start==False):start=True
        elif(s[-1]==')' and end==False):
            end=True
    else:
        print("No")

Submission status: Wrong Answer

Solution code:
N = int(input())

S_list = []
for _ in range(N):
	S_list.append(input().strip())

data = []
for s in S_list:
	bottom = 0
	height = 0
	for c in s:
		if c == ")":
			height -= 1
			if bottom > height:
				bottom = height
		else:
			height += 1
	data.append((bottom, height, s))

data.sort()
data.reverse()

def check():
	height = 0
	for b, h, s in data:
#		print(b, h, s)
		if height + b < 0:
			return False
		height += h
	return height == 0

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

Submission status: Wrong Answer

Solution code:
def count(s):
    ret = 0
    max_down = 0
    for c in s:
        if c=="(": ret += 1
        else: ret -= 1
        max_down = min(max_down,ret)
    return max_down, ret

n = int(input())
s_count_plus = []
s_count_minus = []
for i in range(n):
    si = input()
    down, num = count(si)
    if down ==0:
        s_count_plus.append(num)
    else:
        s_count_minus.append((-down,num))

s_count_minus.sort(reverse=True)

ans = "No"
count_sum = sum(s_count_plus)
for down, num in s_count_minus:
    if count_sum < down: break
    count_sum += num
else:
    if count_sum == 0: ans = "Yes"

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

def l_in():
    return list(map(int, input().split()))

n=n_in()

base=[]

for _ in range(n):
    s = s_in()

    c = s[0]
    cnt = 1
    ar = []
    for t in range(1,len(s)):
        if s[t-1] == s[t]:
            cnt += 1
        else:
            ar.append((c,cnt))
            c = s[t]
            cnt = 1
    ar.append((c,cnt))

    start = 0
    if ar[0][0] == ")":
        start = 1

    r = 0 # ( の数
    sgn = 1
    for c,cnt in ar[start:]:
        r += sgn*cnt
        sgn *= -1


    res = ()
    if ar[0][0] == ")":
        if r >= 0:
            res = (ar[0][1], r)
        else:
            res = (ar[0][1]-r,0)
    else:
        if r >= 0:
            res = (0, r)
        else:
            res = (r, 0)

    base.append(res)

i_cnt = 0
j_cnt = 0

base2 = []

for i,j in base:
    i_cnt += i
    j_cnt += j

    if j > 0:
        base2.append((i,-(j-i),j))

if i_cnt != j_cnt:
    print("No")
    exit()

base2.sort()

current = 0

for i,p,j in base2:
    if current < i:
        print("No")
        exit()
    current -= i
    current += j

print("Yes")

Submission status: Wrong Answer

Solution code:
def do(s):
    l, r = 0, 0
    for i in range(len(s)):
        if s[i] == "(":
            r += 1
        elif s[i] == ")":
            if r > 0:
                r -= 1
            else:
                l += 1
    #print(s, l, r)
    return (l,r)

n = int(input())
dat = []

suml, sumr = 0, 0
for i in range(n):
    s = input()
    l ,r = do(s)
    if l != 0 or r != 0:
        dat.append( [l,r] )

curl, curr = 0, 0
for i in range(len(dat)):
    newl , newr = dat[i]
    caneraseL = min(curl, newr)
    caneraseR = min(curr, newl)
    if caneraseL == caneraseR:
        if curl > curr: # Lを消したい = newは左につける
            # 左につける ver00
            if curl >  newr: # いまのLの方が多いなら
                curl, curr = newl + (curl - newr), curr
            else:
                curl, curr = newl, curr + (newr - curl)
        else: # Rを消す = newは右につける
            # 右につける ver00
            if curr >  newl: # いまのRの方が多いなら
                curl, curr = curl, newr + (curr - newl)
            else:
                curl, curr = curl + (newl - curr), newr
    elif caneraseR > caneraseL:
        # 右につける ver00
        if curr > newl:  # いまのRの方が多いなら
            curl, curr = curl, newr + (curr - newl)
        else:
            curl, curr = curl + (newl - curr), newr
    else: # caneraseR < caneraseL
        # 左につける ver00
        if curl > newr:  # いまのLの方が多いなら
            curl, curr = newl + (curl - newr), curr
        else:
            curl, curr = newl, curr + (newr - curl)
#print(curl,curr)
print("Yes" if curl == curr == 0else "No")

Submission status: Wrong Answer

Solution code:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()
N=int(input())
S=[input() for i in range(N)]
lr=[]
for n in range(N):
    l=0
    r=0
    for i in range(len(S[n])):
        if S[n][i]=="(":
            l+=1
        else:
            if l>0:
                l-=1
            else:
                r+=1
    #print(l,r)
    if l or r:
        lr.append([l,r])
lr.sort(key=lambda x:x[0]*x[1],reverse=True)
idleR=10**7
lsum=0
rsum=0
for l,r in lr:
    lsum+=l
    rsum+=r
#print(lr)
if lr:
    L,R=lr[0]
    stack=[[L,R]]
    for n in range(1,len(lr)):
        #print(stack)
        L,R=lr[n]
        visited=set()
        nstack=[]
        while stack:
            l,r=stack.pop()
            for xl,xr in [[l+L-R,r],[l,r+R-L]]:
                #if xl>=0 and xr>=0:
                    X=xl+idleR*xr
                    if not X in visited:
                        visited.add(X)
                        nstack.append([xl,xr])


        stack=nstack
    #print(stack)
    if not stack or [0,0] in stack:
        print("Yes")
    else:
        print("No")
else:
    print("Yes")

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((left, right))
    elif left == 0 and right > 0:
        R += right
    elif left > 0 and right == 0:
        L += left
for ml, mr in M:
    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:
import math
import fractions
#import sys
#input = sys.stdin.readline

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

def ValueToBits(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

def BitsToValue(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        ans+= arr[i] * 2**i
    return ans

def ZipArray(a):
    aa = [[a[i],i]for i in range(n)]

    aa.sort(key = lambda x : x[0])
    for i in range(n):
        aa[i][0]=i+1
    aa.sort(key = lambda x : x[1])
    b=[aa[i][0] for i in range(len(a))]
    return b

def ValueToArray10(x, digit):
    ans = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        ans[digit-i-1] = now%10
        now = now //10
    return ans

def Zeros(a,b):
    if(b<=-1):
        return [0 for i in range(a)]
    else:
        return [[0 for i in range(b)] for i in range(a)]

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
            
'''
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 2
N = 10 ** 6 + 2
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

'''

#a = list(map(int, input().split()))

#################################################
#################################################
#################################################
#################################################



n = int(input())

lr = []

for i in range(n):
    s = input()
    m = len(s)
    #exam left
    count = 0
    left = 0
    for j in range(m):
        if(s[j]=='('):
            count += 1
        else:
            if(count == 0):
                left+=1
            else:
                count -=1
    #exam right
    count = 0
    right = 0
    for j in range(m):
        if(s[m-j-1]==')'):
            count += 1
        else:
            if(count == 0):
                right+=1
            else:
                count -=1

    #print(left,right)
    lr.append([left,right])

existL = 0
existR = 0
sumL = 0
sumR = 0
for i in range(n):
    sumL += lr[i][0]
    sumR += lr[i][1]
    if(lr[i][0]==0 and lr[i][1]!=0):
        existL=1
        #print(lr[i])
    if(lr[i][1]==0 and lr[i][0]!=0):
        existR=1
        #print(lr[i])

#print(lr,existL,existR)
print("No")
exit()
if(existL*existR == 1 and sumL == sumR):
    print("Yes")
else:
    if(sumL==0 and sumR==0):
        print("Yes")
    else:
        print("No")

Submission status: Wrong Answer

Solution code:
#かっこ列とは…( = +1 ) = -1「途中でマイナスにならない」
N = int(input())
AllMinPlus = []
AllMinMinus = []
for n in range(N):
    S = input()
    minkakko = 10000000
    cur = 0
    for s in S:
        if s == "(":
            cur += 1
        else:
            cur -= 1
        minkakko = min(minkakko,cur)
    if cur >= 0:
        AllMinPlus.append((cur,minkakko))
    else:
        AllMinMinus.append((cur,minkakko))
AllMinPlus.sort(key = lambda x:x[1],reverse=True)
AllMinMinus.sort(key = lambda x:x[1])
AllMin = AllMinPlus + AllMinMinus
print(AllMin)
if sum([x[0] for x in AllMin]) == 0:
    pos = 0
    for a,m in AllMin:
        if pos < -m:
            print("No")
            exit()
        pos += a
        if pos < 0:
            print("No")
            exit()        
    #プラス組のなかでMinが大きい順に積んでいく
    #マイナス組のなかでMinが小さい順に積んでいく
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
n = int(input())
s = [input() for _ in range(n)]

l = 0
r = 0
m = []


def fin():
    print("No")
    exit()


for word in s:
    stack = []
    for e in word:
        if stack and stack[-1] == "(" and e == ")":
            stack.pop()
        else:
            stack.append(e)

    if stack:
        if stack[0] == ")" and stack[-1] == "(":
            m.append(stack)
        elif stack[0] == ")":
            r += len(stack)
        else:
            l += len(stack)

ml = []
mm = 0
mr = []

for word in m:
    ll = word.index("(")
    rr = len(word) - ll
    if ll > rr:
        mr.append([ll, rr])
    elif ll < rr:
        ml.append([ll, rr])
    else:
        mm = max(mm, ll)

ml.sort()
for ll, rr in ml:
    l -= ll

    if l < 0:
        fin()

    l += rr

mr.sort(key=lambda x: x[1])
for ll, rr in ml:
    r -= rr

    if r < 0:
        fin()

    r += ll

if mm <= l or mm <= r:
    if l == r:
        print("Yes")
        exit()

fin()

Submission status: Wrong Answer

Solution code:
n = int(input())

a = []
b = []
for i in range(n):
    s = input()
    x = 0
    y = 0
    for c in s:
        if c == '(':
            y += 1
        else:
            if y >= 1:
                y -= 1
            else:
                x += 1
    if x < y: a.append([x, y])
    if x > y: b.append([y, x])

def calc(a):
    ret = 0
    for x, y in sorted(a):
        if ret < x: return -1
        ret += y-x
    return ret
   
res1 = calc(a)
res2 = calc(b)
print("Yes" if res1 >= 0 and res1 == res2 else "No")

Submission status: Wrong Answer

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

n = int(input())
s = [input().rstrip() for _ in range(n)]
s_cnt = []
for i in range(n):
    s_ = list(s[i])
    left = 0
    right = 0
    for j in s_:
        if j == ")":
            if left >= 1:
                left -= 1
            else:
                right += 1
        else:
            left += 1
    s_cnt.append([left, right])
left = 0
right = 0
for i in s_cnt:
    left += i[0]
    right += i[1]
if left == right:
    print("Yes")
else:
    print("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
        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:
def matched(str):
    count = 0
    for i in str:
        if i == "(":
            count += 1
        elif i == ")":
            count -= 1
        if count < 0:
            return False
    return count == 0


n = int(input())
string = ""
for ele in range(n):
    string += input()


if matched(string):
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
def kton(S):
    r = 0
    m = 0
    for s in S:
        r += 1 if s == '(' else -1
        m = min(m, r)
    return r, m
        
def main():
    N = int(input())
    RM = [kton(input()) for _ in range(N)]
    pos = 0
    negp = []
    negn = []
    posn = []
    for r, m in RM:
        if m < 0:
            if r >= 0:
                negp.append((-m, r))
            else:
                negn.append((-r, -m))
        else:
            pos += r

    negp.sort()
    for m, r in negp:
        if pos - m < 0:
            return False
        pos += r
    negn.sort()
    for r, m in negn:
        if pos - m < 0:
            return False
        pos -= r
    return pos == 0

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

Submission status: Wrong Answer

Solution code:
from operator import itemgetter
N=int(input())
S=[input() for _ in range(N)]

if N==1:
  s=S[0]
  x=len(s)
  tmp=s.count('(')
  if s[0]=='(' and s[-1]==')' and tmp-(x-tmp)==0:
    print('Yes')
  else:
    print('No')
  

nums=[0]*N
soko=[0]*N
for i in range(N):
  s=S[i]
  x=len(s)
  c=0
  for j in range(x):
    if s[j]=='(':
      c+=1
    else:
      c-=1
    if c<soko[i]:
      soko[i]=c
  
  nums[i]=c
  
res=[[nums[i], soko[i], nums[i]+soko[i]] for i in range(N)]
res=sorted(res, key=itemgetter(2, 0), reverse=True)

if sum(nums)!=0:
  print('No')
  exit()
  
h=0
for i in range(N):
  if h+res[i][1]<0:
    print('No')
    exit()
  h+=res[i][0]
  if h<0:
    print('No')
    exit()
print('Yes')

Submission status: Wrong Answer

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


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

    nl = 0
    nr = 0

    buff_l = 0
    buff_r = 0

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

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

        buff_l = 0
        buff_r = 0

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


if __name__ == "__main__":
    main()