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 numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial, gcd
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10 ** 7)
enu = enumerate
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep="\n")

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

up = []
do = []
for li in L:
    l, r = 0, 0
    ext_neg = 0
    ext_pos = 0
    for op in li:
        if op == "(":
            l += 1
        elif op == ")":
            r += 1
        ext_neg = min(ext_neg, l - r)
        ext_pos = max(ext_pos, l - r)
    if 0 <= l - r:
        up.append((l - r, ext_neg, ext_pos))
    else:
        do.append((l - r, ext_neg, ext_pos))
up.sort(key=lambda tup: (-tup[1], -tup[0]))
do.sort(key=lambda tup: (-tup[0], tup[1]))
# print(up)
# print(do)

cur = 0
for upi in up:
    dif, ext_neg, ext_pos = upi
    if cur + ext_neg < 0:
        print("No")
        exit()
    cur += dif
for doi in do:
    dif, ext_neg, ext_pos = doi
    if cur + ext_neg < 0:
        print("No")
        exit()
    cur += dif
if cur == 0:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
# import numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial, gcd
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10 ** 7)
enu = enumerate
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep="\n")

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

up = []
do = []
for li in L:
    l, r = 0, 0
    ext_neg = 0
    ext_pos = 0
    for op in li:
        if op == "(":
            l += 1
        elif op == ")":
            r += 1
        ext_neg = min(ext_neg, l - r)
        ext_pos = max(ext_pos, l - r)
    if 0 <= l - r:
        up.append((l - r, ext_neg, ext_pos))
    else:
        do.append((l - r, ext_neg, ext_pos))
up.sort(key=lambda tup: (-tup[1], -tup[0]))
do.sort(key=lambda tup: (tup[1], -tup[0]))
# print(up)
# print(do)

cur = 0
for upi in up:
    dif, ext_neg, ext_pos = upi
    if cur + ext_neg < 0:
        print("No")
        exit()
    cur += dif
for doi in do:
    dif, ext_neg, ext_pos = doi
    if cur + ext_neg < 0:
        print("No")
        exit()
    cur += dif
if cur == 0:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
# import numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial, gcd
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10 ** 7)
enu = enumerate
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep="\n")

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

up = []
do = []
for li in L:
    l, r = 0, 0
    ext_neg = 0
    ext_pos = 0
    for op in li:
        if op == "(":
            l += 1
        elif op == ")":
            r += 1
        ext_neg = min(ext_neg, l - r)
        ext_pos = max(ext_pos, l - r)
    if 0 <= l - r:
        up.append((l - r, ext_neg, ext_pos))
    else:
        do.append((l - r, ext_neg, ext_pos))
up.sort(key=lambda tup: (-tup[1], -tup[0]))
do.sort(key=lambda tup: (-tup[1], -tup[0]))
# print(up)
# print(do)

cur = 0
for upi in up:
    dif, ext_neg, ext_pos = upi
    if cur + ext_neg < 0:
        print("No")
        exit()
    cur += dif
for doi in do:
    dif, ext_neg, ext_pos = doi
    if cur + ext_neg < 0:
        print("No")
        exit()
    cur += dif
if cur == 0:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
# import numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial, gcd
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10 ** 7)
enu = enumerate
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep="\n")

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

up = []
do = []
for li in L:
    l, r = 0, 0
    ext_neg = 0
    ext_pos = 0
    for op in li:
        if op == "(":
            l += 1
        elif op == ")":
            r += 1
        ext_neg = min(ext_neg, l - r)
        ext_pos = max(ext_pos, l - r)
    if 0 <= l - r:
        up.append((l - r, ext_neg, ext_pos))
    else:
        do.append((l - r, ext_neg, ext_pos))
up.sort(key=lambda tup: (-tup[1], -tup[0]))
do.sort(key=lambda tup: (tup[2], tup[0]))
# print(up)
# print(do)

cur = 0
for upi in up:
    dif, ext_neg, ext_pos = upi
    if cur + ext_neg < 0:
        print("No")
        exit()
    cur += dif
for doi in do:
    dif, ext_neg, ext_pos = doi
    if cur + ext_neg < 0:
        print("No")
        exit()
    cur += dif
