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())
A=[]
B=[]
c=0
for i in range(n):
  S=input()
  a=0
  b=0
  for j in range(len(S)):
    if S[j]=="(":
      a=a+1
    else:
      a=a-1
      if a<b:
        b=a
  if b==0:
    c=c+a
  elif a>=0:
    B.append([-1*b,-1*a])
  else:
    A.append([-1*b,a])
A.sort()
B.sort()
f=0
for i in range(len(B)):
  if c+B[i][0]<0:
    f=1
  c=c-B[i][1]
for i in range(len(A)):
  if c-A[i][0]<0:
    f=1
  c=c+A[i][1]
if c!=0:
  f=1
if f==0:
  print("Yes")
else:
  print("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)]
llst=[]
lr=[]
rlst=[]
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 and not r:
        llst.append(l)
    elif not l and r:
        rlst.append(r)
    elif l or r:
        lr.append([l,r])
llst=sum(llst)
rlst=sum(rlst)

if not llst and not rlst and not lr:
    print("Yes")
    exit()
stack=[]
idleR=10**7
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])
if not stack:
    if llst-rlst==0:
        print("Yes")
    else:
        print("No")
    exit()

for l,r in stack:
    if l<llst:
        l=0
        llst-=l
    else:
        continue
    if r<rlst:
        r=0
        rlst-=r
    else:
        continue

    if llst-rlst==0:
        print("Yes")
    else:
        print("No")
print("No")

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 filter(lambda x: x[1] <= 0 ,base2):
    if current < i:
        print("No")
        exit()
    current -= i
    current += j

base3 = []
for i,p,j in filter(lambda x: x[1] > 0 ,base2):
    base3.append((-p,i,j))

base3.sort()

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

Submission status: Wrong Answer

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


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

Submission status: Wrong Answer

Solution code:
def RunLengthEncoding(S):
    res = []
    N = len(S)
    i = 0
    while i < N:
        cnt = 1
        while i < N - 1 and S[i] == S[i + 1]:
            cnt += 1
            i += 1
        res.append([S[i], cnt])
        i += 1

    while True:
        res2 = omit(res)
        if res == res2:
            return res2
        res = res2


def omit(RLE):
    res = []
    i = 0
    while i < len(RLE):
        k, v = RLE[i]
        if k == ")":
            res.append([k, v])
            i += 1
            continue
        if i >= len(RLE) - 1:
            res.append([k, v])
            break

        kk, y = RLE[i + 1]
        if v > min(v, y):
            res.append([k, v - min(v, y)])
        if y > min(v, y):
            res.append([kk, y - min(v, y)])
        i += 2
    if res:
        res = merge(res)
    return res


def merge(RLE):
    res = []
    res.append(RLE[0])
    for i in range(1, len(RLE)):
        k, v = RLE[i]
        if res[-1][0] != k:
            res.append([k, v])
        else:
            res[-1][1] += v
    return res


if __name__ == "__main__":
    N = int(input())
    tmp = []
    for _ in range(N):
        RLE = RunLengthEncoding(input())
        if RLE:
            tmp.append(RLE)

    if not tmp:
        print("Yes")
        exit()

    outR = 0
    outL = 0
    LR = []
    for b in tmp:
        if len(b) == 1:
            k, v = b[0]
            if k == "(":
                outR += v
            else:
                outL += v
        else:
            _, v1 = b[0]
            _, v2 = b[1]
            LR.append((v1, -v2))

    LR.sort()
    for l, r in LR:
        if outR < l:
            print("No")
            exit()
        outR = outR - l - r

    if outR == outL:
        print("Yes")
    else:
        print("No")

Submission status: Wrong Answer

Solution code:
def check():
    N = int(input())
    lr = [[0,0] for _ in range(N)] #[l,r]
    for i in range(N):
        S = list(input())
        for s in S:
            if s==')': #lの処理
                if lr[i][1]<0:
                    lr[i][1]+=1 #rが受け止めてくれる
                else:
                    lr[i][0]+=1 #rが受け止めてくれない
            else: #rの処理
                lr[i][1] -= 1 #ただ増えるだけ
    lr.sort(key=lambda x: (x[0], x[1]))
    now = 0
    for l,r in lr:
        if now <l:
            return 'No'
        now -= l+r
    if now==0:
        return 'Yes'
    return 'No'
print(check())

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
si = []
for _ in range(n):
    s = input().strip()
    l = 0
    r = 0
    count = 0
    for i in range(len(s)):
        if s[i] == "(":
            count += 1
        else:
            count = max(0, count-1)
    l = count
    count = 0
    for i in range(len(s)-1, -1, -1):
        if s[i] == ")":
            count += 1
        else:
            count = max(0, count-1)
    r = count
    si.append((l, r))

if len(si) == 1:
    if si[0] == (0, 0):
        print("Yes")
        sys.exit()

index_l = -1
index_r = -1
maxi_l = 0
maxi_r = 0
for i in range(n):
    a, b = si[i]
    if a == 0:
        if maxi_l < b:
            maxi_l = b
            index_l = i
    if b == 0:
        if maxi_r < a:
            maxi_r = a
            index_r = i

