Problem:


Score : 600 points

Problem Statement

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

An empty string;

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

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

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

Constraints

1 \leq N \leq 10^6

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

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

Input

Input is given from Standard Input in the following format:

N
S_1
:
S_N

Output

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

Sample Input 1

2
)
(()

Sample Output 1

Yes

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

Sample Input 2

2
)(
()

Sample Output 2

No

Sample Input 3

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

Sample Output 3

Yes

Sample Input 4

3
(((
)
)

Sample Output 4

No



Sample input:
2
)
(()


Sample output:
Yes

Submission status: Wrong Answer

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

LRM = []
for s in S:
    left, right, min_bracket = 0, 0, 0
    tmp = 0
    for ss in s:
        if ss == "(":
            left += 1
            tmp += 1
        else:
            right += 1
            tmp -= 1
        min_bracket = min(tmp, min_bracket)
    LRM.append([left, right, min_bracket])
#print(LRM)

l_sum, r_sum = 0, 0
for l, r, m in LRM:
    l_sum += l
    r_sum += r
if l_sum != r_sum:
    print("No")
    exit()
    
plus, plus_m, minus = [], [], []
for i, (l, r, m) in enumerate(LRM):
    if m >= 0:
        plus.append([l, r, m, i])
    else:
        if l > r:
            plus_m.append([l, r, m, i])
        else:
            minus.append([l, r, m, i])
plus_m.sort(key = lambda x: x[1])
minus.sort(key = lambda x: x[2])

cnt = 0
for l, r, m, i in plus + plus_m + minus:
    #print(S[i])
    for s in S[i]:
        if s == "(":
            cnt += 1
        else:
            cnt -= 1
        if cnt < 0:
            print("No")
            exit()
print("Yes")

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict
from itertools import combinations, permutations, combinations_with_replacement
from itertools import accumulate
from math import ceil, sqrt, pi

MOD = 10 ** 9 + 7
INF = 10 ** 18

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

LRM = []
for s in S:
    left, right, min_bracket = 0, 0, 0
    tmp = 0
    for ss in s:
        if ss == "(":
            left += 1
            tmp += 1
        else:
            right += 1
            tmp -= 1
        min_bracket = min(tmp, min_bracket)
    LRM.append([left, right, min_bracket])
#print(LRM)

l_sum, r_sum = 0, 0
for l, r, m in LRM:
    l_sum += l
    r_sum += r
if l_sum != r_sum:
    print("No")
    exit()
    
plus, plus_m, minus = [], [], []
for i, (l, r, m) in enumerate(LRM):
    if m == 0:
        plus.append([l, r, m, i])
    else:
        if l >= r:
            plus_m.append([l, r, m, i])
        else:
            minus.append([l, r, m, i])
plus_m.sort(key = lambda x: x[1])
minus.sort(key = lambda x: x[2])

cnt = 0
for l, r, m, i in plus + plus_m + minus:
    #print(S[i])
    for s in S[i]:
        if s == "(":
            cnt += 1
        else:
            cnt -= 1
        if cnt < 0:
            print("No")
            exit()
print("Yes")

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys
sys.setrecursionlimit(10**7)
from pprint import pprint as pp
from pprint import pformat as pf
# @pysnooper.snoop()
#import pysnooper # debug

import math
#from sortedcontainers import SortedList, SortedDict, SortedSet # no in atcoder
import bisect

class Part:

    def __init__(self, string):
        self.slope, self.floor = self.calc_slope_floor(string)

    def __repr__(self):
        return "s{} f{}".format(self.slope, self.floor)

    def __lt__(self, other):
        if self.floor > other.floor:
            return True
        if self.slope > self.slope:
            return True
        return False

    @staticmethod
    def calc_slope_floor(string):
        slope = 0
        floor = 0
        for c in string:
            if c == '(':
                slope += 1
            else:
                slope -= 1
            floor = min(floor, slope)
        return slope, floor

    def flip(self):
        self.slope *= -1
        self.floor += self.slope

    def catenate(self, other):
        assert(self.slope >= 0)
        if self.slope < abs(other.floor):
            return False
        self.slope += other.floor
        # self.floor is not needed

def sum_slope(parts):
    s = 0
    for p in parts:
        s += p.slope
    return s

def calc_flat_floor(flat):
    floor = 0
    for f in flat:
        floor = min(floor, f.floor)
    return floor

def enable(parts):
    parts = sorted(parts)
    #print('parts') # debug
    #print(parts) # debug
    chain = Part("")
    for p in parts:
        flg = chain.catenate(p)
        if flg == False:
            return False
    return True



def solve(up, down, flat):
    up_slope = sum_slope(up)
    down_slope = sum_slope(down)
    if up_slope != down_slope:
        return False
    flat_floor = calc_flat_floor(flat)
    #print('up_slope') # debug
    #print(up_slope) # debug
    #print('flat_floor') # debug
    #print(flat_floor) # debug
    if up_slope < abs(flat_floor):
        return False
    if not enable(up):
        return False
    if not enable(down):
        return False
    return True


if __name__ == '__main__':
    n = int(input())
    up = []
    down = []
    flat = []
    for _ in range(n):
        s = input()
        p = Part(s)
        if p.slope > 0:
            up.append(p)
        elif p.slope < 0:
            p.flip()
            down.append(p)
        else:
            flat.append(p)
    ans = solve(up, down, flat)
    if ans:
        print("Yes")
    else:
        print("No")


    #print('\33[32m' + 'end' + '\033[0m') # debug

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6) #再帰関数の上限
import math
from copy import copy, deepcopy
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque 
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする


def input(): return sys.stdin.readline()[:-1]
def printl(li): print(*li, sep="\n")
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)

