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
sys.setrecursionlimit(2147483647)
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
input = lambda:sys.stdin.readline().rstrip()
def resolve():
    n = int(input())
    first, second, third = [], [], []
    for _ in range(n):
        balance = min_balance = 0
        for c in input():
            if c == '(':
                balance += 1
            else:
                balance -= 1
            min_balance = min(min_balance, balance)
        if min_balance == 0:
            first.append((min_balance, balance))
        elif balance > 0:
            second.append((min_balance, balance))
        else:
            third.append((min_balance, balance))

    now = 0
    # first は何も考えず足せば良い
    for min_balance, balance in first:
        now += balance

    # second は min_balance の大きい方から足せば良い
    second.sort(reverse = 1)
    for min_balance, balance in second:
        if now + min_balance < 0:
            print("No")
            return
        now += balance

    # third も min_balance の小さい方から足せば良い
    third.sort()
    for min_balance, balance in third:
        if now + min_balance < 0:
            print("No")
            return
        now += balance

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

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
input = lambda: sys.stdin.readline().rstrip()
sys.setrecursionlimit(20000000)

def remove(s):
    n = len(s)
    que = deque([""])
    for i in range(n):
        if que[-1] == "(" and s[i] == ")":
            que.pop()
        else:
            que.append(s[i])
    return "".join(que)

n = int(input())

s = [[], [], []]
for i in range(n):
    s_ = remove(input())
    t1 = s_.count("(")
    t2 = s_.count(")")
    if t1 > 0 and t2 > 0:
        s[1].append(s_)
    elif t1 > 0:
        s[0].append(s_)
    else:
        s[2].append(s_)

s[0] = sorted(s[0])
s[1] = sorted(s[1])
s[2] = sorted(s[2], reverse=True)
for i in range(3):
    s[i] = "".join(s[i])

s = "".join(s)
s = remove(s)
if len(s) == 0:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
import sys
n=int(input())
s=[input() for i in range(n)]
t=[2*(i.count("("))-len(i) for i in s]
if sum(t)!=0:
    print("No")
    sys.exit()
st=list(map(list,zip(s,t)))

for i in range(n):
    now,mi=0,0
    for j in st[i][0]:
        if j=="(":
            now+=1
        else:
            now-=1
        mi=min(mi,now)
    st[i].append(mi)
#st.sort(reverse=True,key=lambda z:z[1])
u,v=list(filter(lambda x:x[1]>=0,st)),list(filter(lambda x:x[1]<0,st))
u.sort(reverse=True,key=lambda z:z[1])
v.sort(reverse=True,key=lambda z:z[1])
u.sort(reverse=True,key=lambda z:z[2])
v.sort(reverse=True,key=lambda z:z[2])
lu=len(u)
now2=0
for i in range(n):
    if i<lu:
        if now2+u[i][2]<0:
            print("No")
            break
        now2+=u[i][1]
    else:
        if now2+v[i-lu][2]<0:
            print("No")
            break
        now2+=v[i-lu][1]
else:
    print("Yes")

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from operator import mul


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 998244353


n = I()
m = SR(n)
A = []
L = 0
R = 0
for b in m:
    l = 0
    r = 0
    m = deque()
    flg = 0
    for a in b:
        if m and m[-1] == '(' and a == ')':
            m.pop()
            r -= 1
        elif a == '(':
            m += ['(']
            r += 1
        else:
            l += 1
    A += [(l, r, r - l)]
    L += l
    R += r


class Segtree:
    def __init__(self, A, ide_ele, segfunc, initialize=True):
        self.n = len(A)
        self.size = 2 ** (self.n - 1).bit_length()
        self.ide_ele = ide_ele
        self.segfunc = segfunc
        if initialize:
            self.data = [ide_ele] * self.size + A + [ide_ele] * (self.size - self.n)
            for i in range(self.size - 1, 0, -1):
                self.data[i] = self.segfunc(self.data[2 * i], self.data[2 * i + 1])
        else:
            self.data = [ide_ele] * (2 * self.size)

    def update(self, k, x):
        k += self.size
        self.data[k] = x
        while k:
            k = k >> 1
            self.data[k] = self.segfunc(self.data[2 * k], self.data[2 * k + 1])

    def query(self, l, r):
        L, R = l + self.size, r + self.size
        s = self.ide_ele
        while L < R:
            if R & 1:
                R -= 1
                s = self.segfunc(s, self.data[R])
            if L & 1:
                s = self.segfunc(s, self.data[L])
                L += 1
            L >>= 1
            R >>= 1
        return s