if cur == 0:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    N=ii()
    left_br = "("
    right_br = ")"

    XS = []
    br = 0
    left_head_count = 0
    for i in range(N):
        S = list(input())
        count = {left_br:0,right_br:0}
        head = None
        for s in S:
            if head is None:
                head = s
            if s == right_br and count[left_br] > 0:
                count[left_br] -= 1 
            else:
                count[s] += 1

            if count[left_br] == 0 and count[right_br] == 0:
                head = None
            elif count[left_br] == 0:
                head = right_br
    
        # print(count,head)
        if head == left_br:
            left_head_count += 1

        XS.append(count)
        br += count[left_br]
        br -= count[right_br]
        assert count[left_br] >= 0 and count[right_br] >= 0
    
    if left_head_count == 0:
        print("No")
    else:
        print("Yes" if br == 0 else "No")





if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    N=ii()
    left_br = "("
    right_br = ")"

    XS = []
    br = 0
    left_head_count = 0
    for i in range(N):
        S = list(input())
        count = {left_br:0,right_br:0}
        head = S[0]
        for s in S:
            if s == right_br and count[left_br] > 0:
                count[left_br] -= 1 
            else:
                count[s] += 1

            if count[left_br] == 0 and count[right_br] == 0:
                head = None
            elif count[left_br] == 0:
                head = right_br
    
        # print(count,head)
        if head == left_br:
            left_head_count += 1

        XS.append(count)
        br += count[left_br]
        br -= count[right_br]
    
    if left_head_count == 0:
        print("No")
    else:
        print("Yes" if br == 0 else "No")





if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N=int(input())
S=[]
H=[]
for i in range(N):
  s = input()
  S.append(s)
  h =[0]
  for j in range(len(s)):
    if s[j]=='(':
      h.append(h[-1]+1)
    else:
      h.append(h[-1]-1)
  H.append((min(h),h[-1]))
  
if sum([h[1] for h in H]) != 0:
  print('No')
  exit()

height = sum([H[i][-1] for i in range(N) if H[i][0]>=0])
H2 = [H[i] for i in range(N) if H[i][0]<0]
for i in range(len(H2)):
  if height + H2[i][0] < 0:
    print('No')
    exit()
  height += H2[i][-1]

print('Yes')

Submission status: Wrong Answer

Solution code:
import sys
from operator import itemgetter
N = int(input())
S = sys.stdin.read().split()
HT_high = []
HT_low = []
for s in S:
    t = 0
    h = 0
    for c in s:
        if c == "(":
            h += 1
        else:
            h -= 1
            if h < t:
                t = h
    if h >= 0:
        HT_high.append((h, t))
    else:
        HT_low.append((h, t))
HT_high.sort(key=itemgetter(1), reverse=True)
HT_low.sort(key=itemgetter(1))
h0 = 0
for h, t in HT_high + HT_low:
    if h0 + t < 0:
        print("No")
        exit()
    h0 += h
if h0 != 0:
    print("No")
else:
    print("Yes")

Submission status: Wrong Answer

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

for s in S:
    l = 0
    r = 0
    if s[0] == '(':
        l += 1
    else:
        r += 1
    if len(s) > 1:
        for num in range(1, len(s)):
            if s[num] == '(':
                l += 1
            elif s[num] == ')' and l > 0:
                l -= 1
            else:
                r += 1
    if l - r >= 0:
        up.append((l, r))
    else:
        down.append((l, r))
up.sort(key = lambda u: u[0])
down.sort(key = lambda d: (-1)*d[0])

LR = up + down
#print(LR)
count = 0
for l, r in LR:
    count -= r
    if count < 0:
        print('No')
        exit(0)
    count += l
if count != 0:
    print('No')
else:
    print('Yes')

Submission status: Wrong Answer

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

for s in S:
    l = 0
    r = 0
    if s[0] == '(':
        l += 1
    else:
        r += 1
    if len(s) > 1:
        for num in range(1, len(s)):
            if s[num] == '(':
                l += 1
            elif s[num] == ')' and l > 0:
                l -= 1
            else:
                r += 1
    if l - r >= 0:
        up.append((l, r))
    else:
        down.append((l, r))
sorted(up, key = lambda u: u[0])
sorted(down, key = lambda d: (-1)*d[0])

LR = up + down
#print(LR)
count = 0
for l, r in LR:
    count -= r
    if count < 0:
        print('No')
        exit(0)
    count += l
if count != 0:
    print('No')
else:
    print('Yes')

Submission status: Wrong Answer

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