def main():
    mod = 10**9+7
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    N = int(input())
    #N, K = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    l=[]
    for i in range(N):
        S=input()
        lmin=0
        tot=0
        for s in S:
            if s=='(':
                tot+=1
            else:
                tot-=1
                lmin=min(lmin,tot)
        heappush(l,[-lmin,tot])
    tot=0
    cmin=0

    while len(l):
        lmin,ltot=heappop(l)
        lmin=-lmin
        cmin=tot+lmin
        tot+=ltot
        if cmin<0:
            print('No')
            exit()
    if tot==0:
        print('Yes')
    else:
        print('No')

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from operator import itemgetter
N=int(input())
S=[input() for _ in range(N)]
T=[[0, 0] for _ in range(N)]
 
for i in range(N):
  s=S[i]
  l=len(s)
  c=0
  for j in range(l):
    if s[j]=='(':
      c+=1
    else:
      c-=1
      if c<T[i][1]:
        T[i][1]=c
  T[i][0]=c
        
A=[T[i] for i in range(N) if T[i][0]>0]
B=[T[i] for i in range(N) if T[i][0]<=0]
 
A=sorted(A, key=itemgetter(1), reverse=True)
B=sorted(B, key=lambda x: (x[1], -x[0]))
 
h=0
la=len(A)
lb=len(B)
 
i=0
for tmp in A:
  if h+tmp[1]<0:
    print('No')
    exit()
  else:
    h+=tmp[0]
  
for tmp in B:
  if h+tmp[1]<0:
    print('No')
    exit()
  else:
    h+=tmp[0]
  
if h==0:
  print('Yes')
else:
  print('No')

Submission status: Wrong Answer

Solution code:
def result(m, b):
    sum1 = m
    resmin = m
    for i in range(len(b)):
        resmin += b[i][0]
        if resmin < 0:
            return -1
        else:
            resmin += b[i][1] - b[i][0]
    for i in range(len(b)):
        sum1 += b[i][1]
    if sum1 != 0:
        return -1
    return 0
n = int(input().strip('\n'))
resmin = 10 ** 7
set_pos = []
set_neg = []
for i in range(n):
    a = input().strip('\n')
    loc_min = 10 ** 7
    total = 0
    flag = True
    tmp = 0
    for j in range(len(a)):
        if a[j] == '(':
            tmp += 1
        else:
            tmp -= 1
        if tmp < loc_min:
            loc_min = tmp
    total = tmp
    if total >= 0:
        set_pos.append((loc_min, total))
    else:
        set_neg.append((loc_min, total))
total_pos = 0
set_pos = sorted(set_pos, key = lambda l: l[0], reverse = True)
for elem in set_pos:
    if total_pos + elem[0] < 0:
        flag = False
    total_pos += elem[1]   