if L != R:
    print('No')
else:
    A.sort()
    A = [(e[0], e[1], e[2], i) for i, e in enumerate(A)]
    seg = Segtree([(INF, INF, INF, INF) for i in range(n)], (INF, INF, INF, INF), min)
    ret = 0
    res = 0
    idx = -1
    for i in range(n):
        while idx + 1 < n and A[idx + 1][0] <= res:
            idx += 1
            seg.update(idx, (A[idx][2], A[idx][0], A[idx][1], idx))
        q, ql, qr, q_idx = seg.query(0, ret + 1)
        seg.update(idx, (INF, INF, INF, INF))
        if q == INF:
            print('No')
            exit()
        ret += q
        res = max(res, ret)
    print('Yes')

Submission status: Wrong Answer

Solution code:
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)
from heapq import heappush, heappop

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

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def rangeI(it, l, r):
    for i, e in enumerate(it):
        if l <= i < r:
            yield e
        elif l >= r:
            break

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

INF = 999999999999999999999999
MOD = 10**9+7

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

left = 0
right = 0

l_ok = [False] * n
r_ok = [False] * n
lmr = [0] * n
min_lmr = [INF] * n

for i,s in enumerate(S):
    l = 0
    r = 0
    lok = True
    for j,c in enumerate(s):
        if c == "(":
            l += 1
        else:
            r += 1
            if r > l:
                lok = False
            min_lmr[i] = min(min_lmr[i], l-r)
    lmr[i] = l - r
    l = 0
    r = 0
    rok = True
    for j in range(len(s)-1, -1, -1):
        if s[j] == "(":
            l += 1
            if l > r:
                rok = False
                break
        else:
            r += 1

    left += s.count("(")
    right += s.count(")")

    l_ok[i] = lok
    r_ok[i] = rok

# log(l_ok)
# log(r_ok)

if left != right:
    print("No")
    exit()

strs = []

# LeftOKを並べる
for i in range(n):
    if l_ok[i]:
        strs.append(S[i])

# LeftもRightもだめなやつをminL-Rが多い順に並べる
ngs = []
for i in range(n):
    if not l_ok[i] and not r_ok[i]:
        # ngs.append((-1 * min_lmr[i], -1 * lmr[i], i))
        ngs.append((lmr[i]<1, -1 * min_lmr[i], i))

ngs.sort()

for ng in ngs:
    strs.append(S[ng[2]])

# RightOKを並べる
for i in range(n):
    if r_ok[i] and not l_ok[i]:
        strs.append(S[i])

# log(ngs)
# log(min_lmr)
# log("".join(strs))

l = 0
r = 0
for s in strs:
    for j,c in enumerate(s):
        if c == "(":
            l += 1
        else:
            r += 1
            if r > l:
                print("No")
                exit()
print("Yes")

Submission status: Wrong Answer

Solution code:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()
N=int(input())
S=[input() for i in range(N)]
llst=[]
lr=[]
rlst=[]
for n in range(N):
    l=0
    r=0
    for i in range(len(S[n])):
        if S[n][i]=="(":
            l+=1
        else:
            if l>0:
                l-=1
            else:
                r+=1
    #print(l,r)
    if l and not r:
        llst.append(l)
    elif not l and r:
        rlst.append(r)
    elif l or r:
        lr.append([l,r])
llst=sum(llst)
rlst=sum(rlst)

if not llst and not rlst and not lr:
    print("Yes")
    exit()
if not lr:
    if llst-rlst==0:
        print("Yes")
    else:
        print("No")
    exit()

idleR=10**7
if lr:
    L,R=lr[0]
    dp=[defaultdict(int) for i in range(len(lr))]
    X=L+idleR*R
    dp[0][X]=1
    stack=[[0,L,R]]
    while stack:
        n,l,r=stack.pop()
        if n+1<len(lr):
            L,R=lr[n+1]
            for xl,xr in [[l+L-R,r],[l,r+R-L]]:
                if xl>=0 and xr>=0:
                    X=xl+idleR*xr
                    if  not dp[n+1][X]:
                        dp[n][X]=1
                        stack.append([n+1,xl,xr])
        else:
            if l<=rlst:
                L=rlst-l
            else:
                continue
            if r<=llst:
                R=llst-r
            else:
                continue
            if L-R==0:
                print("Yes")
                exit()