for s in S:
    l = 0
    r = 0
    if s[0] == '(':
        l += 1
    else:
        r += 1
    if len(s) > 1:
        for num in range(1, len(s)):
            if s[num] == '(':
                l += 1
            elif s[num] == ')' and l != 0:
                l -= 1
            else:
                r += 1
    if l - r >= 0:
        up.append((l, r))
    else:
        down.append((l, r))
sorted(up, key = lambda u: u[1])
sorted(down, key = lambda d: (-1)*d[0])

LR = up + down
#print(LR)
count = 0
for l, r in LR:
    count -= r
    if count < 0:
        print('No')
        exit(0)
    count += l
if count != 0:
    print('No')
else:
    print('Yes')

Submission status: Wrong Answer

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

for s in S:
    l = 0
    r = 0
    if s[0] == '(':
        l += 1
    else:
        r += 1
    if len(s) > 1:
        for num in range(1, len(s)):
            if s[num] == '(':
                l += 1
            elif s[num] == ')' and l != 0:
                l -= 1
            else:
                r += 1
    if l != 0 or r != 0:
        if l - r >= 0:
            up.append((l, r))
        else:
            down.append((l, r))
sorted(up, key = lambda u: u[1])
sorted(down, key = lambda d: (-1)*d[1])

LR = up + down
count = 0
for l, r in LR:
    count -= r
    if count < 0:
        print('No')
        exit(0)
    count += l
if count != 0:
    print('No')
else:
    print('Yes')

Submission status: Wrong Answer

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

for s in S:
    sam = 0
    for c in s:
        if c == '(':
            sam += 1
        else:
            sam -= 1
    Sam.append(sam)

Sam.reverse()
print(Sam)
count = 0
for m in Sam:
    count += m
    if count < 0:
        print('No')
        exit(0)
if count != 0:
    print('No')
else:
    print('Yes')

Submission status: Wrong Answer

Solution code:
from operator import itemgetter
from itertools import chain


N = int(input())
inc = []
dec = []
for i in range(N):
    S = input()
    low = 0
    pos = 0

    for s in S:
        if s == '(':
            pos += 1
        else:
            pos -= 1
        low = min(low, pos)
    
    if pos >= 0:
        inc.append((low, pos))
    else:
        dec.append((low, pos))

inc.sort(key=itemgetter(0), reverse=True)
dec.sort(key=itemgetter(0), reverse=True)
height = 0
for i, (low, pos) in enumerate(chain(inc, dec)):
    if height + low < 0:
        ans = 'No'
        break
    height += pos
else:
    ans = 'Yes' if height == 0 else 'No'
print(ans)

Submission status: Wrong Answer

Solution code:
def score(a,b):
    if b-a >= 0:
        return a
    else:
        return 10**6+1-b

N = int(input())

A = [0]*N
B = [0]*N

for i in range(N):
    S = input()
    a = 0
    b = 0
    for j in range(len(S)):
        if S[j] == ')':
            a += 1
        else:
            a -= 1
        A[i] = max(A[i],a)

        if S[-j-1] == '(':
            b += 1
        else:
            b -= 1
        B[i] = max(B[i],b)

#print('S',S)
#print('A',A)
#print('B',B)

L = sorted(list(range(N)),key = lambda i:score(A[i],B[i]))

SA = 0
SB = 0

for i in range(N):
    if SB > A[L[i]]:
        SB += B[L[i]]
    else:
        SA += A[L[i]]-SB
        SB = B[L[i]]

if SA == 0 and SB == 0:
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
INF =  float("inf")
import bisect

def count(s):
    a = 0
    aa = 0
    b = 0
    bb = 0
    for i in range(len(s)):
        if s[i] == ")":
            if aa == 0:
                a = a + 1
            else:
                aa = aa - 1
        if s[i] == "(":
            aa = aa + 1
        if s[len(s)-1-i] == "(":
            if bb == 0:
                b = b + 1
            else:
                bb = bb - 1
        if s[len(s)-1-i] == ")":
            bb = bb + 1
    return [a, b]

N = int(input())

c = []
d = []
for i in range(N):
    s = input()
    e = count(s)
    if e[1] - e[0] >= 0: c.append(e)
    if e[0] - e[1] > 0: d.append(e)

c.sort(key=lambda x: x[0])
d.sort(key=lambda x: x[0])

c = c + d

