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
mx = 10**6+1000
index_plus = [[] for _ in range(mx*2)]
index_minus = [[] for _ in range(mx*2)]
n = int(input())
s = [input() for _ in range(n)]
cnts = []
sm = 0
cnt_minus = 0
cnt_plus = 0
for i in range(n):
    cnt = 0
    mn = 0
    for c in s[i]:
        if c == '(':
            cnt+=1
        else: cnt-=1
        mn = min(cnt, mn)
    cnts.append(abs(cnt))
    sm+=cnt
    if cnt<=0:
        index_minus[mn].append(i)
        cnt_minus+=1
    else:
        index_plus[-mn].append(i)
        cnt_plus+=1
if(sm != 0):
    print('No')
    sys.exit()


now = 0
que = []
for i in range(-mx-1, now+1):
    for j in index_plus[i]:
        que.append(j)
for i in range(cnt_plus):
    if(len(que)==0):
        print('No')
        sys.exit()
    j = que.pop()
    for k in range(now+1, now+cnts[j]+1):
        for l in index_plus[k]:
            que.append(l)
    now+=cnts[j]

que = []
now = 0
for i in range(-mx-1, now+1):
    for j in index_minus[i]:
        que.append(j)
for i in range(cnt_minus):
    if(len(que)==0):
        print('No')
        sys.exit()
    j = que.pop()
    for k in range(now+1, now+cnts[j]+1):
        for l in index_minus[k]:
            que.append(l)
    now+=cnts[j]
print('Yes')

Submission status: Wrong Answer

Solution code:
N = int(input())

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

C = [[0,0] for i in range(N)]

for i in range(N):
    for j in range(len(S[i])):
        if S[i][j] == '(':
            C[i][0] += 1
        else:
            C[i][0] -= 1
        C[i][1] = min(C[i][0],C[i][1])

if sum(C[i][0] for i in range(N)) != 0:
    print('No')
    exit()

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

now = 0
ans = 'Yes'
for i in range(N):
    if now + C[i][1] < 0:
        ans = 'No'
        break

    now += C[i][0]

print(ans)

Submission status: Wrong Answer

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

os = cs = 0
zo = []
zc = []
for i,s in enumerate(S):
    op = 0
    for c in s:
        if c=='(':
            op += 1
        else:
            if op: op -= 1
    cl = 0
    for c in s[::-1]:
        if c==')':
            cl += 1
        else:
            if cl: cl -= 1
    os += op
    cs += cl
    if op==0:
        zo.append(i)
    if cl==0:
        zc.append(i)

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

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, key=lambda x: x[0]):
        if t + tmn < 0:
            print('No')
            return
        t += tsm
    print('Yes')


if __name__ == '__main__':
    main()

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([dep-mindep,-1 * dep])

pl_d.sort()
mi_d.sort()

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:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    inf=10**9
    n=II()
    ss=[SI() for _ in range(n)]
    ms=[]
    for s in ss:
        mn=0
        now=0
        for c in s:
            if c=="(":now+=1
            else:now-=1
            if now<mn:mn=now
        ms.append((mn,now))
    ms.sort(key=lambda x:x[0]-x[1])
    #print(ms)
    cnt=0
    for mn,s in ms:
        if cnt+mn<0:
            print("No")
            exit()
        cnt+=s
    if cnt==0:print("Yes")
    else:print("No")

main()

Submission status: Wrong Answer

Solution code:
n=int(input())

t=[0 for i in range(n)]

for i in range(n):
  s=input()
  t[i]=s.count('(')-s.count(')')

t.sort()
t.reverse()
c=0
#print(t)
for i in range(n):
  c+=t[i]
  if c<0:
    print("No")
    exit()
if c==0:
  print("Yes")
else:
  print("No")

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N = int(input())
left = []
right = []
lst = []
for i in range(N):
    S = input()
    t = 0
    for c in S:
        if c == '(':
            t -= 1
        else:
            t += 1
    if S[0] == '(':
        left.append((t, i))
    if S[-1] == ')':
        right.append((t, i))
    lst.append((t, i))