b = sorted(set_neg, key = lambda l: l[1] - l[0], reverse = True)
#print(b)
print(set_pos, b)
res = result(total_pos, b)
print('No' if (res == -1 or not flag) else 'Yes')

Submission status: Wrong Answer

Solution code:
N = int((input()))
C_p = []
C_m = []
for i in range(N):
    kakko = input()
    temp = 0
    temp_min = 0
    for s in kakko:
        if s == "(":
            temp += 1
        else:
            temp -= 1
            temp_min = min(temp, temp_min)
    if temp >= 0:
        C_p.append((temp_min, temp))
    else:
        C_m.append((temp_min, temp))
C_p.sort(reverse=True)

flag = 0
final = 0
for l, f in C_p:
    if final + l < 0:
        flag = 1
    final += f

C_m.sort()

for l, f in C_m:
    if final + l < 0:
        flag = 1
    final += f
    
if final != 0:
    flag = 1

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

Submission status: Wrong Answer

Solution code:
from operator import itemgetter
N=int(input())
S=[input() for _ in range(N)]
T=[[0, 0] for _ in range(N)]
 
for i in range(N):
  s=S[i]
  l=len(s)
  c=0
  for j in range(l):
    if s[j]=='(':
      c+=1
    else:
      c-=1
      if c<T[i][1]:
        T[i][1]=c
  T[i][0]=c
        
A=[T[i] for i in range(N) if T[i][0]>=0]
B=[T[i] for i in range(N) if T[i][0]<0]
 
A=sorted(A, key=itemgetter(1), reverse=True)
B=sorted(B, key=lambda x: x[1])
 
h=0
la=len(A)
lb=len(B)
 
i=0
for tmp in A:
  if h+tmp[1]<0:
    print('No')
    exit()
  else:
    h+=tmp[0]
  
for tmp in B:
  if h+tmp[1]<0:
    print('No')
    exit()
  else:
    h+=tmp[0]
  
if h==0:
  print('Yes')
else:
  print('No')

Submission status: Wrong Answer

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

for i in range(N):
  s=S[i]
  l=len(s)
  c=0
  for j in range(l):
    if s[j]=='(':
      c+=1
    else:
      c-=1
      if c<T[i][1]:
        T[i][1]=c
  T[i][0]=c

A=[T[i] for i in range(N) if T[i][0]>=0]
B=[T[i] for i in range(N) if T[i][0]<0]

A=sorted(A, key=itemgetter(1), reverse=True)
B=sorted(B, key=itemgetter(1))

h=0
la=len(A)
lb=len(B)

i=0
for tmp in A:
  if h+tmp[1]<0:
    print('No')
    exit()
  else:
    h+=tmp[0]
    
for tmp in B:
  if h+tmp[1]<0:
    print('No')
    exit()
  else:
    h+=tmp[0]
    
if h==0:
  print('Yes')
else:
  print('No')

Submission status: Wrong Answer

Solution code:
N = int((input()))
C_p = []
C_m = []
for i in range(N):
    kakko = input()
    temp = 0
    temp_min = 0
    for s in kakko:
        if s == "(":
            temp += 1
        else:
            temp -= 1
            temp_min = min(temp, temp_min)
    if temp >= 0:
        C_p.append((temp_min, temp))
    else:
        C_m.append((temp_min, temp))
C_p.sort(reverse=True)

flag = 0
final = 0
for l, f in C_p:
    if final + l < 0:
        flag = 1
    final += f

C_m.sort(reverse=True)

for l, f in C_m:
    if final + l < 0:
        flag = 1
    final += f
    
if final != 0:
    flag = 1

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

Submission status: Wrong Answer

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

def bracket(s):
    left, right = 0, 0
    tmp, min_tmp = 0, 0
    for ss in s:
        if ss == ")":
            tmp -= 1
            right += 1
        else:
            tmp += 1
            left += 1
        min_tmp = min(min_tmp, tmp)
    return [-min_tmp, left, right]

lst = []
for s in S:
    lst.append(bracket(s))
#print(lst)

left_sum = 0
right_sum = 0
for mt, l, r in lst:
    left_sum += l
    right_sum += r
#print(left_sum, right_sum)

if left_sum != right_sum:
    print("No")
    exit()
    
lst.sort()
cnt = 0
for mt, l, r in lst:
    if cnt - mt < 0:
        print("No")
        exit()
    cnt = cnt + l - r