f = 0
for cc in c:
    f = f - cc[0]
    if f < 0:
        print("No")
        sys.exit()
    f = f + cc[1]

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

Submission status: Wrong Answer

Solution code:
from operator import itemgetter
from itertools import chain


l = '('
r = ')'

N = int(input())
SL = []
SR = []
for i in range(N):
    S = input()
    L = len(S)

    suffix = L
    while 0 < suffix and S[suffix - 1] == l:
        suffix -= 1
    cntl = 0
    cntr = 0
    for i in range(suffix):
        if S[i] == l:
            cntl += 1
        else:
            cntr += 1
    A = max(0, cntr - cntl)

    prefix = 0
    while prefix < L and S[prefix] == r:
        prefix += 1
    cntl = 0
    cntr = 0
    for i in range(prefix, L):
        if S[i] == l:
            cntl += 1
        else:
            cntr += 1
    B = max(0, cntl - cntr)

    if A < B:
        SL.append((A, B))
    else:
        SR.append((A, B))


SL.sort(key=itemgetter(0))
SR.sort(key=itemgetter(1), reverse=True)
cnt = 0
for a, b in chain(SL, SR):
    cnt -= a
    if cnt < 0:
        print('No')
        exit()
    cnt += b
ans = 'Yes' if cnt == 0 else 'No'
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
d=[]
e=[]
for i in range(n):
    p=[0,0]
    s=input()
    for j in s:
        if j==")":
            if p[0]!=0:
                p[0]-=1
            else:
                p[1]+=1
        else:
            p[0]+=1
    if p[1]-p[0]>=0:
        d.append(p)
    else:
        e.append(p)
d=sorted(d,key=lambda x:x[1])
e=sorted(e,key=lambda x:-x[0])
s=d+e
q=0
for i,j in s:
    if q<j:
        print("No")
        exit()
    else:
        q=q-j+i
if q==0:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
import sys
import heapq

N = int(input())

data1 = []
data2 = []
for i in range(N):
    S = input()
    m = 0
    t = 0
    for j in range(len(S)):
        if S[j] == '(':
            t += 1
        else:
            t -= 1
        m = min(m,t)
    data1.append((-m,-t))

s = 0
for i in range(N):
    s -= data1[i][1]###-tなので注意

if s != 0:
    print('No')
    sys.exit()

heapq.heapify(data1)
###今dataは文字列中のスコア最小値が大きい順->トータルスコア最大値が大きい順にソートされている

det = 1
score = 0

###文字列内最小スコアが0以上のもの->いくら入れても問題ない
while data1 and data1[0][0] <= 0:###-tなので注意
    x = heapq.heappop(data1)
    #print((-x[0],-x[1]),score)
    score -= x[1]###-tなので注意

###文字列内最小スコアが負で、トータルスコアが正であるものを、文字列内最小スコアが大きい順に
while data1:
    x = heapq.heappop(data1)
    if x[1] < 0:###-tなので注意
        #print((-x[0],-x[1]),score)
        if score - x[0] < 0:###x[0] = -mなので注意
            det = -1
            break
        score -= x[1]###-tなので注意
    else:
        data2.append((-x[0],x[1]))
        ###(m,-t)文字列中スコア最小値が同じなら、トータルが大きい方をできるだけ先に入れたい

heapq.heapify(data2)

while data2:
    x = heapq.heappop(data2)
    #print((x[0],-x[1]),score)
    if score + x[0] < 0:
        det = -1
        break
    else:
        score -= x[1]###-tなので注意

if det == 1:
    print('Yes')
else:
    print('No')
###優先順位
###文字列中スコア最小値が正のもの（この場合は当然トータルも正）
###->トータルスコアが正のものを、文字列中スコア最小値が大きい順に
### （それがダメなら、文字列中スコア最小値がより小さいものは当然ダメ。スコアはこれから大きくなるので、厄介者は後にしておく方が無難）
###->トータルスコアが負のものを、文字列中スコア最小値が小さい順に
### （どうせスコアは大きくならないので、厄介者を先に処理しておく方が無難）

Submission status: Wrong Answer

Solution code:
import sys
import heapq

N = int(input())

data1 = []
data2 = []
for i in range(N):
    S = input()
    m = 0
    t = 0
    for j in range(len(S)):
        if S[j] == '(':
            t += 1
        else:
            t -= 1
        m = min(m,t)
    data1.append((-m,-t))

s = 0
for i in range(N):
    s -= data1[i][1]###-tなので注意

