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

si.sort()
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]

for i, j in si:
    count -= i
    if count < 0:
        break
    count += j
count -= last[0]

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

Submission status: Wrong Answer

Solution code:
n = int(input())
s = []
ml = set()
mr = set()
for i in range(n):
  si = input()
  if si[0] == '(':
    ml.add(i)
  if si[-1] == ')':
    mr.add(i)
  s.append((si.count('('),si.count(')')))

if len(ml) == 0 or len(mr) == 0 or (len(ml) == 1 and len(mr) == 1 and ml == mr):
  print('No')
  exit()

s.sort(key=lambda x:(-x[0],x[1]))
l = 0
r = 0
for a,b in s:
  l += a
  r += b
  if l < r:
    print('No')
    exit()
print('Yes' if l == r else 'No')

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
input = lambda:sys.stdin.readline().rstrip()
from heapq import heappop, heappush, heapify
def resolve():
    n = int(input())
    rest = [None] * n
    for i in range(n):
        balance = min_balance = 0
        for c in input():
            if c == '(':
                balance += 1
            else:
                balance -= 1
            min_balance = min(min_balance, balance)
        rest[i] = (-min_balance, -balance) # min_balance の大きい方から取得、balance はまあどちらでも
    heapify(rest)

    now = 0
    candidate = [] # (-balance, -min_balance), balance の大きい方から取得
    for _ in range(n):
        while candidate and now - candidate[0][1] < 0:
            balance, min_balance = heappop(candidate)
            heappush(rest, (min_balance, balance))
        while rest and now - rest[0][0] >= 0:
            min_balance, balance = heappop(rest)
            heappush(candidate, (balance, min_balance))
        if not candidate:
            print("No")
            return
        balance, min_balance = heappop(candidate)
        now -= balance
        if now < 0:
            print("No")
            return

    print("Yes" if now == 0 else "No")
resolve()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    N = int(input())
    S = [input().rstrip() for _ in range(N)]

    mn = [0] * N
    sm = [0] * N
    for i, s in enumerate(S):
        t = 0
        tmn = 0
        for c in s:
            if c == '(':
                t += 1
            else:
                t -= 1
            tmn = min(tmn, t)
        mn[i] = tmn
        sm[i] = t

    if sum(sm) != 0:
        print('No')
        return
    t = 0
    for tmn, tsm in sorted(zip(mn, sm), reverse=True):
        if t + tmn < 0:
            print('No')
            return
        t += tsm
    print('Yes')


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
class SegmentTree():
    def __init__(self, arr, func=min, ie=2**63):
        self.n = 2**(len(arr) - 1).bit_length()
        self.ie = ie
        self.func = func
        self.tree = [ie for _ in range(2 * self.n)]
        for i in range(len(arr)):
            self.tree[self.n + i - 1] = arr[i]
        for i in range(self.n - 1)[::-1]:
            self.tree[i] = func(self.tree[2 * i + 1], self.tree[2 * i + 2])

    def set(self, idx, x):
        idx += self.n - 1
        self.tree[idx] = x
        while idx:
            idx = (idx - 1) // 2
            self.tree[idx] = self.func(self.tree[2 * idx + 1], self.tree[2 * idx + 2])

    def query(self, lt, rt):
        if rt <= lt:
            return self.ie
        lt += self.n - 1
        rt += self.n - 2
        tmp_l = self.ie
        tmp_r = self.ie
        while rt - lt > 1:
            if lt & 1 == 0:
                tmp_l = self.func(tmp_l, self.tree[lt])
            if rt & 1 == 1:
                tmp_r = self.func(self.tree[rt], tmp_r)
                rt -= 1
            lt = lt // 2
            rt = (rt - 1) // 2
        if lt == rt:
            tmp_l = self.func(tmp_l, self.tree[lt])
        else:
            tmp_l = self.func(self.func(tmp_l, self.tree[lt]), self.tree[rt])
        return self.func(tmp_l, tmp_r)
import sys
input = sys.stdin.readline

from bisect import bisect_left, bisect_right

INF = 10**18

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

D = []
E = []