print("Yes")

Submission status: Wrong Answer

Solution code:
def result(m, b):
    sum1 = m
    resmin = m
    for i in range(len(b)):
        resmin += b[i][0]
        if resmin < 0:
            return -1
        else:
            resmin += b[i][1] - b[i][0]
    for i in range(len(b)):
        sum1 += b[i][1]
    if sum1 != 0:
        return -1
    return 0
n = int(input())
resmin = 10 ** 7
set_pos = []
set_neg = []
for i in range(n):
    a = input().strip('\n')
    loc_min = 10 ** 7
    total = 0
    flag = True
    tmp = 0
    for j in range(len(a)):
        if a[j] == '(':
            tmp += 1
        else:
            tmp -= 1
        if tmp < loc_min:
            loc_min = tmp
    total = tmp
    if total >= 0:
        set_pos.append((loc_min, total))
    else:
        set_neg.append((loc_min, total))
total_pos = 0
set_pos = sorted(set_pos, key = lambda l: l[0], reverse = True)
for elem in set_pos:
    if total_pos + elem[0] < 0:
        flag = False
    total_pos += elem[1]   
b = sorted(set_neg, key = lambda l: (l[0], -l[1]), reverse = False)
#print(b)
res = result(total_pos, b)
print('No' if (res == -1 or not flag) else 'Yes')

Submission status: Wrong Answer

Solution code:
from bisect import bisect_right

N = int(input())
arr = []
arr2 = []
for _ in range(N):
    tmp = mi = 0
    for c in input():
        tmp += 1 if c == '(' else -1
        mi = mi if mi < tmp else tmp
    arr.append((-mi, tmp)) # 最下点、終点の高さ
    arr2.append(-mi)
# 最下点の高さが高い順にソートしておく
arr.sort()
arr2.sort()

# セグメント木(範囲内で、終点の高さが最大の要素のindexを持つ)
BL = (N-1).bit_length()
WIDTH = 2**BL
bufsize = 2**(BL+1) - 1
BASE = bufsize - WIDTH
buf = [None] * bufsize

def compare(i1, i2):
    if i1 is None or i2 is None:
        return i1 if i2 is None else i2
    return i1 if arr[i1][1] > arr[i2][1] else i2

def update(i, x):
    arr[i] = x
    buf[BASE+i] = None if x is None else i
    i += BASE
    i = (i-1) // 2
    while i >= 0:
        buf[i] = compare(buf[2*i+1], buf[2*i+2])
        i = (i-1) // 2

# [q_left, q_right]
def search(l, width, i, q_left, q_right):
    r = l + width - 1
    if q_right < l or r < q_left:
        return None
    if q_left <= l and r <= q_right:
        return buf[i]
    nwidth = width // 2
    c1 = search(l, nwidth, 2*i+1, q_left, q_right)
    c2 = search(l+nwidth, nwidth, 2*i+2, q_left, q_right)
    return compare(c1, c2)

for i, a in enumerate(arr):
    update(i, a)

tmp = 0
for _ in range(N):
    # 現在の状態に繋げられる(最下点が0を下回らない)範囲を探す
    right = bisect_right(arr2, tmp)
    if right == 0:
        break
    # 範囲内で終点の高さが最大になるものを探す
    idx = search(0, WIDTH, 0, 0, right-1)
    if idx is None:
        break
    # 状態を更新
    tmp += arr[idx][1]
    update(idx, None) 
else:
    if tmp == 0:
        print('Yes')
        exit()
print('No')

Submission status: Wrong Answer

Solution code:
from bisect import bisect_right

N = int(input())
BL = (N-1).bit_length()
WIDTH = pow(2, BL)
bufsize = pow(2, BL+1) - 1
base = bufsize - WIDTH

buf = [None] * bufsize
arr = []

def compare(i1, i2):
    if i1 is None or i2 is None:
        return i1 if i2 is None else i2
    v1, v2 = arr[i1][1], arr[i2][1]
    if v1 > v2:
        return i1
    else:
        return i2

def update(i, x):
    arr[i] = x
    buf[base+i] = None if x is None else i
    i += base
    i = (i-1) // 2
    while i >= 0:
        buf[i] = compare(buf[2*i+1], buf[2*i+2])
        i = (i-1) // 2