print("No")

Submission status: Wrong Answer

Solution code:
import numpy as np



n = int(input())
s = []
s_num = np.zeros(n)
s_num_min = np.zeros(n)
for i in range(n):
    kakko_in = input()
    s.append(kakko_in)
    for s_in in kakko_in:
        if s_in == '(':
            s_num[i] += 1
        else:
            s_num[i] -= 1
        if s_num[i] < s_num_min[i]:
            s_num_min[i] = s_num[i]

if np.sum(s_num) != 0:
    print("No")
else:
    now_sum = 0
    now_min_sum = 0
    s_num_index = s_num.argsort()[::-1]
    # print(s_num_index)
    # print(s_num_min_index)
    yet = [1 for _ in range(n)]
    i = 0
    flag = 0
    while i < n:
        index = s_num_index[i]
        if now_sum + s_num_min[index] >= 0:
            flag = 0
            now_sum += s_num[index]
            i += 1
        elif i < n-1:
            if flag:
                break
            temp = s_num_index[i+1]
            s_num_index[i] = temp
            s_num_index[i+1] = index
            flag = 1
    if flag:
        print("No")
    else:
        print("Yes")

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import combinations, product
#import bisect# lower_bound etc
#import numpy as np
def run():
    N = int(input())
    dic = {'(':- 1, ')': 1}
    dic2 = {'(': 0, ')': 1}
    ret = 0
    cri = [0,0,0]
    for _ in range(N):
        S = input()
        arr = []
        for s in S:
            ret += dic[s]
            arr.append(dic2[s])
            try:
                if arr[-1] == 1 and arr[-2] == 0:
                    arr.pop()
                    arr.pop()
            except:
                continue
        #print('arr', arr)
        if arr == []: continue
        if len(arr) == 1:
            cri[arr[0]] += 1
        else:
            if arr[0] == 0 and arr[-1] == 0:
                cri[0] += 1
            elif arr[0] == 1 and arr[-1] == 1:
                cri[1] += 1
            else:
                cri[2] += 1
        #print('cri', cri)
    if ret == 0 and (cri[2] == 0 or (cri[1] > 0 and cri[0] > 0)):
        print('Yes')
    else:
        print('No')
if __name__ == "__main__":
    run()

Submission status: Wrong Answer

Solution code:
def calc(s):
    r = 0
    under = 0
    for c in s:
        if c == '(':
            r += 1
        else:
            r -= 1
            under = min(under, r)
    return r, under

def check(S):
    v = 0
    for r, under in sorted([calc(s) for s in S])[::-1]:
        if (v + under) < 0:
            return False
        v += r
    return v == 0

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

if check(S):
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

Solution code:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()
N=int(input())
S=[input() for i in range(N)]
llst=[]
lr=[]
rlst=[]
for n in range(N):
    l=0
    r=0
    for i in range(len(S[n])):
        if S[n][i]=="(":
            l+=1
        else:
            if l>0:
                l-=1
            else:
                r+=1
    #print(l,r)
    if l and not r:
        llst.append(l)
    elif not l and r:
        rlst.append(r)
    elif l or r:
        lr.append([l,r])
llst=sum(llst)
rlst=sum(rlst)

if not llst and not rlst and not lr:
    print("Yes")
    exit()
if not lr:
    if llst-rlst==0:
        print("Yes")
    else:
        print("No")
    exit()

idleR=10**7
if lr:
    L,R=lr[0]
    dp=[defaultdict(int) for i in range(len(lr))]
    X=L+idleR*R
    dp[0][X]=1
    stack=[[0,L,R]]
    while stack:
        n,l,r=stack.pop()
        if n+1<len(lr):
            L,R=lr[n+1]
            for xl,xr in [[l+L-R,r],[l,r+R-L]]:
                if xl>=0 and xr>=0:
                    X=xl+idleR*xr
                    if not X in dp[n+1]:
                        dp[n][X]=1
                        stack.append([n+1,xl,xr])
        else:
            if l<=rlst:
                L=rlst-l
            else:
                continue
            if r<=llst:
                R=llst-r
            else:
                continue
            if L-R==0:
                print("Yes")
                exit()