left.sort()
right.sort(reverse=1)
if left[0][1] == right[0][1]:
    if len(right) > 1:
        l = left[0][1]
        r = right[1][1]
        lst.sort()
        cnt = 0
        for (t, i) in lst:
            if i == l or i == r:
                continue
            cnt += t
        if cnt == 0:
            print('Yes')
            exit()
    if len(left) > 1:
        l = left[1][1]
        r = right[0][1]
        lst.sort()
        cnt = 0
        for (t, i) in lst:
            if i == l or i == r:
                continue
            cnt += t
        if cnt == 0:
            print('Yes')
            exit()
else:
    l = left[0][1]
    r = right[0][1]
    lst.sort()
    cnt = 0
    for (t, i) in lst:
        if i == l or i == r:
            continue
        cnt += t
    if cnt == 0:
        print('Yes')
        exit()
print('No')

Submission status: Wrong Answer

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

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

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

print("Yes" if check1 and check2 and check3 else "No")

Submission status: Wrong Answer

Solution code:
n=int(input())
ch=True
fd=0
inv=0
bk=0
sm=0
for t in range (n):
    s=input()
    l=len(s)
    i=0
    curr=0
    m=l+1
    for i in range (l):
        if s[i]=='(':
            curr+=1
        else:
            curr-=1
        m=min(m,curr)
    if m<curr and m<0:
        ch=False
        inv+=1
    elif curr>0:
        fd+=1
    elif curr<0:
        bk+=1
    sm+=curr
    #print(m,curr,ch)
if ch and sm==0:
    print("Yes")