# [q_left, q_right]
def search(l, width, i, q_left, q_right):
    if q_right < l or l + width - 1 < q_left:
        return None
    if q_left <= l and l + width - 1 <= q_right:
        return buf[i]
    nwidth = width // 2
    c1 = search(l, nwidth, 2*i+1, q_left, q_right)
    c2 = search(l+nwidth, nwidth, 2*i+2, q_left, q_right)
    return compare(c1, c2)

arr2 = []
for _ in range(N):
    tmp = mi = 0
    for c in input():
        if c == '(':
            tmp += 1
        else:
            tmp -= 1
        mi = mi if mi < tmp else tmp
    arr.append((-mi, tmp))
    arr2.append(-mi)

arr.sort()
arr2.sort()
for i, a in enumerate(arr):
    update(i, a)

INF = float('inf')
tmp = 0
for _ in range(N):
    right = bisect_right(arr2, tmp)
    if right == 0:
        break
    idx = search(0, WIDTH, 0, 0, right-1)
    if idx is None:
        break
    tmp += arr[idx][1]
    update(idx, None) 
else:
    if tmp == 0:
        print('Yes')
        exit()
print('No')

Submission status: Wrong Answer

Solution code:
N = int(input())

S1 = []
S2 = []
for i in range(N):
    T = input()
    m, tmp = 0, 0    
    for s in T:
        if s == '(':
            tmp += 1
        else:
            tmp -= 1
        m = min(m, tmp)
    if tmp > 0:
        S1.append((m,tmp))
    else:
        S2.append((m,tmp))

S1.sort(reverse=True)
S2.sort()

inter, end = 0, 0
flag = True
for t in S1:
    a, b = t
    inter = end + a
    end = end + b
    # print(inter, end)
    if inter < 0 or end < 0:
        flag = False
        break

end1 = end

for t in S2:
    a, b = t
    inter = end + a
    end = end + b
    # print(inter, end)
    if inter < 0 or end < 0:
        flag = False
        break        

end2 = end

if flag:
    if end2 != 0:
        print('No')
    else:
        print('Yes')
else:
    print('No')

Submission status: Wrong Answer

Solution code:
from bisect import bisect_right

N = int(input())

BL = (N-1).bit_length()
WIDTH = pow(2, BL)
bufsize = pow(2, BL+1) - 1
base = bufsize - WIDTH

buf = [None] * bufsize

arr = []

def compare(i1, i2):
    if i1 is None or i2 is None:
        return i1 if i2 is None else i2
    v1, v2 = arr[i1][1], arr[i2][1]
    if v1 > v2:
        return i1
    else:
        return i2

def update(i, x):
    arr[i] = x
    buf[base+i] = None if x is None else i
    i += base
    i = (i-1) // 2
    while i >= 0:
        buf[i] = compare(buf[2*i+1], buf[2*i+2])
        i = (i-1) // 2


# [q_left, q_right]
def search(l, width, i, q_left, q_right):
    if q_right < l or l + width - 1 < q_left:
        return None
    if q_left <= l and l + width - 1 <= q_right:
        return buf[i]
    nwidth = width // 2
    c1 = search(l, nwidth, 2*i+1, q_left, q_right)
    c2 = search(l+nwidth, nwidth, 2*i+2, q_left, q_right)
    return compare(c1, c2)

for _ in range(N):
    tmp = mi = 0
    for c in input():
        if c == '(':
            tmp += 1
        else:
            tmp -= 1
        mi = mi if mi < tmp else tmp
    arr.append((-mi, tmp))

arr.sort()
for i, a in enumerate(arr):
    update(i, a)

INF = float('inf')
tmp = 0
for _ in range(N):
    right = bisect_right(arr, (tmp, INF))
    if right == 0:
        break
    idx = search(0, WIDTH, 0, 0, right-1)
    if idx is None:
        break
    tmp += arr[idx][1]
    if tmp < 0:
        break
    update(idx, (arr[idx][0], -INF))
else:
    if tmp == 0:
        print('Yes')
        exit()
print('No')

Submission status: Wrong Answer

Solution code:
from bisect import bisect_right

N = int(input())

BL = (N-1).bit_length()
WIDTH = pow(2, BL)
bufsize = pow(2, BL+1) - 1
base = bufsize - WIDTH

buf = [None] * bufsize