for i in range(N):
    kakko = 0
    minkakko = 10**18
    for j in range(len(S[i])):
        if S[i][j] == '(':
            kakko += 1
        else:
            kakko -= 1
        minkakko = min(kakko, minkakko)
    D.append((minkakko, kakko))
    E.append(minkakko)


E.sort()
D.sort()

F = []
for i in range(N):
    F.append((D[i][1], D[i][0], i))

s = 0

st = SegmentTree(F, max, (-INF, -INF, 0))

for i in range(N):
    x = bisect_left(E, -s)
    if x >= N:
        print('No')
        break
    v = st.query(x, N + 1)
    if v[0] == -INF:
        print('No')
        break
    s += v[0]
    st.set(v[2], (-INF, -INF, 0))
else:
    if s == 0:
        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)

    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:
N=int(input())
plus_data=[]
minus_data=[]
for i in range(N):
    s=list(input())
    dif=0
    maxi=0
    mini=0
    for j in range(len(s)):
        if s[j]=="(":
            dif+=1
        else:
            dif-=1
        maxi=max(maxi,dif)
        mini=min(mini,dif)
    if mini>=0:  
        plus_data.append((maxi,mini,dif))
    else:
        minus_data.append((maxi,mini,dif))
    
minus_data.sort(key=lambda x:(-x[1],-x[2]))
flag=True
sums=0
for some in plus_data:
    sums+=some[2]
for some in minus_data:
    maxi,mini,dif=some
    if sums+mini<0:
        flag=False
        break
    else:
        sums+=dif
if flag:
    if sums==0:
        print("Yes")
    else:
        print("No")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
N = int(input())
S = []
last = None
for i in range(N):
	s = input()
	l = len(s)
	r_needed = 0
	l_needed = 0
	for j in range(l):
		if s[j] == "(":
			r_needed += 1
		elif s[j] == ")" and r_needed > 0:
			r_needed -= 1

		if s[l-1 - j] == ")":
			l_needed += 1
		elif s[l-1 - j] == "(" and l_needed > 0:
			l_needed -= 1
	if r_needed == 0 and last == None:
		last = (l_needed, -r_needed, s)
	else:
		S.append((l_needed, -r_needed, s))

if last == None:
	print("No")
	exit()

S.sort()
rest_l = 0
for i in range(N-1):
	s = S[i]
	l_needed = s[0]
	r_needed = -s[1]
	if rest_l < l_needed:
		print("No")
		exit()
	rest_l -= l_needed
	rest_l += r_needed
rest_l -= last[0]
if rest_l != 0:
	print("No")
else:
	print("Yes")

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
#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())
brackets_plus = []
brackets_minus = []
right = 0
left = 0
for i in range(n):
    s = input()
    cur = 0
    m = 0
    for j in range(len(s)):
        if s[j] == "(":
            left += 1
            cur += 1
        else:
            right += 1
            cur -= 1
            m = min(m,cur)
    if cur >= 0:
        brackets_plus.append((m,cur))
    else:
        brackets_minus.append((m,-cur))
if right != left:
    print("No")
    exit()
cur = 0
brackets_plus.sort(reverse = True)
for i in brackets_plus:
    if i[0] + cur < 0:
        print("No")
        exit()
    cur += i[1]
brackets_minus.sort()
for i in brackets_minus:
    if i[0] + cur < 0:
        print("No")
        exit()
    cur -= i[1]
print("Yes")

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**6-1, -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:]
        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())
left = []
right = []
for i in range(n):
    s = input()
    n0 = 0
    n1 = 0
    l = len(s)
    for j in range(l):
        if s[j] == "(":
            n0 += 1
        else:
            if n0 == 0:
                n1 += 1
            else:
                n0 -= 1
    if n0 > n1:
        left.append([n1, n0])
    else:
        right.append([n0, n1])

left.sort()
right.sort()

def solve():
    nl0 = 0
    nl1 = 0
    for p in left:
        if p[0] > nl0:
            return False
        nl0 -= p[0]
        nl1 += p[1]
    nr0 = 0
    nr1 = 0
    for p in right:
        if p[0] > nr1:
            return False
        nr1 -= p[0]
        nr0 += p[1]
    if nl1 == nr0:
        return True
    else:
        return False

if solve():
    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] == '(':
                    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] == ')':
                    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:
n=int(input())
A=[[] for i in range(n)]
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
  A[i]=[b,a]
A.sort(reverse=True)
a=0
b=0
f=0
for i in range(n):
  if a+A[i][0]<0:
    f=1
  a=a+A[i][1]
if a!=0:
  f=1
if f==0:
  print("Yes")
else:
  print("No")

Submission status: Wrong Answer

Solution code:
#!/bin/bash
''':'
docker run --rm -it -v $(cd $(dirname $0) && pwd):/vo:ro pypy:3-2.4.0 \
   /bin/bash -c "pypy3 /vo/$(basename $0) < /vo/input.txt"
exit $?
'''
import sys

def _s(): return sys.stdin.readline().strip()

def _i(): return int(sys.stdin.readline().strip())

def parse(s):
    l, r = 0, 0
    for c in s:
        if c == '(':
            r += 1
        else:
            if r>0:
                r-=1
            else:
                l+=1
    return (r,l)


def main():
    n = _i()
    p = list(filter(lambda x: x !=(0,0), [parse(_s()) for _ in range(n)]))
    p.sort(key= lambda x: (-x[0],x[1]))

    r = 0
    for pi in p:
        rr, ll = pi
        if ll > r:
            return 'No'
        r += (rr - ll)

    return 'Yes' if r == 0 else 'No'

if __name__ == "__main__":
    print(main())

Submission status: Wrong Answer

Solution code:
N=int(input())

L=[]
for i in range(N):
    s=input()
    Min=0
    cnt=0
    for j in range(len(s)):
        if s[j]=="(":
            cnt+=1
        else:
            cnt-=1
            if Min>cnt:
                Min=cnt
    L.append([Min,cnt])
L.sort(reverse=True)
#print(L)

Sum=0
for i,j in L:
    Sum+=j
if Sum!=0:
    print("No")
else:
    #print("Yes?")
    cnt=0
    for i,j in L:
        if cnt+i<0:
            print("No")
            exit()
        cnt+=j
    print("Yes")

Submission status: Wrong Answer

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

    tmp = 0
    lst1 = [] #合計としては伸びるけど途中にマイナスがあるもの
    lst1_append = lst1.append

    lst2 = [] #合計してもマイナス　途中もマイナス
    lst2_append = lst2.append

    for _ in range(N):
        S = list(input())
        min_ = 0
        total = 0
        for s in S:
            if s == '(':
                total += 1
            else:
                total -= 1
                min_ = min(min_, total)
        if min_ == 0:
            tmp += total
        else:
            if total >= 0:
                lst1_append([min_, total])
            else:
                lst2_append([min_, total])

    lst1.sort(key = lambda x: x[0], reverse = True) #途中での小さくなり方が小さいものから入れる どんどん条件は緩くなるから小さくなる値が0に近いものから
    for a, b in lst1:
        if tmp + a < 0:
            print ('No')
            exit()
        else:
            tmp += b

    lst2.sort(key = lambda x: x[0], reverse = False) #どんどん条件が厳しくなるから、より小さいもの　= 0から遠いもの　から使っていく
    for a, b in lst2:
        if tmp + a < 0:
            print ('No')
            exit()
        else:
            tmp += b

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

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
bra = []
ket = []
for _ in range(n):
  s = input()
  mini = 0
  now = 0
  l = len(s)
  for i in range(l):
    if s[i] == '(':
      now += 1
    else:
      now -= 1
      mini = min(mini,now)
  if now >= 0:
    bra.append([-mini,now])
  s = s[::-1]
  mini = 0
  now = 0
  for i in range(l):
    if s[i] == ')':
      now += 1
    else:
      now -= 1
      mini = min(mini,now)
  if now >= 0:
    ket.append([-mini,now])  
check = 0
for x in bra:
  #print(x)
  check += x[1]
if check != 0:
  print('No')
  exit()
bra.sort()
now = 0
here = -1
#print(bra)
import heapq
pool = []
for i in range(n):
  while here != n-1:
    if bra[here+1][0] <= now:
      here += 1
      heapq.heappush(pool,-bra[here][1])
    else:
      break
  #print(i,'#',pool)
  if not pool:
    print('No')
    exit()
  else:
    now -= heapq.heappop(pool)