if index_l == -1 or index_r == -1:
    print("No")
    sys.exit()

count = 0
if index_r < index_l:
    count += si.pop(index_l)[1]
    last = si.pop(index_r)
else:
    last = si.pop(index_r)
    count += si.pop(index_l)[1]

from heapq import *
c = [[] for i in range(10*10**5+1)]
for i, j in si:
    c[i].append(j-i)
ind = count
use = 0
q = []
for i in range(count):
    for j in c[i]:
        heappush(q, -j)
        use += 1
while q:
    now = -q.pop()
    count += now
    ind += now
    if now > 0:
        for i in range(ind-now+1, ind+1):
            for j in c[i]:
                heappush(q, -j)
                use += 1

count -= last[0]

if count == 0 and use == n-2:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

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

def count(s):
    m=0
    e=0
    for t in s:
        if t=='(':
            e+=1
        else:
            e-=1
        m=min(m,e)
    return (e,m)

def main():
    n=int(input())
    S=[input().strip() for _ in range(n)]
    C=[]
    for s in S:
        e,m=count(s)
        C.append((m,e))
    s=0
    for _,e in C:
        s+=e
    if s!=0:
        return 'No'
    C.sort()
    s=0
    hq=[]
    #print(C)
    while C:
        #print(s,C)
        while C and s+C[-1][0]>=0:
            m,e=C.pop()
            heapq.heappush(hq,-e)
        #print(hq)
        if not hq:
            return 'No1'
        e=heapq.heappop(hq)
        e*=-1
        if s+e<0:
            return 'No2'
        s+=e
    return 'Yes'
    
if __name__=='__main__':
    print(main())

Submission status: Wrong Answer

Solution code:
n = int(input())
l = []
#[c,d]c=right d=left
for i in range(n):
    s = list(input())
    c = 0
    d = 0
    for j in range(len(s)):
        if s[j] == "(":
            c += 1
        else:
            if c > 0:
                c -= 1
            else:
                d += 1
    l.append([c,d])
key = [0,0,0]
ac = 0
ad = 0
bc = 0
bd = 0
gc = 0
gd = 0
for i in range(n):
    c,d = l[i]
    if c == 0:
        if d == 0:
            key[2] += 1
        else:
            key[0] += 1
            bd += d
    else:
        if d == 0:
            key[1] += 1
            bc += c
        else:
            if gc > 0:
                if d <= gc:
                    gc -= d
                    gd += gc - d
                else:
                    gc = c
                    gd += d - gc
            else:
                gc = c
                gd = d
    ac += c
    ad += d
if ac == ad and gd+bd == bc + gc:
    if key[0] > 0 and key[1] > 0:
        print("Yes")
    else:
        print("No")
else:
    print("No")

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

n = int(input())

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

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

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

    if not s:
        return jud

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

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

    return jud

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

    print('No')
    return
main()

Submission status: Wrong Answer

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

start = False
end = False
sc = 0
ec = 0
for i, s in enumerate(ss):
    if s.startswith("("):
        start = True
    if s.endswith(")"):
        end = True
    sc = sc + s.count('(')
    ec = ec + s.count(')')
print("Yes" if sc == ec and start and end else "Bo")

Submission status: Wrong Answer

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


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

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

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

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

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

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

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

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

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

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

from operator import eq

N = int(readline())

memo = [None]*N

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

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

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

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

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

Submission status: Wrong Answer

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

INF = 2**62-1


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


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


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


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


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


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

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


def mt(f):
    import time

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

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

    return wrap


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

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

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

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

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

    return 'No'


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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
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])
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:
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:
            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())

cnt = 0
start = 0
goal = 0
kanpeki = 1
for _ in range(N):
    S = input()
    k = 0
    for i in S:
        if i == "(":
            k += 1
        else:
            k -= 1
        if k < 0:
            kanpeki = 0       
    cnt += k
    if S[0] == "(" and k > 0:
        start = 1
    if S[-1] == ")" and k < 0:
        goal = 1

if kanpeki == 1 and cnt == 0:
    print("Yes")
elif cnt == 0 and start == 1 and goal == 1:
    print("Yes")
else:
    print("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)]
llst=[]
lr=[]
rlst=[]
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 and not r:
        llst.append(l)
    elif not l and r:
        rlst.append(r)
    elif l or r:
        lr.append([l,r])
llst=sum(llst)
rlst=sum(rlst)

if not llst and not rlst and not lr:
    print("Yes")
    exit()
stack=[]
idleR=10**7
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])
if not stack:
    if llst-rlst==0:
        print("Yes")
    else:
        print("No")
    exit()

for l,r in stack:
    if l<llst:
        l=0
    else:
        continue
    if r<rlst:
        r=0
    else:
        continue

    if llst-rlst==0:
        print("Yes")
    else:
        print("No")
print("No")

Submission status: Wrong Answer

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

new_s = [0]*N
for i in range(N):
    c = S[i]
    for j in range(len(c)):
        if c[j] == "(":
            new_s[i] += 1
        elif c[j] == ")":
            new_s[i] -= 1