if s != 0:
    print('No')
    sys.exit()

heapq.heapify(data1)
###今dataは文字列中のスコア最小値が大きい順->トータルスコア最大値が大きい順にソートされている

det = 1
score = 0

###文字列内最小スコアが0以上のもの->いくら入れても問題ない
while data1 and data1[0][0] <= 0:###-tなので注意
    x = heapq.heappop(data1)
    print((-x[0],-x[1]),score)
    score -= x[1]###-tなので注意

###文字列内最小スコアが負で、トータルスコアが正であるものを、文字列内最小スコアが大きい順に
while data1:
    x = heapq.heappop(data1)
    if x[1] < 0:###-tなので注意
        print((-x[0],-x[1]),score)
        if score - x[0] < 0:###x[0] = -mなので注意
            det = -1
            break
        score -= x[1]###-tなので注意
    else:
        data2.append((-x[0],x[1]))
        ###(m,-t)文字列中スコア最小値が同じなら、トータルが大きい方をできるだけ先に入れたい

heapq.heapify(data2)

while data2:
    x = heapq.heappop(data2)
    print((x[0],-x[1]),score)
    if score + x[0] < 0:
        det = -1
        break
    else:
        score -= x[1]###-tなので注意

if det == 1:
    print('Yes')
else:
    print('No')
###優先順位
###文字列中スコア最小値が正のもの（この場合は当然トータルも正）
###->トータルスコアが正のものを、文字列中スコア最小値が大きい順に
### （それがダメなら、文字列中スコア最小値がより小さいものは当然ダメ。スコアはこれから大きくなるので、厄介者は後にしておく方が無難）
###->トータルスコアが負のものを、文字列中スコア最小値が小さい順に
### （どうせスコアは大きくならないので、厄介者を先に処理しておく方が無難）

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

N = int(input())

data = []
for i in range(N):
    S = input()
    m = 0
    t = 0
    for j in range(len(S)):
        if S[j] == '(':
            t += 1
        else:
            t -= 1
        m = min(m,t)
    data.append((m,t))

s = 0
for i in range(N):
    s += data[i][1]

if s != 0:
    print('No')
    sys.exit()

data.sort(reverse = True)
data = deque(data)
###今dataは文字列中のスコア最小値が大きい順->トータルスコア最大値が大きい順にソートされている

###
#print(data)
###

det = 1
score = 0

while data and data[0][1] >0:
    x = data.popleft()
    #print(x,score)
    score += x[1]

list(data).sort()
data = deque(data)

while data:
    x = data.popleft()
    #print(x,score)
    if score+x[0] < 0:
        det = -1
        break
    else:
        score += x[1]

if det == 1:
    print('Yes')
else:
    print('No')
###優先順位
###文字列中スコア最小値が正のもの（この場合は当然トータルも正）
###->トータルスコアが正のものを、文字列中スコア最小値が大きい順に
### （それがダメなら、文字列中スコア最小値がより小さいものは当然ダメ。スコアはこれから大きくなるので、厄介者は後にしておく方が無難）
###->トータルスコアが負のものを、文字列中スコア最小値が小さい順に
### （どうせスコアは大きくならないので、厄介者を先に処理しておく方が無難）

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

N = int(input())

data = []
for i in range(N):
    S = input()
    m = 0
    t = 0
    for j in range(len(S)):
        if S[j] == '(':
            t += 1
        else:
            t -= 1
        m = min(m,t)
    data.append((m,t))

s = 0
for i in range(N):
    s += data[i][1]

if s != 0:
    print('No')
    sys.exit()

data.sort(reverse = True)
data = deque(data)
###今dataは文字列中のスコア最小値が大きい順->トータルスコア最大値が大きい順にソートされている

###
print(data)
###

det = 1
score = 0

while data and data[0][1] >0:
    x = data.popleft()
    print(x,score)
    score += x[1]

list(data).sort()
data = deque(data)

while data:
    x = data.popleft()
    print(x,score)
    if score+x[0] < 0:
        det = -1
        break
    else:
        score += x[1]

if det == 1:
    print('Yes')
else:
    print('No')
###優先順位
###文字列中スコア最小値が正のもの（この場合は当然トータルも正）
###->トータルスコアが正のものを、文字列中スコア最小値が大きい順に
### （それがダメなら、文字列中スコア最小値がより小さいものは当然ダメ。スコアはこれから大きくなるので、厄介者は後にしておく方が無難）
###->トータルスコアが負のものを、文字列中スコア最小値が小さい順に
### （どうせスコアは大きくならないので、厄介者を先に処理しておく方が無難）

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