ket.sort()
now = 0
here = -1
#print(bra)
pool = []
for i in range(n):
  while here != n-1:
    if ket[here+1][0] <= now:
      here += 1
      heapq.heappush(pool,-ket[here][1])
    else:
      break
  #print(i,'#',pool)
  if not pool:
    print('No')
    exit()
  else:
    now -= heapq.heappop(pool)
print('Yes')

Submission status: Wrong Answer

Solution code:
import sys

st = []
n = int(input())
for i in range(n):
    s = input()
    bal = 0
    min_bal = 0
    for c in s:
        bal += 1 if c == '(' else -1
        min_bal = min(bal, min_bal)

    st.append((min_bal, bal))

st.sort(reverse=True)

cur = 0
for m, e in st:
    if cur + m < 0:
        print("No")
        sys.exit()

    cur += e

print("Yes" if cur == 0 else "No")

Submission status: Wrong Answer

Solution code:
n=int(input())
A=[]
for i in range(n):
  x=0
  min=0
  now=input()
  for j in range(len(now)):
    if now[j]=="(":
      x+=1
    else:
      x-=1
      if min>x:
        min-=1
  A.append([x,min])
A=sorted(A, key=lambda func: func[1],reverse=True) 

check=0
OK="Yes"
for i in range(n):
  if check+A[i][1]<0:
    OK="No"
  else:
    check+=A[i][0]
if check!=0:
  OK="No"
print(OK)

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
for i in range(n):
    c,d = l[i]
    if c == 0:
        if d == 0:
            key[2] += 1
        else:
            key[0] += 1
    else:
        if d == 0:
            key[1] += 1
    ac += c
    ad += d
if ac == ad:
    if sum(key) < 2:
        print("No")
    else:
        if key[2] == 0 and (key[1] == 0 or key[0] == 0):
            print("No")
        else:
            print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from collections import Counter
def main():
    N = int( input())
    Ss = [ input() for _ in range(N)]
    left = 0
    right = 0
    Up = []
    Down = []
    Sig = []
    for S in Ss:
        C = Counter(S)
        left += C["("]
        right += C[")"]
        now = 0
        p = [0]
        for s in S:
            if s == "(":
                now += 1
            else:
                now -= 1
            p.append(now)
        m = -min(p)
        s = p[0]+m
        g = p[-1]+m
        if s == g:
            Sig.append((s, s, g))
        elif s < g:
            Up.append((s ,s, g))
        else:
            Down.append((g,s,g))
    if left != right:
        print("No")
        return
    Sig.sort()
    Up.sort()
    Down.sort()
    now = 0
    for m,s,g in Up:
        if now < m:
            print("No")
            return
        now += g-s
    for m,s,g in Sig:
        if now < m:
            print("No")
            return
    for m,s,g in Down:
        if now < m:
            print("No")
            return
        now += g-s    
    print("Yes")
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

n=int(input())
D=[]
for i in range(n):
    s=input()
    m=0
    L=0
    R=0
    for l in s:
        if l=="(":
            L+=1
        else:
            R+=1
        m=min(L-R,m)
    D.append([m,L-R,i])
D=list(reversed(sorted(D)))
a=0
for d in D:
    if a+d[0]>=0 and a+d[1]>=0:
        a+=d[1]
    else:
        print("No")
        sys.exit()
if a==0:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:

"""

大事な要素
深さと高低差
まず、高低差の話が0であることは必須

もう一つ、現状が深さ以上ないと設置できない。
まず、高くするやつで置けるやつはどんどんおいていい。
置いたもん勝ち
→つまり、+で深さが浅い順においていけばいい

降りるときは、深い→浅いが置けない場合で浅い→深いが置ける場合はない
→深い順に億


"""


N = int(input())

ans = 0

pl_d = [] 
mi_d = []

for lp in range(N):

    S = input()

    dep = 0
    mindep = 0

    for i in S:
        if i == "(":
            dep += 1
        else:
            dep -= 1

        mindep = min(dep,mindep)

    if dep >= 0:
        pl_d.append([mindep,dep])
    else:
        mi_d.append([mindep-dep,-1 * dep])

pl_d.sort()
mi_d.sort()
pl_d.reverse()
mi_d.reverse()