print("No")

Submission status: Wrong Answer

Solution code:
import sys
n=int(input())
s=[input() for i in range(n)]
t=[2*(i.count("("))-len(i) for i in s]
if sum(t)!=0:
    print("No")
    sys.exit()
st=list(map(list,zip(s,t)))

for i in range(n):
    now,mi=0,0
    for j in st[i][0]:
        if j=="(":
            now+=1
        else:
            now-=1
        mi=min(mi,now)
    st[i].append(mi)
#st.sort(reverse=True,key=lambda z:z[1])
u,v=list(filter(lambda x:x[1]>=0,st)),list(filter(lambda x:x[1]<0,st))
u.sort(reverse=True,key=lambda z:z[2])
v.sort(reverse=True,key=lambda z:z[2])
lu=len(u)
now2=0
for i in range(n):
    if i<lu:
        if now2+u[i][2]<0:
            print("No")
            break
        now2+=u[i][1]
    else:
        if now2+v[i-lu][2]<0:
            print("No")
            break
        now2+=v[i-lu][1]
else:
    print("Yes")

Submission status: Wrong Answer

Solution code:
a=int(input())
s=''
for _ in range(a):
  x=input()
  s=s+x
oc=s.count('(')
cc=s.count(')')
if oc==cc:
  print('Yes')
else:
  print('No')

Submission status: Wrong Answer

Solution code:
n = int(input())
cnt_list = [0]*n
l_zero = []
r_zero = []
suleft = 0
suright = 0

for i in range(n):
    ss = input()
    l = len(ss)
    right = 0
    left=0
    for j in range(l):
        if ss[j]=='(': left+=1
        elif left>0: left-=1
        else: right+=1
    cnt_list[i] = [left,right]
    if left==0: l_zero.append(i)
    if right==0: r_zero.append(i)
    suleft += left
    suright += right


if l_zero ==[] or r_zero==[]:
    print('No')
    exit()
if len(l_zero)==1 and len(l_zero)==1 and l_zero[0]==r_zero[0]:
    print('No')
    exit()

for lz in l_zero:
    for rz in r_zero:
        good_l = suright - cnt_list[lz][1]
        good_r = suleft - cnt_list[rz][0]

        if cnt_list[rz][0] == good_l and cnt_list[lz][1] == good_r:
            print('Yes')
            exit()

print('No')

Submission status: Wrong Answer

Solution code:
N = int(input())

S = [input() for _ in range(N)]
for i in range(N):
    while S[i] != S[i].replace("()",""):
        S[i] = S[i].replace("()","")
ls = [[0,0,0] for _ in range(N)]
for i in range(N):
    for s in S[i]:
        if s == "(":
            ls[i][0] += 1
        if s == ")":
            ls[i][1] += 1
    ls[i][2] = ls[i][0]-ls[i][1]

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

if ls[0][1] > 0 or ls[-1][0] > 0:
    print('No')
    exit()
else:
    sum = 0
    for i in range(len(ls)-1):
        sum += ls[i][0]-ls[i+1][1]
        if sum < 0:
            print('No')
            exit()
    if sum == 0:
        print("Yes")
    else:
        print("No")

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
input = lambda:sys.stdin.readline().rstrip()
def resolve():
    n = int(input())
    first, second, third = [], [], []
    for _ in range(n):
        balance = min_balance = 0
        for c in input():
            if c == '(':
                balance += 1
            else:
                balance -= 1
            min_balance = min(min_balance, balance)
        if min_balance >= 0:
            first.append((min_balance, balance))
        elif balance > 0:
            second.append((min_balance, balance))
        else:
            third.append((min_balance, balance))

    now = 0
    # first は何も考えず足せば良い
    for min_balance, balance in first:
        now += balance

    # second は min_balance の小さい方から足せば良い
    second.sort()
    for min_balance, balance in second:
        if now + min_balance < 0:
            print("No")
            return
        now += balance

    # third も min_balance の小さい方から足せば良い
    third.sort()
    for min_balance, balance in third:
        if now + min_balance < 0:
            print("No")
            return
        now += balance

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

Submission status: Wrong Answer