arr = []

def compare(i1, i2):
    if i1 is None or i2 is None:
        return i1 if i2 is None else i2
    v1, v2 = arr[i1][1], arr[i2][1]
    if v1 > v2:
        return i1
    else:
        return i2

def update(i, x):
    arr[i] = x
    buf[base+i] = None if x is None else i
    i += base
    i = (i-1) // 2
    while i >= 0:
        buf[i] = compare(buf[2*i+1], buf[2*i+2])
        i = (i-1) // 2


# [q_left, q_right]
def search(l, width, i, q_left, q_right):
    if q_right < l or l + width - 1 < q_left:
        return None
    if q_left <= l and l + width - 1 <= q_right:
        return buf[i]
    nwidth = width // 2
    c1 = search(l, nwidth, 2*i+1, q_left, q_right)
    c2 = search(l+nwidth, nwidth, 2*i+2, q_left, q_right)
    return compare(c1, c2)

for _ in range(N):
    tmp = mi = 0
    for c in input():
        if c == '(':
            tmp += 1
        else:
            tmp -= 1
        mi = mi if mi < tmp else tmp
    arr.append((mi, tmp))

arr.sort(reverse=True)
for i, a in enumerate(arr):
    update(i, a)

INF = float('inf')
tmp = 0
for _ in range(N):
    right = bisect_right(arr, (tmp, -INF))
    if right == 0:
        break
    idx = search(0, WIDTH, 0, 0, right-1)
    if idx is None:
        break
    tmp += arr[idx][1]
    if tmp < 0:
        break
    update(idx, (arr[idx][0], -INF))
else:
    if tmp == 0:
        print('Yes')
        exit()
print('No')

Submission status: Wrong Answer

Solution code:
from bisect import bisect_right

N = int(input())

BL = (N-1).bit_length()
WIDTH = pow(2, BL)
bufsize = pow(2, BL+1) - 1
base = bufsize - WIDTH

buf = [None] * bufsize

arr = []

def compare(i1, i2):
    if i1 is None or i2 is None:
        return i1 if i2 is None else i2
    v1, v2 = arr[i1][1], arr[i2][1]
    if v1 > v2:
        return i1
    else:
        return i2

def update(i, x):
    arr[i] = x
    buf[base+i] = None if x is None else i
    i += base
    i = (i-1) // 2
    while i >= 0:
        buf[i] = compare(buf[2*i+1], buf[2*i+2])
        i = (i-1) // 2


# [q_left, q_right]
def search(l, width, i, q_left, q_right):
    if q_right < l or l + width - 1 < q_left:
        return None
    if q_left <= l and l + width - 1 <= q_right:
        return buf[i]
    nwidth = width // 2
    c1 = search(l, nwidth, 2*i+1, q_left, q_right)
    c2 = search(l+nwidth, nwidth, 2*i+2, q_left, q_right)
    return compare(c1, c2)

for _ in range(N):
    tmp = mi = 0
    for c in input():
        if c == '(':
            tmp += 1
        else:
            tmp -= 1
        mi = mi if mi < tmp else tmp
    arr.append((mi, tmp))

arr.sort(reverse=True)
for i, a in enumerate(arr):
    update(i, a)

INF = float('inf')
tmp = 0
for _ in range(N):
    right = bisect_right(arr, (tmp, INF))
    if right == 0:
        break
    idx = search(0, WIDTH, 0, 0, right-1)
    if idx is None:
        break
    tmp += arr[idx][1]
    if tmp < 0:
        break
    update(idx, (arr[idx][0], -INF))
else:
    if tmp == 0:
        print('Yes')
        exit()
print('No')

Submission status: Wrong Answer

Solution code:
from bisect import bisect_right

N = int(input())

BL = (N-1).bit_length()
WIDTH = pow(2, BL)
bufsize = pow(2, BL+1) - 1
base = bufsize - WIDTH

buf = [None] * bufsize

arr = []

def compare(i1, i2):
    if i1 is None or i2 is None:
        return i1 if i2 is None else i2
    v1, v2 = arr[i1][1], arr[i2][1]
    if v1 > v2:
        return i1
    else:
        return i2

def update(i, x):
    arr[i] = x
    buf[base+i] = None if x is None else i
    i += base
    i = (i-1) // 2
    while i >= 0:
        buf[i] = compare(buf[2*i+1], buf[2*i+2])
        i = (i-1) // 2