N = int(input())

data = []
for i in range(N):
    S = input()
    m = 0
    t = 0
    for j in range(len(S)):
        if S[j] == '(':
            t += 1
        else:
            t -= 1
        m = min(m,t)
    data.append((m,t))

s = 0
for i in range(N):
    s += data[i][1]

if s != 0:
    print('No')
    sys.exit()

data.sort(reverse = True)
data = deque(data)
###今dataは文字列中のスコア最小値が大きい順->トータルスコア最大値が大きい順にソートされている

det = 1
score = 0

while data:
    x = data.popleft()
    if score+x[0] < 0:
        det = -1
        break
    else:
        score += x[1]

if det == 1:
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

Solution code:
import sys
N = int(input())
S = [list(input()) for i in range(N)]
T = []
for i in range(N):
    T_i = [0]
    for j in S[i]:
        if j == '(':
            T_i.append(T_i[-1]+1)
        else:
            T_i.append(T_i[-1]-1)
        T_i[0] = min(T_i[1:])
    T.append(T_i)

T.sort(reverse=True)
ans = 0
for i in range(N):
    if ans + T[i][0] < 0:
        print('No')
        sys.exit()
    ans += T[i][-1]
    

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

Submission status: Wrong Answer

Solution code:
#from collections import deque,defaultdict
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7
#R = 998244353

def ddprint(x):
  if DBG:
    print(x)

n = inn()
ls = []
rs = []
z = 0
for i in range(n):
    ss = ins()
    l = r = 0
    for c in ss:
        if c=='(':
             l += 1
        else:
            if l>0:
                l -= 1
            else:
                r += 1
    rr = r
    l = r = 0
    for j in range(len(ss)-1,-1,-1):
        c = ss[j]
        if c==')':
             r += 1
        else:
            if r>0:
                r -= 1
            else:
                l += 1
    r = rr
    if l>r:
        ls.append((r,l-r))
    elif l<r:
        rs.append((l,r-l))
    else:
        z = max(z,r)
ls.sort()
rs.sort()
#ddprint(ls)
#ddprint(rs)
#ddprint(z)
l = r = 0
for rr,ll in ls:
    if l<rr:
        print('No')
        exit()
    l = l-rr+ll
for ll,rr in rs:
    if r<ll:
        print('No')
        exit()
    r = r-ll+rr
print('Yes' if l==r>=z else 'No')

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
import numba
from numba import njit
i8 = numba.int64

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@njit((i8[:], ), cache=True)
def main(S):
    N = len(S)
    L = np.empty(N, np.int64)
    R = np.empty(N, np.int64)

    x = y = 0
    n = 0
    for s in S:
        if s == 0:
            y += 1
        elif s == 1:
            if y:
                y -= 1
            else:
                x += 1
        else:
            L[n], R[n] = x, y
            n += 1
            x = y = 0

    L, R = L[:n], R[:n]
    L1, R1 = L[L > R], R[L > R]
    L2, R2 = L[L <= R], R[L <= R]

    ind = L1.argsort()
    L1, R1 = L1[ind], R1[ind]

    ind = R2.argsort()[::-1]
    L2, R2 = L2[ind], R2[ind]

    L = np.concatenate((L1, L2))
    R = np.concatenate((R1, R2))

    n = 0
    for i in range(len(L)):
        if n < R[i]:
            return False
        n += L[i] - R[i]
    return n == 0

N = int(readline())
S = np.array(list(read()), np.int64) - ord('(')

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

Submission status: Wrong Answer

Solution code:
#import numpy as np
#import math
#from decimal import *
#from numba import njit

#@njit
def main():
    N = int(input())
    A = []
    for i in range(N):
        string = input()
        m = 0
        s = 0
        for c in string:
            if c == '(':
                s += 1
            else:
                s -= 1
                m = min(m, s)
        A += [m,s],
    
    A = sorted(A, key=lambda x: (x[0],x[1]), reverse=True)
    s = 0
    for i in range(len(A)):
        if A[i][0] + s < 0 or s + A[i][1] < 0:
            print('No')
            return
        s += A[i][1]
    
    if s == 0:
        print('Yes')
    else:
        print('No')