Solution code:
import sys
import heapq
hpush = heapq.heappush
hpop = heapq.heappop
input = sys.stdin.readline
N = int(input())
ls = [0] * N
rs = [0] * N
h = []
base = 10 ** 7
for x in range(N):
  S = list(input())[: -1]
  for i in range(len(S)):
    if S[i] == "(": rs[x] += 1
    if S[i] == ")":
      if rs[x]: rs[x] -= 1
      else: ls[x] += 1
  hpush(h, ls[x] * base - rs[x])
if sum(ls) != sum(rs):
  print("No")
  exit(0)
if sum(ls) == 0:
  print("Yes")
  exit(0)
l = 0
r = 0
for i in range(N):
  if ls[i] == 0 and (rs[i] > 0): l |= 1
  if rs[i] == 0 and (ls[i] > 0):
    l |= 2
    r = max(r, ls[i])
if l < 3:
  print("No")
  exit(0)
#print(h)
l = 0
while len(h):
  t = hpop(h)
  x = max(0, -(-t // base))
  y = -t % base
  if y == 0 and (x == r):
    continue
  if l < x:
    print("No")
    exit(0)
  l += y - x
  #print(l, r, x, y)
if l - r: print("No")
else: print("Yes")

Submission status: Wrong Answer

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

N = int(input())
S = [input()[:-1] for _ in range(N)]
high = []
low = []
for i in range(N):
    cnt = 0
    m = 0
    for j in range(len(S[i])):
        if S[i][j] == "(":
            cnt += 1
        else:
            cnt -= 1
        m = min(m, cnt)
    if cnt > 0:
        high.append([m, cnt])
    else:
        low.append([m-cnt, -cnt])
high.sort(reverse=True)
low.sort()

h = 0
for m, up in high:
    if h+m < 0:
        print("No")
        sys.exit()
    h += up
p = 0
for m, down in low:
    if p+m < 0:
        print("No")
        sys.exit()
    p += down
if h == p:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
def input():
    return sys.stdin.readline().strip()

def check():
    s = input()
    m = 0
    res = deque([])
    for i in s:
        if i == "(":
            m += 1 
        else:
            m -= 1
            res.append(m)
    ##print(res)
    try:
        a = min(res)
    except:
        a = 0
    return [a,m]

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

S.sort(reverse=True)


a = 0
b = 0

for res,m in S:
    a += res
    b += m
    ##print(a,b)
    if a < 0:
        print("No")
        exit()
    a += m - res

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

Submission status: Wrong Answer

Solution code:
import sys
import heapq
hpush = heapq.heappush
hpop = heapq.heappop
input = sys.stdin.readline
N = int(input())
ls = [0] * N
rs = [0] * N
h = []
base = 10 ** 7
for x in range(N):
  S = list(input())[: -1]
  for i in range(len(S)):
    if S[i] == "(": rs[x] += 1
    if S[i] == ")":
      if rs[x]: rs[x] -= 1
      else: ls[x] += 1
  hpush(h, ls[x] * base - rs[x])
if sum(ls) != sum(rs):
  print("No")
  exit(0)
if sum(ls) == 0:
  print("Yes")
  exit(0)
l = 0
r = 0
for i in range(N):
  if ls[i] == 0 and (rs[i] > 0): l = 1
  if rs[i] == 0 and (ls[i] > 0):
    l |= 2
    r = max(r, ls[i])
if l < 3:
  print("No")
  exit(0)
#print(h)
l = 0
while len(h):
  t = hpop(h)
  x = max(0, -(-t // base))
  y = -t % base
  if y == 0 and (x == r):
    continue
  if l < x:
    print("No")
    exit(0)
  l += y - x
  #print(l, r, x, y)
if l - r: print("No")
else: print("Yes")

Submission status: Wrong Answer

Solution code:
import sys
import heapq
hpush = heapq.heappush
hpop = heapq.heappop
input = sys.stdin.readline
N = int(input())
ls = [0] * N
rs = [0] * N
h = []
base = 10 ** 7
for x in range(N):
  S = list(input())[: -1]
  for i in range(len(S)):
    if S[i] == "(": rs[x] += 1
    if S[i] == ")":
      if rs[x]: rs[x] -= 1
      else: ls[x] += 1
  hpush(h, ls[x] * base - rs[x])
if sum(ls) != sum(rs):
  print("No")
  exit(0)
if sum(ls) == 0:
  print("Yes")
  exit(0)
l = 0
r = 0
for i in range(N):
  if ls[i] == 0 and (rs[i] > 0): l = 1
  if rs[i] == 0 and (ls[i] > 0): r = max(r, ls[i])
if l & r == 0:
  print("No")
  exit(0)
#print(h)
l = 0
while len(h):
  t = hpop(h)
  x = max(0, -(-t // base))
  y = -t % base
  if y == 0 and (x == r):
    continue
  if l < x:
    print("No")
    exit(0)
  l += y - x
  #print(l, r, x, y)
if l - r: print("No")
else: print("Yes")

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
def input():
    return sys.stdin.readline().strip()

def check():
    s = input()
    m = 0
    res = deque([])
    for i in s:
        if i == "(":
            m += 1 
        else:
            m -= 1
            res.append(m)
    ##print(res)
    try:
        a = min(res)
    except:
        a = 0
    return [a,m]

N = int(input())
S = [check() for _ in range(N)]
##print(S)
S.sort(reverse=True)

a = 0
b = 0

for res,m in S:
    a += res
    b += m
    if a < 0:
        print("No")
        exit()

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

Submission status: Wrong Answer

Solution code:
n = int(input())
R = 0
L = 0
flag = 0
M = []
for _ in range(n):
    s = input()
    right = 0
    left = 0
    for w in s:
        if w == "(":
            left += 1
        if w == ")":
            if left > 0:
                left -= 1
            else:
                right += 1
    if left > 0 and right > 0:
        M.append((right, left, left - right))
    elif left == 0 and right > 0:
        R += right
    elif left > 0 and right == 0:
        L += left
M.sort()
remain = []
for mr, ml, delta in M:
    if delta > 0:
        L -= mr
        if L < 0:
            flag = 1
        L += ml
    else:
        remain.append((mr, ml))
for mr, ml in remain:
    L -= mr
    if L < 0:
        flag = 1
    L += ml


if L != R:
    flag = 1
if flag:
    print("No")
else:
    print("Yes")

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import combinations, product
#import bisect# lower_bound etc
#import numpy as np
def run():
    N = int(input())
    dic = {'(':- 1, ')': 1}
    dic2 = {'(': 0, ')': 1}
    ret = 0
    cri = [0,0,0]
    for _ in range(N):
        S = input()
        arr = []
        for s in S:
            ret += dic[s]
            arr.append(dic2[s])
            try:
                if arr[-1] == 1 and arr[-2] == 0:
                    arr.pop()
                    arr.pop()
            except:
                continue
            #print('arr', arr)
        if arr == []: continue
        if len(arr) == 1:
            cri[arr[0]] += 1
        else:
            if arr[0] == 0 and arr[-1] == 0:
                cri[0] += 1
            elif arr[0] == 1 and arr[-1] == 1:
                cri[1] += 1
            else:
                cri[2] += 1
        #print('cri', cri)
    if ret == 0 and cri[0] - cri[2] == cri[1] - cri[2] and cri[0] >= cri[2]:
        print('Yes')
    else:
        print('No')
if __name__ == "__main__":
    run()

Submission status: Wrong Answer

Solution code:
N = int(input())
s = [input() for i in range(N)]
S = [[0]*len(s[i]) for i in range(N)]
for i, x in enumerate(s):
    res = []
    q = 0
    for j in range(len(x)):
        if x[j] == ')':
            S[i][j] = -1
        else:
            S[i][j] = 1
s = [0]*N
m = [len(S[i]) for i in range(N)]
for i, x in enumerate(S):
    tmp = 0
    for j in range(len(x)):
        tmp += S[i][j]
        m[i] = min(tmp, m[i])
    s[i] = tmp
if sum(s) == 0:
    ss = [(S[i], m[i], s[i]) for i in range(N)]
    ss.sort(key=lambda x: (x[1], x[2]), reverse=True)
    tmp = 0
    for x, _, _ in ss:
        for z in x:
            tmp += z
            if tmp < 0:
                    print("No")
                    exit(0)
    print("Yes")

else:
    print("No")

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import combinations, product
#import bisect# lower_bound etc
#import numpy as np
def run():
    N = int(input())
    dic = {'(':- 1, ')': 1}
    dic2 = {'(': 0, ')': 1}
    ret = 0
    cri = [0,0,0]
    for _ in range(N):
        S = input()
        arr = []
        for s in S:
            ret += dic[s]
            arr.append(dic2[s])
            try:
                if arr[-1] == 1 and arr[-2] == 0:
                    arr.pop()
                    arr.pop()
            except:
                continue
            #print('arr', arr)
        if arr == []: continue
        if len(arr) == 1:
            cri[arr[0]] += 1
        else:
            if arr[0] == 0 and arr[-1] == 0:
                cri[0] += 1
            elif arr[0] == 1 and arr[-1] == 1:
                cri[1] += 1
            else:
                cri[2] += 1
        #print('cri', cri)
    if ret == 0 and cri[0] - cri[2] == cri[1] - cri[2]:
        print('Yes')
    else:
        print('No')
if __name__ == "__main__":
    run()

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    S = [input() for _ in [0]*n]
    s2 = []
    s3 = []
    for s in S:
        temp = [0, 0]
        m = 0
        now = 0
        for i in s:
            if i == "(":
                now += 1
            else:
                now -= 1
            m = min(m, now)
        temp[0] = -m
        temp[1] = (s.count("(")-s.count(")"))-m
        if temp[1] > temp[0]:
            s2.append(temp)
        else:
            s3.append(temp)
    s2.sort(key=lambda x: (-x[0]))
    s3.sort(key=lambda x: (x[1]))
    cnt = 0
    for i, j in s2:
        cnt -= i
        if cnt < 0:
            print("No")
            return
        cnt += j
    for i, j in s3:
        cnt -= i
        if cnt < 0:
            print("No")
            return
        cnt += j
    if cnt != 0:
        print("No")
        return
    print("Yes")


main()

Submission status: Wrong Answer

Solution code:
def check(pt, brackets):
    brackets.sort(reverse=True)
    for m, t in brackets:
        if pt + m < 0:
            return False
        pt += t
    return pt


n = int(input())
brackets_p = []  # (始めを0として、( = +1, ) = -1 として、最後はいくつか, 途中の最小値はいくつか)
brackets_m = []
brackets_0_min = 0
pt = 0
mt = 0
for _ in range(n):
    s = input()
    total = 0
    mini = 0
    for c in s:
        if c == '(':
            total += 1
        else:
            total -= 1
            mini = min(mini, total)

    if total > 0:
        if mini == 0:
            pt += total
        else:
            brackets_p.append((mini, total))
    elif total == 0:
        if mini < 0:
            brackets_0_min = min(brackets_0_min, mini)
    else:
        total, mini = -total, mini - total
        if mini == 0:
            mt += total
        else:
            brackets_m.append((mini, total))

pt = check(pt, brackets_p)
mt = check(mt, brackets_m)

if (pt == False) or (mt == False) or (pt != mt) or (pt + brackets_0_min < 0):
    print('No')
else:
    print('Yes')

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
def input():
    return sys.stdin.readline().strip()

def check():
    s = input()
    m = 0
    res = deque([])
    for i in s:
        if i == "(":
            m += 1 
        else:
            m -= 1
            res.append(m)
    ##print(res)
    try:
        a = min(res)
    except:
        a = m
    return [a,m]

N = int(input())
S = [check() for _ in range(N)]
##print(S)
S.sort(reverse=True)

a = 0
b = 0

for res,m in S:
    a += res
    b += m
    if a < 0:
        print("No")
        exit()

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

Submission status: Wrong Answer

Solution code:
import sys
n=int(input())
s=[input() for i in range(n)]
t=[2*(i.count("("))-len(i) for i in s]
if sum(t)!=0:
    print("No")
    sys.exit()
st=list(map(list,zip(s,t)))

for i in range(n):
    now,mi=0,0
    for j in st[i][0]:
        if j=="(":
            now+=1
        else:
            now-=1
        mi=min(mi,now)
    st[i].append(mi)
st.sort(reverse=True,key=lambda z:z[1])
st.sort(reverse=True,key=lambda z:z[2])
now2=0
for i in range(n):
    if now2+st[i][2]<0:
        print("No")
        break
    if st[i][1]>=0:
        now2+=st[i][1]
else:
    print("Yes")