# [q_left, q_right]
def search(l, width, i, q_left, q_right):
    if q_right < l or l + width - 1 < q_left:
        return None
    if q_left <= l and l + width - 1 <= q_right:
        return buf[i]
    nwidth = width // 2
    c1 = search(l, nwidth, 2*i+1, q_left, q_right)
    c2 = search(l+nwidth, nwidth, 2*i+2, q_left, q_right)
    return compare(c1, c2)

for _ in range(N):
    tmp = mi = 0
    for c in input():
        if c == '(':
            tmp += 1
        else:
            tmp -= 1
        mi = mi if mi < tmp else tmp
    arr.append((mi, tmp))

arr.sort(reverse=True)
for i, a in enumerate(arr):
    update(i, a)

INF = float('inf')
tmp = 0
for _ in range(N):
    right = bisect_right(arr, (tmp, INF))
    if right == 0:
        break
    idx = search(0, WIDTH, 0, 0, right-1)
    if idx is None:
        break
    tmp += arr[idx][1]
    if tmp < 0:
        break
    update(idx, (-INF, -INF))
else:
    print('Yes')
    exit()
print('No')

Submission status: Wrong Answer

Solution code:
# F - Bracket Sequencing

N = int(input())
L = []
R = []
for _ in range(N):
    S = list(str(input()))
    d = 0
    min_d = 0
    for s in S:
        if s == '(':
            d += 1
        else:
            d -= 1
            min_d = min(min_d, d)
    if d >= 0:
        L.append((d, min_d))
    else:
        R.append((d, min_d))

L.sort(key=lambda x: x[0], reverse=True)
L.sort(key=lambda x: x[1], reverse=True)
R.sort(key=lambda x: x[0], reverse=True)
R.sort(key=lambda x: x[1])

ans = 'Yes'
now = 0
for d, min_d in L:
    if now + min_d < 0:
        ans = 'No'
        break
    else:
        now += d

for d, min_d in R:
    if now + min_d < 0:
        ans = 'No'
        break
    else:
        now += d

if now != 0:
    ans = 'No'

print(ans)

Submission status: Wrong Answer

Solution code:
# F - Bracket Sequencing

N = int(input())
L = []
R = []
for _ in range(N):
    S = list(str(input()))
    d = 0
    min_d = 0
    for s in S:
        if s == '(':
            d += 1
        else:
            d -= 1
            min_d = min(min_d, d)
    if d >= 0:
        L.append((d, min_d))
    else:
        R.append((d, min_d))

L.sort(key=lambda x: x[0], reverse=True)
L.sort(key=lambda x: x[1], reverse=True)
R.sort(key=lambda x: x[1])
R.sort(key=lambda x: x[0], reverse=True)

ans = 'Yes'
now = 0
for d, min_d in L:
    if now + min_d < 0:
        ans = 'No'
        break
    else:
        now += d

for d, min_d in R:
    if now + min_d < 0:
        ans = 'No'
        break
    else:
        now += d

if now != 0:
    ans = 'No'

print(ans)

Submission status: Wrong Answer

Solution code:
# F - Bracket Sequencing

N = int(input())
L = []
R = []
for _ in range(N):
    S = list(str(input()))
    d = 0
    min_d = 0
    for s in S:
        if s == '(':
            d += 1
        else:
            d -= 1
            min_d = min(min_d, d)
    if d >= 0:
        L.append((d, min_d))
    else:
        R.append((d, min_d))

L.sort(key=lambda x: x[0], reverse=True)
L.sort(key=lambda x: x[1], reverse=True)
R.sort(key=lambda x: x[1], reverse=True)
R.sort(key=lambda x: x[0], reverse=True)

ans = 'Yes'
now = 0
for d, min_d in L:
    if now + min_d < 0:
        ans = 'No'
        break
    else:
        now += d

for d, min_d in R:
    if now + min_d < 0:
        ans = 'No'
        break
    else:
        now += d

if now != 0:
    ans = 'No'

print(ans)

Submission status: Wrong Answer

Solution code:
# F - Bracket Sequencing