main()

Submission status: Wrong Answer

Solution code:
#import numpy as np
#import math
#from decimal import *
#from numba import njit

#@njit
def main():
    N = int(input())
    A = []
    for i in range(N):
        string = input()
        m = 0
        s = 0
        for c in string:
            if c == '(':
                s += 1
            else:
                s -= 1
                m = min(m, s)
        A += [m,s],
    
    A = sorted(A, key=lambda x: (x[0],x[1]), reverse=True)
    s = 0
    for i in range(len(A)):
        if A[i][0] + s < 0 or s + A[i][1] < 0:
            return
        s += A[i][1]
    
    if s == 0:
        print('Yes')
    else:
        print('No')

main()

Submission status: Wrong Answer

Solution code:
#import numpy as np
#import math
#from decimal import *
#from numba import njit

#@njit
def main():
    N = int(input())
    A = []
    for i in range(N):
        string = input()
        m = 0
        s = 0
        for c in string:
            if c == '(':
                s += 1
            else:
                s -= 1
                m = min(m, s)
        A += [m,s],
    
    A = sorted(A, key=lambda x: (x[0],x[1]), reverse=True)
    s = 0
    for i in range(len(A)):
        if A[i][0] < s or s +A[i][1] < 0:
            print('No')
            return
        s += A[i][1]
    
    if s == 0:
        print('Yes')
    else:
        print('No')

main()

Submission status: Wrong Answer

Solution code:
#import numpy as np
#import math
#from decimal import *
#from numba import njit

#@njit
def main():
    N = int(input())
    A = []
    for i in range(N):
        string = input()
        m = 0
        s = 0
        for c in string:
            if c == '(':
                s += 1
            else:
                s -= 1
                m = min(m, s)
        A += [m,s],
    
    A = sorted(A, key=lambda x: (x[0],x[1]), reverse=True)
    s = 0
    for i in range(len(A)):
        s += A[i][1]
        if s < 0:
            print('No')
            return
    
    if s == 0:
        print('Yes')
    else:
        print('No')

main()

Submission status: Wrong Answer

Solution code:
#import numpy as np
#import math
#from decimal import *
#from numba import njit

#@njit
def main():
    N = int(input())
    A = []
    for i in range(N):
        string = input()
        m = 0
        s = 0
        for c in string:
            if c == '(':
                s += 1
            else:
                s -= 1
                m = min(m, s)
        A += [m,s],
    
    A = sorted(A, key=lambda x: (x[0],x[1]), reverse=True)
    s = 0
    for i in range(len(A)):
        s += A[i][1]
        if s < 0:
            print('No')
            return
    
    print('Yes')

main()

Submission status: Wrong Answer

Solution code:
import numpy as np
#import math
#from decimal import *
#from numba import njit

#@njit
def main():
    N = int(input())
    A = np.zeros((N,2), dtype='int16')
    for i in range(N):
        string = input()
        m = 0
        s = 0
        for c in string:
            if c == '(':
                s += 1
            else:
                s -= 1
                m = max(m, -s)
        A[i] = [m,s]
    
    A = A[np.argsort(A[:,1])]
    A = A[np.argsort(A[:,0])][::-1]

    s = 0
    while len(A) > 0:
        index = np.where(A[:,0] >= s)[0]
        if len(index) <= 0:
            print('No')
            return
        s += A[index][0][1]
        if s < 0:
            print('No')
            return
        A = np.delete(A, index[0], 0)
        #A[index][0][0] = 10**6+1
    
    print('Yes')

main()

Submission status: Wrong Answer

Solution code:
import numpy as np
#import math
#from decimal import *
#from numba import njit

#@njit
def main():
    N = int(input())
    A = np.zeros((N,2), dtype='int16')
    for i in range(N):
        string = input()
        m = 0
        s = 0
        for c in string:
            if c == '(':
                s += 1
            else:
                s -= 1
                m = max(m, -s)
        A[i] = [m,s]
    
    A = A[np.argsort(A[:,1])]
    A = A[np.argsort(A[:,0])][::-1]
    #print(A)

    s = 0
    for _ in range(N):
        index = np.where(A[:,0] >= s)[0]
        if len(index) <= 0:
            print('No')
            return
        s += A[index][0][1]
        #A = np.delete(A, index[0], 0)
        A[index][0][0] = 10**6+1
    
    print('Yes')

main()