if sum(new_s) != 0:
    print("No")
    exit()

print("Yes")

Submission status: Wrong Answer

Solution code:
n=int(input())
import random
cnt1=0
cnt2=0
for inp in range(n):
    s=input()
    cnt1+=s.count("(")
    cnt2+=len(s)

if cnt1*2!=cnt2:
    print("No")
else:
    if random.random()>0.7:
        res="No"
    else:
        res="Yes"
    print(res)

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
    left2 = []
    right = 0
    right2 = []
    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
            left2.append(len(stack) - s)
            right2.append(s - 1)
        else:
            flag2 = True
            right += len(stack) - 1
    if (right == 0 and left == 0 and  right2 == 0 and left2 == 0):
        print('Yes')
    else:
        l = 0
        if len(left2) > 0:
            l = min(left2)
        r = 0
        if len(right2) > 0:
            r = min(right2)
        x = max(r,l)
        if flag1 and flag2 and (right + sum(right2) == left + sum(left2)) and (left >= x) and (right >= x):
            print('Yes')
        else:
            print('No')
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
x = []
for i in range(n):
    s = input()
    while "()" in s:
        s = s.replace("()", "")
    if '(' in s:
        x.append(len(s))
    elif ')' in s:
        x.append(-len(s))
x = sorted(x)
if len(x) % 2 != 0:
    print("No")
    exit()
for i in range(int(len(x)/2)):
    if x[i] != -x[len(x)-i-1]:
        print("No")
        exit()
print("Yes")

Submission status: Wrong Answer

Solution code:
n = int(input())
List = []
flg_l = []
flg_r = []
sum = 0
for i in range(n):
    s = input()
    left = 0
    tmp = 0
    for i in range(len(s)):
        if s[i] == ')':
            tmp += 1
        else:
            tmp -= 1
        left = max(left, tmp)
    right = 0
    tmp = 0
    for i in range(len(s)):
        if s[len(s)-1-i] == '(':
            tmp += 1
        else:
            tmp -= 1
        right = max(right, tmp)

    sum += right - left
    if right == 0:
        flg_r.append(i)
    if left == 0:
        flg_l.append(i)
    List.append((left, right))


if sum == 0 and len(flg_l) > 0 and len(flg_r) > 0:
    if len(flg_l) == 1 and len(flg_r) == 1 and flg_l == flg_r:
        print('No')
    else:
        print('Yes')
else:
    print('No')

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],reverse=True)
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:
# 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('Yes'); exit()

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

Submission status: Wrong Answer

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

S_mod = []
for i, s in enumerate(S):
    tmp = [0,0]
    for k in s:
        if k == ')':
            idx = 0
        else:
            idx = 1
        if idx:
            tmp[idx] += 1
        else:
            if tmp[1-idx] >= 1:
                tmp[1-idx] -= 1
            else:
                tmp[idx] += 1

    if tmp != [0, 0]:
        S_mod.append(tmp)

gap = 0
rflag = 0
lflag = 0
for s in S_mod:
    gap += s[0] - s[1]
    if s[0] == 0 and s[1] >= 1:
        rflag = 1
    if s[0] >= 1 and s[1] == 0:
        lflag = 1

if gap == 0 and lflag and rflag:
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

Solution code:
N=int(input())
l = '('
r = ')'
S = {l:0,r:0}
for _ in range(N):
  s = {l:0,r:0}
  for v in input():
    if v == r:
      if s[l]>0:s[l]-=1
      else: s[r]+=1
    else:
      s[l]+=1
  if min(S[l],s[r]) < min(S[r],s[l]):
    if S[r] < s[l]:
      S[r]=s[r]
      S[l]+=(s[l]-S[r])
    else:
      S[l] = s[l]
      S[r]+= (s[r]-S[l])
  else:
    if S[l] < s[r]:
      S[l] = s[l]
      S[r] += (s[r]-S[l])
    else:
      S[r] = s[r]
      S[l] += (s[l]-S[r])
if S[r]==0 and S[l] == 0:
  print('Yes')
else:
  print('No')

Submission status: Wrong Answer

Solution code:
N = int(input())

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

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

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

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

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

Submission status: Wrong Answer

Solution code:
N = int(input())
S_info1 = []
S_info2 = []

tot = 0

for _ in range(N):
    s = input()
    score = 0
    maxv = 0
    minv = 0
    for c in s:
        if c == "(":
            score += 1
        else:
            score -= 1
        maxv = max(maxv, score)
        minv = min(minv, score)
    tot += score
    if minv >= 0:
        S_info1.append([s, score, maxv, minv])
    else:
        S_info2.append([s, score, maxv, minv])

if tot != 0:
    print("No")
else:
    S_info1.sort(key = lambda x:(-x[3], x[1]))
    #print(S_info1)
    tot = 0
    flag = True
    for i in range(len(S_info1)):
        s, score, maxv, minv = S_info1[i]
        if tot < -minv:
            flag = False
            break
        tot += score
    if not flag:
        print("No")
    else:
        print("Yes")