N = int(input())
L = []
for _ in range(N):
    S = list(str(input()))
    d = 0
    min_d = 0
    for s in S:
        if s == '(':
            d += 1
        else:
            d -= 1
            min_d = min(min_d, d)
    L.append((d, min_d))

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

ans = 'Yes'
now = 0
for d, min_d in L:
    if now + min_d < 0:
        ans = 'No'
        break
    else:
        now += d

if now != 0:
    ans = 'No'

print(ans)

Submission status: Wrong Answer

Solution code:
def hoge(S):
    cum = 0
    mi = 0
    for s in S:
        cum += 1 if s == '(' else -1
        mi = min(mi, cum)
    return (-mi, cum - mi)

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

M = 0
mx = 0
L = []
for l, r in S:
    if l == 0:
        M += r
    elif l == r:
        mx = max(mx, l)
    else:
        L.append((l, r))

if M < mx:
    print('No')
    exit()

L.sort(key=lambda l: l[1], reverse=True)
for l, r in L:
    M -= l
    if M < 0:
        print('No')
        exit()
    M += r

print('Yes' if M == 0 else 'No')

Submission status: Wrong Answer

Solution code:
def hoge(S):
    cum = 0
    mi = 0
    for s in S:
        cum += 1 if s == '(' else -1
        mi = min(mi, cum)
    return (-mi, cum - mi)

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

M = 0
L = []
for l, r in S:
    if l == 0:
        M += r
    else:
        L.append((l, r))

L.sort(key=lambda l: l[1], reverse=True)
for l, r in L:
    M -= l
    if M < 0:
        print('No')
        exit()
    M += r

print('Yes' if M == 0 else 'No')

Submission status: Wrong Answer

Solution code:
n = int(input())
up_list = []
down_list = []

for _ in range(n):
    txt = input()
    min_comp = 10 ** 6
    compare = 0
    cnt = 0
    for s in txt:
        cnt += 1
        if s == '(':
            compare += 1
        else:
            compare -= 1
            min_comp = min(min_comp, compare)
    if compare > 0:
        up_list.append([compare, min(min_comp, 0)])
    else:
        down_list.append([compare, min(min_comp, 0) - compare])


up_list.sort(key=lambda x: x[1], reverse=True)
down_list.sort(key=lambda x: x[1], reverse=False)
txt = 'No'
c = 0

for t in up_list + down_list:
    if t[1] + c < 0:
        break
    else:
        c += t[0]
else:
    if c == 0:
        txt = 'Yes'

print(txt)

Submission status: Wrong Answer

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

for i in range(N):
  s=S[i]
  l=len(s)
  c=0
  for j in range(l):
    if s[j]=='(':
      c+=1
    else:
      c-=1
      if c<T[i][1]:
        T[i][1]=c
  T[i][0]=c
        
A=[T[i] for i in range(N) if T[i][0]>=0]
B=[T[i] for i in range(N) if T[i][0]<0]

A=sorted(A, key=itemgetter(1), reverse=True)
B=sorted(B, key=lambda x: (x[1], -x[0]))

h=0
la=len(A)
lb=len(B)

i=0
for tmp in A:
  if h+tmp[1]<0:
    print('No')
    exit()
  else:
    h+=tmp[0]
  
for tmp in B:
  if h+tmp[1]<0:
    print('No')
    exit()
  else:
    h+=tmp[0]
  
if h==0:
  print('Yes')
else:
  print('No')

Submission status: Wrong Answer

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

plus_stock = []
minus_stock = []
for i, row in enumerate(S):
    lowest = 0
    now = 0
    for j,char in enumerate(row):
        if char == "(":
            now+=1
        elif char == ")":
            now-=1 
        if now < lowest:
            lowest = now
    if now >= 0:
        plus_stock.append([now, lowest])
    else:
        minus_stock.append([-now, lowest - now])
plus_stock  = sorted(plus_stock, key = lambda x:x[1])
minus_stock = sorted(minus_stock, key = lambda x:x[1])

now = 0

for i in range(len(plus_stock)):
    if now + plus_stock[i][1] < 0:
        print("No")
        sys.exit()
    else:
        now = now+plus_stock[i][0]
last = now
now = 0
for i in range(len(minus_stock)):
    if now + minus_stock[i][1] < 0:
        print("No")
        sys.exit()
    else:
        now = now+minus_stock[i][0]
if last == now:
    print("Yes")
else:
    print("No")