elif sm==0 and inv>0 and fd>=inv:
    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)
    heapify(rest)

    now = 0
    candidate = []
    for _ in range(n):
        # now + (-rest[0][0]) >= 0 なら使える
        while rest and now - rest[0][0] >= 0:
            min_balance, balance = heappop(rest)
            heappush(candidate, (balance, min_balance)) # balance を優先させる
        # now + (-min_balance) < 0 なら使えない
        while candidate and now - candidate[0][1] < 0:
            balance, min_balance = heappop(candidate)
            heappush(rest, (min_balance, 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:
n = int(input())
s = []
for i in range(n):
    temp = input()
    count = 0
    min_count = 0
    for j in temp:
        if j == "(":
            count += 1
        else:
            count -= 1
            min_count = min(min_count, count)
    s.append([count, min_count])
sum_count = sum([s[i][0] for i in range(n)])
if sum_count != 0:
    print("No")
else:
    s2 = [s[i] for i in range(n) if s[i][1] >= 0]
    s3 = [s[i] for i in range(n) if s[i][1] < 0]
    s3.sort(key = lambda x: x[1], reverse = True)
    flag = True
    count = 0
    for i in range(len(s2)):
        count += s2[i][0]
    for i in range(len(s3)):
        if count + s3[i][1] < 0:
            flag = False
            break
        else:
            count += s3[i][1]
    if flag == True:
        print("Yes")
    else:
        print("No")

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[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:
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
    if(lr[i][1]==0 and lr[i][0]!=0):
        existR=1

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

Submission status: Wrong Answer

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

A = [(0,0)]*N
B = [(0,0)]*N
for i,T in enumerate(S):
    m = 0
    tot = 0
    for t in T:
        if t==")":
            tot -= 1
            m = min(m,tot)
        else:
            tot += 1
    if tot >= 0:
        A[i] = (m,tot)
    else:
        B[i] = (m,tot)

A.sort(reverse=True)
B.sort()

tot = 0
ans = True
for m,t in A:
    if tot + m < 0:
        ans = False
        break
    tot += t
for m,t in B:
    if tot + m < 0:
        ans = False
        break
    tot += t
if tot != 0:
    ans = False

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

Submission status: Wrong Answer

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

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

def calc(S):
    now = 0
    ret = 0
    for s in S:
        if s == '(':
            now += 1
        else:
            now -= 1
        ret = min(ret, now)
    return ret

H = []
P = []
L = []

for s in S:
    less = -calc(s)
    if less == 0:
        H.append(s)
    else:
        l = s.count('(')
        r = len(s) - l
        if l >= r:
            P.append((less, s))
        else:
            L.append((less, s))

P.sort(reverse=False)
L.sort(reverse=False)
P = [s for _, s in P]
L = [s for _, s in L]

ans = ''.join(H + P + 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:
import sys
# input = sys.stdin.readline
# sys.setrecursionlimit(10 ** 9)
MOD = 10 ** 9 + 7

N = int(input())


tmp = 0
lst = []
lst_append = lst.append

for i 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:
        lst_append([min_, total])

lst.sort(key = lambda x: x[0], reverse = False) #途中で小さくなるものから優先的に入れる

# print (lst)
# print (tmp)
for a, b in lst:
    if tmp + a < 0:
        print ('No')
        exit()
    else:
        tmp += b

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

Submission status: Wrong Answer

Solution code:
#!python3

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

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


def main():
    l, r = [None] * N, [None] * N
    lstart, rend = [], []
    for i in range(N):
        l[i] = S[i].count("(")
        r[i] = len(S[i]) - l[i]
        if S[i][0] == "(":
            lstart.append(i)
        if S[i][-1] == ")":
            rend.append(i)
    
    if sum(l) != sum(r):
        print("No")
        return

    if len(lstart) == 0 or len(rend) == 0:
        print("No")
        return

    if N == 1:
        print("Yes")
        return
    
    if len(lstart) == 1 and len(rend) == 1:
        if lstart[0] == rend[0]:
            print("No")
            return
    
    print("Yes")


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    s = [list(input()) for _ in range(n)]
    L_cnt = []
    R_cnt = []
    LR_cnt = []
    min_l,min_r = 10**6,10**6
    for i in range(n):
        t = s[i]
        flag = 0
        l = 0
        r = 0
        for j in range(len(t)):
            if not flag and t[j] == ')':
                r += 1
            elif t[j] == '(':
                flag = 1
                l += 1
            else:
                l -= 1
                if l == 0:
                    flag = 0
        if r == 0 and l == 0:
            continue
        if r == 0:
            L_cnt.append(l)
        elif l == 0:
            R_cnt.append(r)
        else:
            LR_cnt.append([l,r])
            min_l = min(min_l,l)
            min_r = min(min_r,r)
    L,R = sum(L_cnt),sum(R_cnt)
    for i in range(len(LR_cnt)):
        L += LR_cnt[i][0]
        R += LR_cnt[i][1]
    if LR_cnt and L_cnt and R_cnt and (L==R) and min_r <= L and min_l <= R:
        print('Yes')
    elif L_cnt and R_cnt and (L==R):
        print('Yes')
    else:
        print('No')
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import heapq
n = int(input())
s = [input() for _ in range(n)]
t = [None] * n
for i in range(n):
    k = 0
    m = 0
    for c in s[i]:
        if c == '(':
            k += 1
        else:
            k -= 1
            m = min(k, m)
    t[i] = (-m, k)
t.sort()
hq = []
d = 0
idx = 0
for i in range(n):
    while idx < n and d >= t[idx][0]:
        m, k = t[idx]
        heapq.heappush(hq, (-k, m))
        idx += 1
    if hq:
        k, m = heapq.heappop(hq)
    else:
        print('No')
        break
    if m > d:
        print('No')
        break
    d -= k
else:
    if d == 0:
        print('Yes')
    else:
        print('No')

Submission status: Wrong Answer

Solution code:
import bisect
import sys
from collections import defaultdict
input = sys.stdin.readline


class Node:
    def __init__(self, value, index):
        self.value = value
        self.index = index

    def __str__(self):
        return 'val : ' + str(self.value) + ' index : ' + str(self.index)

# 0-indexed SegmentTree


class SegmentTree:
    def __init__(self, N, default_list, default_value=-10**10):
        self.N0 = pow(2, (N - 1).bit_length())
        self.nodes = [Node(default_value, i + 1 - self.N0) for i in range(2 * self.N0 - 1)]
        for i in reversed(range(2 * self.N0 - 1)):
            ind = i + 1 - self.N0
            if ind >= N:
                self.nodes[i].value = default_value
            elif N > ind >= 0:
                self.nodes[i].value = default_list[ind]
            else:
                self.nodes[i] = self.process(self.nodes[i * 2 + 1], self.nodes[i * 2 + 2])

    def __str__(self):
        return '[' + ', '.join(map(str, [self.nodes[i + self.N0 - 1].value for i in range(self.N0)])) + ']'

    def query(self, L, R):  # [L,R)の値
        retnode = Node(-10**10, -10**10)
        L += self.N0
        R += self.N0
        while L < R:
            if R & 1:
                R -= 1
                retnode = self.process(retnode, self.nodes[R - 1])
            if L & 1:
                retnode = self.process(retnode, self.nodes[L - 1])
                L += 1
            L >>= 1
            R >>= 1
        return retnode

    def process(self, node_x, node_y):  # x,yが子の時，親に返る値
        if node_x.value > node_y.value:
            return node_x
        else:
            return node_y

    def update(self, i, x):
        i += self.N0 - 1
        self.nodes[i] = Node(x, i + 1 - self.N0)
        while i:
            i = (i - 1) // 2
            self.nodes[i] = self.process(self.nodes[i * 2 + 1], self.nodes[i * 2 + 2])


N = int(input())
ss = [input().replace("\n", "") for _ in range(N)]


def calc(S):
    tmp = 0
    MIN = 0
    for s in S:
        if s == "(":
            tmp += 1
        else:
            tmp -= 1
        MIN = min(tmp, MIN)

    return -MIN, tmp


cnts = []
for s in ss:
    down, up = calc(s)
    cnts.append((down, up, s))

cnts.sort()
# print(cnts)

ups = []
downs = []
rights = defaultdict(int)
for i, (d, u, s) in enumerate(cnts):
    downs.append(d)
    ups.append(u)

ST = SegmentTree(N, ups)

tmp = 0
for _ in range(N):
    R = bisect.bisect_right(downs, tmp)
    # print(tmp, R)
    node = ST.query(0, R)
    ST.update(node.index, -10 ** 10)

    tmp += node.value

    if tmp < 0:
        print("No")
        sys.exit()


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

Submission status: Wrong Answer

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

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

def calc(S):
    now = 0
    ret = 0
    for s in S:
        if s == '(':
            now += 1
        else:
            now -= 1
        ret = min(ret, now)
    return ret

H = []
P = []
L = []

for s in S:
    less = -calc(s)
    if less == 0:
        H.append(s)
    else:
        l = s.count('(')
        r = len(s) - l
        if l >= r:
            P.append((less, s))
        else:
            L.append((less, s))

P.sort(reverse=True)
L.sort(reverse=False)
P = [s for _, s in P]
L = [s for _, s in L]

ans = ''.join(H + P + 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:
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 = len(s) - l
        if l >= r:
            P.append((less, s))
        else:
            L.append((less, s))

P.sort()
L.sort(reverse=True)
P = [s for _, s in P]
L = [s for _, s in L]

ans = ''.join(H + P + 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:
import sys
from itertools import accumulate
N = int(input())
ls = [0]*N
M = [0]*N
m = 0
for i in range(N):
  S = input()
  l = [0]*len(S)
  for j,c in enumerate(S):
    if c=='(':
      l[j] = 1
    else:
      l[j] = -1
  ls[i] = l.copy()
  M[i] = sum(l)
  m += sum(l)
line = sorted(range(N),key=lambda x:M[x],reverse=True)
b = []
for i in line:
  b += ls[i]
b = list(accumulate(b))
if m!=0:
  print('No')
  sys.exit()
if all(c>=0 for c in b):
  print('Yes')
else:
  print('No')

Submission status: Wrong Answer

Solution code:
import sys
n=int(input())
s=[list(input()) for i in range(n)]
ct=[]
ct1=0;ct2=0
for i in range(n):
  ct3=0
  L=[]
  for j in range(len(s[i])):
    if s[i][j]=='(':
      ct1+=1
      ct3+=1
      L.append(ct3)
    else:
      ct2+=1
      ct3-=1
      L.append(ct3)
  ct.append([min(L),L[-1]])
if ct1!=ct2:
  print('No')
  sys.exit()
ct.sort()
ct.reverse()
ct4=0
for i in range(len(ct)):
  if ct4+ct[i][0]<0:
    print('No')
    sys.exit()
  ct4+=ct[i][1]
  if ct4<0:
    print('No')
    sys.exit()
print('Yes')

Submission status: Wrong Answer

Solution code:
N=int(input())
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)
        
    data.append((maxi,mini,dif))
data.sort(key=lambda x:(-x[1],x[2]))
flag=True
sums=0
for some in data:
    maxi,mini,dif=some
    if sums+mini<0:
        flag=False
        break
    else:
        sums+=dif
if flag:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
n = int(input())
left = []
mid = []
right = []
L = []
R = []

for i in range(n):
    s = input()
    l = 0
    r = 0
    for x in s:
        if x == '(':
            l += 1
        else:
            if l > 0:
                l -= 1
            else:
                r += 1
    if l > 0 and r == 0:
        left.append((l, r))
    elif l > 0 and r > 0:
        mid.append((r, l))  # a,b
    elif l == 0 and r > 0:
        right.append((l, r))
    L.append(l)
    R.append(r)

if sum(L) != sum(R):
    print('No')
    exit()

A = 0
B = 0
for x in left:
    A += x[0]
for x in right:
    B += x[1]

mid = sorted(mid, key=lambda x: x[0]*10**7-x[1])
l = A
r = 0
for a, b in mid:
    if l < a:
        print('No')
        exit()
    l -= a
    l += b

print('Yes')

Submission status: Wrong Answer

Solution code:
N = int(input())
S = []
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
	S.append((l_needed, -r_needed, s))

S.sort()
rest_l = 0
for i in range(N):
	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

if rest_l > 0:
	print("No")
else:
	print("Yes")

Submission status: Wrong Answer

Solution code:
import heapq
n = int(input())
sss = [input() for _ in range(n)]

a = []
b = []
ss = 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)
    if s >= 0:
        a.append([-s, mi, ma, i])
    else:
        b.append([s, mi-s, ma-s, i])
    ss += s

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
        kkk = 0
        for j in heapq.heappop(heap)[-1]:
            kkk += 1
            if j == "(":
                s += 1
            else:
                s -= 1
            if s < 0:
                print("No")
                exit()


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
        kkk = 0
        for j in heapq.heappop(heap)[-1]:
            kkk += 1
            if j == ")":
                s += 1
            else:
                s -= 1
            if s < 0:
                print("No")
                exit()


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

Submission status: Wrong Answer

Solution code:
n=int(input())
a=[]
for i in range(n):
    z=input()
    b,c,d=z.count('(')-z.count(')'),[],0
    for j in range(len(z)):
        d+=1 if z[j]=='(' else -1
        c.append(d)
    a.append([b,min(min(c),0)])
e=0
for i in range(n):
    e+=a[i][0]
if e!=0:
    print('No')
    exit()
e=0
a1,a2=[],[]
for i in range(n):
    if a[i][0]>=0 and a[i][1]==0:
        e+=a[i][0]
    elif a[i][0]>0:
        a1.append(a[i])
    else:
        a2.append(a[i])
a1=sorted(a1,key=lambda x:x[1],reverse=1)
a2=sorted(a2,key=lambda x:x[1])
for i in range(len(a1)):
    if e+a1[i][1]<0:
        print('No')
        exit()
    e+=a1[i][0]
for i in range(len(a2)):
    if e+a2[i][1]<0:
        print('No')
        exit()
    e+=a2[i][0]
print('Yes')

Submission status: Wrong Answer

Solution code:
N=int(input())

cand=[]
for _ in range(N):
    cand.append(input())
    
cand.sort(key=lambda x : x.count(")")-x.count("("))

ans=("".join(cand))

temp=0
#print(ans)
for item in ans:
    if item=="(":
        temp+=1
    else:
        temp-=1
    if temp<0:
        print("No")
        exit()
if temp==0:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N = int(input())
bool = [0,0,0]
Sigma = ''
for i in range(N):
    S = input()

    if S[0] == '(':
        bool[0] = 1
    elif S[-1] == ')':
        bool[1] = 1
    Sigma += S

if Sigma.count('(') == Sigma.count(')'):
    bool[2] = 1
if bool == [1, 1, 1]:
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

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

D = [[0] * 2 for _ in range(N)]

for i in range(N):
  s = S[i]
  ma = 0
  l = 0
  r = 0
  for j in s:
    if j == ")":
      r += 1
    else:
      l += 1
    ma = max(ma, r - l)
  D[i] = [l - r, ma, s]

cnt = 0
P = []
M = []
for x, y ,s in D:
  if x >= 0:
    if y <= 0:
      cnt += x
    else:
      P.append([x, y])
  else:
    M.append([x, y, s])

P.sort(key = lambda x:x[1])

for x, y in P:
  if y > cnt:
    print("No")
    exit()
  cnt += x

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

for i in range(len(M) -1, -1, -1):
  x, y, s= M[i]
  if s[-1] == ")":
    g = x
    M[i] = [0, 0, ""]
    break
else:
  print("No")
  exit()

for x, y, s in M:
  if cnt < y:
    print("No")
    exit()
  cnt += x

if cnt + g == 0:
  print("Yes")
else:
  print("No")