print (pl_d,mi_d)

nowp = 0

import sys
for i in range(len(pl_d)):

    nd,np = pl_d[i]

    if nowp + nd < 0:
        print ("No")
        sys.exit()

    nowp += np

nowm = 0

import sys
for i in range(len(mi_d)):

    nd,np = mi_d[i]

    if nowm + nd < 0:
        print ("No")
        sys.exit()

    nowm += np


if nowp != nowm:
    print ("No")
else:
    print ("Yes")

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')
elif len(l)==1:
	print('No')
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
sys.setrecursionlimit(2147483647)
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
input = lambda:sys.stdin.readline().rstrip()
from heapq import heappop, heappush, heapify
def resolve():
    n = int(input())
    rest = [None] * n
    for i in range(n):
        balance = min_balance = 0
        for c in input():
            if c == '(':
                balance += 1
            else:
                balance -= 1
            min_balance = min(min_balance, balance)
        rest[i] = (-min_balance, -balance) # min_balance の大きい方から取得、balance はまあどちらでも
    heapify(rest)

    now = 0
    candidate = [] # (-balance, -min_balance), balance の大きい方から取得
    for _ in range(n):
        while candidate and now - candidate[0][1] < 0:
            balance, min_balance = heappop(candidate)
            heappush(rest, (min_balance, balance))
        while rest and now - rest[0][0] >= 0:
            min_balance, balance = heappop(rest)
            heappush(candidate, (balance, min_balance))
        if not candidate:
            print("No")
            return
        balance, min_balance = heappop(candidate)
        now -= balance

    print("Yes" if now == 0 else "No")
resolve()

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 = []
    for r, m in RM:
        if m < 0:
            if r >= 0:
                negp.append((-m, r))
            else:
                negn.append((m, -r))
        else:
            pos += r
    negp.sort()
    for m, r in negp:
        if pos - m < 0:
            return False
        pos += r
    negn.sort()
    for m, r 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:
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)
        else:
            nr += max(buff_r - nl, 0)
            nl = max(nl - buff_r, 0)

        buff_l = 0
        buff_r = 0

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


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

def count(s):
    n = len(s)
    n1 = 0
    n2 = 0
    for i in range(n):
        if s[i]=='(':
            n2 += 1
        else:
            if n2 > 0:
                n2 -= 1
            else:
                n1 += 1
    return n1,n2

l = []
for i in range(N):
    n1,n2 = count(S[i])
    if n1+n2!=0:
        l.append([n1,n2])

l.sort(key=lambda x:x[1]-x[0])
l.sort(key=lambda x:x[0])

ans = True
n = 0
for i in range(len(l)):
    n1,n2 = l[i]
    if n1 > n:
        ans = False
    n += n2-n1
if n!=0:
    ans = False
if ans:
    ans = 'Yes'
else:
    ans = 'No'
print(ans)

Submission status: Wrong Answer

Solution code:
#0や1のケースに注意
#index out of range

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    #from math import gcd

    #inf = 10**17
    #mod = 10**9 + 7

    n = int(input())
    left = 0
    right = 0
    flag = 0
    for i in range(n):
        s = input().rstrip()
        if s[0] == '(':
            for i in s:
                if i=='(':
                    left += 1
                else:
                    left -= 1
        else:
            for i in s:
                if i == ')':
                    right += 1
                else:
                    right -= 1
            if s[-1] == ')':
                flag = 1
    if flag == 1 and left == right:
        print('Yes')
    else:
        print('No')


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
a, b = 0, 0
cnt = [0, 0]
for _ in range(n):
    s = list(input())
    l = len(s)
    for i in s:
        if i == ")":
            cnt[0] += 1
        else:
            cnt[1] += 1
    if not s[0] == ")":
        x = 0
        for i in range(l):
            if s[i] == "(":
                x += 1
            else:
                x -= 1
            if x < 0:
                break
        if x > 0:
            a += 1
    if not s[l - 1] == "(":
        y = 0
        for i in range(l):
            if s[l - i - 1] == ")":
                y += 1
            else:
                y -= 1
            if y < 0:
                break
        if y > 0:
            b += 1
print("Yes" if cnt[0] == cnt[1] and a > 0 and b > 0 else "No")