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 = [list(input()) for _ in range(n)]

bs = []
for si in s:
    li, ri = 0, 0
    for c in si:
        if c == '(':
            li += 1
        elif c == ')' and li == 0:
            ri += 1
        elif c == ')' and 0 < li:
            li -= 1
    bs.append((ri, (ri - li), -li))

bs.sort()
bra = 0
ans = "Yes"
for (ri, d, li) in bs:
    li *= -1
    bra -= ri
    if bra < 0:
        ans = "No"
        break
    bra += li
if bra != 0:
    ans = "No"
print(ans)

Submission status: Wrong Answer

Solution code:
def main():

    import sys, math
    #from bisect import bisect_left as bl, bisect_right as br, insort
    #from heapq import heapify, heappush, heappop
    from collections import defaultdict as dd, deque
    def data(): return sys.stdin.readline().strip()
    def mdata(): return list(map(int, data().split()))
    def out(*var, end="\n"): sys.stdout.write(' '.join(map(str, var))+end)
    # sys.setrecursionlimit(100000)
    INF = int(1e9)
    mod = int(1e9)+7

    n=int(data())
    l1=[]
    l2=[]
    cnt1=0
    cnt2=0
    for i in range(n):
        s=data()
        o=c=0
        for j in s:
            if j=='(':
                o+=1
            else:
                if o>0:
                    o-=1
                else:
                    c+=1
        if o==0:
            if c!=0:
                cnt2+=c
        elif c==0:
            cnt1+=o
        else:
            if c>o:
                l2.append([c,o])
            else:
                l1.append([c,o])
    l1.sort(key=lambda x:x[0])
    flag=True
    for i in l1:
        if cnt1>=i[0]:
            cnt1=cnt1-i[0]+i[1]
        else:
            flag=False
            break
    l2.sort(key=lambda x: x[0])
    for i in l2:
        if cnt1>=i[0]:
            cnt1=cnt1-i[0]+i[1]
        else:
            flag=False
            break
    if flag==True:
        if cnt1-cnt2==0:
            print("Yes")
        else:
            print("No")
    else:
        print("No")

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
M = 0
H = 0
tipm = 0
tiph = 0
tipex = 0
ans = "No"
for i in range(N):
  S = input()
  l = len(S)
  h = 0
  hm = 0
  m = 0
  mh = 0
  for j in range(l):
    k = - j - 1
    if ((S[j] == ")") and (hm == 0)):
      h = h + 1
    elif ((S[j] == ")") and (hm > 0)):
      hm = hm - 1
    elif (S[j] == "("):
      hm = hm + 1
    if ((S[k] == "(") and (mh == 0)):
      m = m + 1
    elif ((S[k] == "(") and (mh > 0)):
      mh = mh - 1
    elif (S[k] == ")"):
      mh = mh + 1
  M = M + m
  H = H + h
  if m == 0:
    tipm = tipm + 1
  if h == 0:
    tiph = tiph + 1
  if ((m == 0) and (h == 0)):
    tipex = tipex + 1
tip = tipm + tiph - tipex
if ((tipm > 0) and (tiph > 0) and (tip > 1)):
  if M == H:
    ans = "Yes"
print(ans)

Submission status: Wrong Answer

Solution code:
import re

n = int(input())
s = set()
for i in range(n):
    ss = input().rstrip()
    ns = len(ss)
    while True:
        ss = ss.replace('()', '')
        nns = len(ss)
        if nns == ns:
            break
        ns = nns
    if ss:
        s.add(ss)

ss = ''.join(sorted(list(s)))
ns = len(ss)
while True:
    ss = ss.replace('()', '')
    nns = len(ss)
    if nns == ns:
        break
    ns = nns
if len(ss) == 0:
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

Solution code:
def count(s):
    ret = 0
    max_down = 0
    for c in s:
        if c=="(": ret += 1
        else: ret -= 1
        max_down = min(max_down,ret)
    return max_down, ret

n = int(input())
s_count_plus = []
s_count_minus = []
for i in range(n):
    si = input()
    down, num = count(si)
    if num > 0:
        s_count_plus.append((down, num))
    else:
        s_count_minus.append((-down,num))

s_count_plus.sort(reverse=True)
s_count_minus.sort(reverse=True)

ans = "No"
count_sum = 0

flag = 1

for down, num in s_count_plus:
    if count_sum + down < 0:
        flag = 0
        break
    count_sum += num

for down, num in s_count_minus:
    if count_sum < down:
        flag = 0
        break
    count_sum += num

if flag and count_sum == 0: ans = "Yes"

print(ans)

Submission status: Wrong Answer

Solution code:
class SegTree:
    def __init__(self, init_val, ide_ele, segfunc):
        self.n = len(init_val)
        self.num =2**(self.n-1).bit_length()
        self.ide_ele = ide_ele
        self.seg = [[self.ide_ele, i] for i in range (2*self.num)]
        self.segfunc = segfunc
        
        #set_val
        for i in range(self.n):
            self.seg[i+self.num-1] = init_val[i]    
        #built
        for i in range(self.num-2,-1,-1) :
            self.seg[i] = segfunc(self.seg[2*i+1], self.seg[2*i+2]) 
    
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k+1:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])
    
    def query(self, p, q):
        if q<=p:
            return self.ide_ele,0
        p += self.num-1
        q += self.num-2
        res = [self.ide_ele, self.ide_ele] 
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res

def Int():
    return int(input())
def Ints():
    return map(int,input().split())
def IntList():
    return list(Ints())
def IntMat(N):
    return [IntList() for i in range(N)]

import sys
sys.setrecursionlimit(4100000)
rl = sys.stdin.readline

N = Int()
Sum = 0

A = []

for i in range(N):
    s = rl()
    now = 0
    minimum = 0
    for j in s:
        if j=='(':
            now += 1
        elif j == ')':
            now -= 1
        minimum = min(minimum,now)
    Sum += now
    A.append([minimum,now])

#print(A)
A.sort()
Min = []
Now = []
c = 0
for (i,j) in A:
    Min.append(i)
    Now.append([j,c])
    c += 1
    
if Sum!=0:
    print('No')
    sys.exit()

INF = 10**15
ide_ele = -INF
Seg = SegTree(Now,ide_ele,max)

import bisect

count = 0
now = 0

#print(Min)
#print(Now)

while count < N:
    i = bisect.bisect_left(Min,-now)
    #print(i,N)
    j,k = Seg.query(i, N)
    
    #print(j)
    now += j
    Seg.update(k,[-INF,k])
    
    if now<0:
        print('No')
        sys.exit()
    count += 1
    
print('Yes')

Submission status: Wrong Answer

Solution code:
n = int(input())
cnt_list = [0]*n

for i in range(n):
    ss = input()
    l = len(ss)
    cnt = ss.count('(')
    cnt_list[i] = 2*cnt - l

if sum(cnt_list) == 0:
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

Solution code:
n = int(input())
sn = [None] * n
for i in range(n):
    sn[i] = input().strip()

def counter(s):
    while '()' in s and s != '':
        s = s.replace('()', '')
    return [s.count(')'), s.count('(')]


check1 = False
check2 = False
checkSP = True
results = []
r, l = (0, 0)
for i, s in enumerate(sn):
    pair = counter(s)
    r += pair[0]
    l += pair[1]
    if pair[0] == 0 and pair[1] != 0:
        check1 = True
    if pair[1] == 0 and pair[0] != 0:
        check2 = True
    if pair[1] != 0 or pair[0] != 0:
            checkSP = False
    
if (check1 and check2 and r == l) or checkSP:
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

Solution code:
n = int(input())
data = []
for i in range(n):
    s = input()
    k = len(s) - s.count(')')*2
    data.append([k,s])
data.sort(reverse=True,key=lambda x: x[0])
ans = 0
for i in range(len(data)):
    s = data[i][1]
    for j in range(len(s)):
        if s[j] == '(':
            ans += 1
        else:
            ans -= 1
        if ans < 0:
            print("No")
            exit()
if ans == 0:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
n = int(input())

all_change_depth = 0
required_depth = []

change_posi_zero = []
change_nega = []

for i in range(n):
    paren = input()
    current_depth = 0
    min_depth = 0
    for ch in paren:
        if ch == '(':
            current_depth += 1
        else:
            current_depth -= 1
            min_depth = min(min_depth, current_depth)

    all_change_depth += current_depth
    if current_depth > 0:
        change_posi_zero.append( (current_depth, -(min_depth)) )
    else:
        change_nega.append( (current_depth, -(min_depth)) )

# まず変化depthの合計が非ゼロならNo。（と）の個数が全体で不一致なので。
if all_change_depth != 0:
    print('No')
    exit()

# 変化depthが0と正の要素を、要求depthが小さい順に投入する。
# 現在depth < 要求depthならアウト
current_depth = 0
change_posi_zero.sort(key=lambda x: x[1])
for paren in change_posi_zero:
    change_depth = paren[0]
    required_depth = paren[1]

    if required_depth > current_depth:
        print('No')
        exit()
    current_depth += change_depth

# 変化depthが負の要素を、要求depthが大きい順に投入する。
# 現在depth < 要求depthならアウト
change_nega.sort(key=lambda x: x[1], reverse=True)

for paren in change_nega:
    change_depth = paren[0]
    required_depth = paren[1]

    if required_depth > current_depth:
        print('No')
        exit()
    current_depth += change_depth

assert(current_depth == 0)
print('Yes')

Submission status: Wrong Answer

Solution code:
import heapq
import sys

input = sys.stdin.readline

N = int(input())

data = [0]*N
for i in range(N):
    S = list(str(input()))
    s = 0
    m = 0
    for j in range(len(S)):
        if S[j] == "(":
            s += 1
        else:
            s -= 1
            m = min(m,s)
    data[i] = [-m,-s]


heapq.heapify(data)
x = 0
valid = []
heapq.heapify(valid)

det = 0

###
#print("data",data)
#print("valid",valid)
#print(x)
###

while data:
    ###
    #print("data",data)
    #print("valid",valid)
    ###
    while data and x - data[0][0] >= 0:
        y = heapq.heappop(data)
        heapq.heappush(valid,[y[1],y[0]])
    
    ###
    #print("valid",valid)
    ###

    ###
    #print("data",data)
    #print("valid",valid)
    #print(x)
    ###
    while valid and x >= 0:
        z = heapq.heappop(valid)
        x -= z[0]
    
    if data and x - data[0][0] < 0:
        det = -1
        break

if det == 0 and x == 0 and valid ==[]:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
from collections import deque

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

tmp = []
for i,s in enumerate(S):
    tmp.append([s.count("(")-s.count(")"),i])

tmp.sort(reverse=True)

a = 0
b = 0
s = ""
for _,i in tmp:
    s += S[i]
print(s)
for i in range(len(s)):
    if s[i] == "(":
        a += 1
    else:
        b += 1
    if b > a:
        print("No")
        exit()

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import sys
N=int(input())
L=[0]*N
R=[0]*N
for i in range(N):
  S=input()
  for j in range(len(S)):
    if S[j]=='(':
      L[i]+=1
    elif S[j]==')' and L[i]==0:
      R[i]+=1
    else:
      L[i]-=1
if sum(L)!=sum(R):
  print('No')
  sys.exit()
r,l=0,0
LR=[]
for i in range(N):
  if L[i]==0 and R[i]!=0:
    r+=R[i]
  elif L[i]!=0 and R[i]==0:
    l+=L[i]
  elif L[i]!=0 and R[i]!=0:
    LR.append([L[i]-R[i],L[i],R[i]])
LR.sort()
LL,RR=0,0
for i in range(len(LR)):
  if LL<LR[i][2]:
    RR+=(LR[i][2]-LL)
    LL=0
  elif LL>=LR[i][2]:
    LL-=LR[i][2]
  LL+=LR[i][1]
if l==RR and r==LL:
  print('Yes')
elif (LL==0 or RR==0) and LL+l==RR+r:
  print('Yes')
else:
  print('No')

Submission status: Wrong Answer

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

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)
    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(")")
    lmr[i] = left - right

    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((min_lmr[i], i))

ngs.sort(key=lambda ng: ng[0], reverse=True)

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

# 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:
import bisect
import sys
from collections import defaultdict


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


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

    return MIN, tmp


cnts = []
for s in ss:
    down, up = calc(s)
    if up > 0:
        cnts.append((1, down, up, s))
    elif up == 0:
        cnts.append((0, down, up, s))
    else:
        cnts.append((-1, down, up, s))

cnts.sort(reverse=True)
# print(cnts)

tmp = 0
for _, d, u, _ in cnts:
    if tmp + d < 0:
        print("No")
        sys.exit()

    tmp += u

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


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

Submission status: Wrong Answer

Solution code:
from operator import itemgetter


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


n = int(input())
brackets_p = []  # (始めを0として、( = +1, ) = -1 として、最後はいくつか, 途中の最小値はいくつか)
brackets_m = []
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((total, mini))
        continue

    total = 0
    mini = 0
    for c in s[::-1]:
        if c == ')':
            total += 1
        else:
            total -= 1
            mini = min(mini, total)

    if mini == 0:
        mt += total
    else:
        brackets_m.append((total, mini))

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

if pt == False or mt == False or pt != mt:
    print('No')
else:
    print('Yes')

Submission status: Wrong Answer

Solution code:


N=int(input())


cand=[]
right=[]
left=[]
for _ in range(N):
    moji=input()
    if moji.count(")")-moji.count("(")>=0:
        right.append(moji)
    else:
        left.append(moji)
mx_r=[]
for item in right:
    mx=-10**9
    temp=0
    for moji in item:
        if moji=="(":
            temp+=1
        else:
            temp-=1
        mx=max(temp,mx)
    mx_r.append([mx,item])

mx_l=[]
for item in left:
    mi=-10**9
    temp=0
    for moji in item:
        #print(temp)
        if moji=="(":
            temp+=1
        else:
            temp-=1
        mi=max(temp,mi)
    mx_l.append([mi,item])

mx_l.sort(key=lambda x:x[0],reverse=True)
mx_r.sort(key=lambda x:x[0],reverse=True)
#print(mx_r,mx_l)    

ans=""
for item in mx_l:
    ans+=item[1]
for item in mx_r:
    ans+=item[1]
#print(ans)

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n = int(input())
sn = [None] * n
for i in range(n):
    sn[i] = input().strip()

def counter(s):
    while '()' in s and s != '':
        s = s.replace('()', '')
    return [s.count(')'), s.count('(')]


check1 = False
check2 = False
checkSP = True
results = []
r, l = (0, 0)
for i, s in enumerate(sn):
    pair = counter(s)
    r += pair[0]
    l += pair[1]
    if pair[0] == 0 and pair[1] != 0:
        check1 = True
    if pair[1] == 0 and pair[0] != 0:
        check2 = True
        if pair[1] != 0 or pair[0] != 0:
            checkSP = False
    
if (check1 and check2 and r == l) or checkSP:
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

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

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

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

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

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

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

if len(M) == 0:
  if cnt == 0:
    print("Yes")
  else:
    print("No")
  exit()

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

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

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

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

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

N = I()
S = []
for i in range(N):
    S.append(list(input()))

# ')' - '('
num = [0]*N
for i in range(N):
    val = 0
    temp = [0]*len(S[i])
    for j in range(len(S[i])):
        if S[i][j] == ')':
            temp[j] = temp[j-1]+1
        else:
            temp[j] = temp[j-1]-1

    num[i] = max(temp)

soukei = [0]*N
for i in range(N):
    temp = 0
    for j in range(len(S[i])):
        if S[i][j] == '(':
            temp += 1
        else:
            temp -= 1
    soukei[i] = temp

if sum(soukei) != 0:
    print('No')
    exit()

A = []
for i in range(N):
    A.append((num[i],soukei[i]))


A.sort(key=lambda x:(x[0],-x[1]))
s = 0
used = [False]*N
for i in range(N):
    if A[i][0] <= 0:
        used[i] = True
        s += A[i][1]

for i in range(N):
    if used[i]:
        continue
    if s < A[i][0]:
        print('No')
        exit()
    else:
        s += A[i][1]
    
print('Yes')

Submission status: Wrong Answer

Solution code:
def kton(S):
    r = 0
    m = 0
    for s in S:
        r += 1 if s == '(' else -1
        m = min(m, r)
    return r, m
        
def main():
    N = int(input())
    RM = [kton(input()) for _ in range(N)]
    pos = 0
    negp = []
    negn = []
    posn = []
    for r, m in RM:
        if m < 0:
            if r >= 0:
                negp.append((-m, r))
            else:
                negn.append((-r, m))
        else:
            pos += r

    negp.sort()
    for m, r in negp:
        if pos - m < 0:
            return False
        pos += r
    negn.sort()
    for r, m in negn:
        if pos + m < 0:
            return False
        pos -= r
    return pos == 0

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

Submission status: Wrong Answer

Solution code:
from itertools import combinations

import numpy as np


def run():
    n = int(input())
    s_list = [input() for _ in range(n)]
    s_list = np.array([encode(s) for s in s_list])

    s = np.sum(s_list, axis=0)

    s_list_is_0 = s_list == 0

    left_found = (s_list_is_0 == np.array([True, False])).all(axis=1)
    right_found = (s_list_is_0 == np.array([False, True])).all(axis=1)

    if s[0] == s[1] and left_found.any() and right_found.any():
        print('Yes')
    else:
        print('No')


def encode(s: str):
    temp_s = s
    while True:
        next_s = temp_s.replace('()', '')
        if temp_s == next_s:
            break
        temp_s = next_s

    return temp_s.count(')'), temp_s.count('(')


if __name__ == '__main__':
    run()

Submission status: Wrong Answer

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

def brancket(s):
    ans = [0, 0]
    l, r = 0, 0
    for i in s:
        if i == ')':
            if r == 0:
                ans[0] += 1
            else:
                r -= 1
        if i == '(':
            r += 1
    ans[1] = r
    return ans

L, R, tl, tr = 0, 0, False, False
for i in S:
    if (a := brancket(i)) != [0, 0]:
        if a[0] == 0:
            tl = True
        if a[1] == 0:
            tr = True
    L += a[0]
    R += a[1]

if L != 0 or R != 0:
    print('Yes' if tl and tr and L == R else '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)
#print(ls, rs)

#print(h)
l = 0
while len(h):
  t = hpop(h)
  x = max(0, t // base)
  y = -t % base
  if l < x:
    print("No")
    exit(0)
  l += y - x
  #print(l)
if l:
  print("No")
else: print("Yes")

Submission status: Wrong Answer

Solution code:
N = int(input())

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

T = []

for i in range(N):
    count1 = 0
    count2 = 0
    count = 0
    for j in range(len(S[i])):
        if S[i][j]=="(":
            count += 1
        else:
            count -= 1
        count1 = max(count1,-count)
    count = 0
    for j in range(len(S[i])):
        if S[i][len(S[i])-j-1]=="(":
            count += 1
        else:
            count -= 1
        count2 = max(count2,count)

    T.append((count1,count2))
flag1 = False
flag2 = False
count0 = 0
for i in range(N):
    if T[i][0]==0 and T[i][1]==0:
        count0 += 1
    elif T[i][0]==0 and T[i][1]!=0:
        flag1 = True
    elif T[i][0]!=0 and T[i][1]==0:
        flag2 = True

if (flag1 and flag2) or count0>=2 or (flag1 and count0==1) or (flag2 and count0==1):
    count1=0
    count2=0
    for i in range(N):
        count1 += T[i][0]
        count2 += T[i][1]
    if count1==count2:
        print("Yes")
    else:
        print("No")
elif N==1 and count0==1:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
import sys
n = int(input())
s = [input() for _ in range(n)]
cnts = []
mins = []
plus = []
minus = []
sm = 0
for i in range(n):
    cnt = 0
    mn = 0
    mx = 0
    for c in s[i]:
        if c == '(':
            cnt+=1
        else: cnt-=1
        mn = min(cnt, mn)
        mx = max(cnt, mx)
    cnts.append(abs(cnt))
    if cnt>0:
        plus.append(i)
        mins.append(abs(mx))
    else:
        minus.append(i)
        mins.append(abs(mn))
    sm+=cnt
if(sm != 0):
    print('No')
    sys.exit()

plus.sort(key = lambda x:mins[x])
minus.sort(key = lambda x:mins[x])
now = 0
que = []
r = 0
while r<len(plus) and mins[plus[r]]<=now:
    que.append(plus[r])
    r+=1
for i in range(len(plus)):
    if(len(que)==0):
        print('No')
        sys.exit()
    j = que.pop()
    now+=cnts[j]
    while r<len(plus) and mins[plus[r]]<=now:
        que.append(plus[r])
        r+=1

plus = minus
now = 0
que = []
r = 0
while r<len(plus) and mins[plus[r]]<=now:
    que.append(plus[r])
    r+=1
for i in range(len(plus)):
    if(len(que)==0):
        print('No')
        sys.exit()
    j = que.pop()
    now+=cnts[j]
    while r<len(plus) and mins[plus[r]]<=now:
        que.append(plus[r])
        r+=1
print('Yes')

Submission status: Wrong Answer

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

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

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

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

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

P.sort(key=lambda a: a[0])
L.sort(key=lambda a: a[0], reverse=True)
P = [s for _, s in P]
L = [s for _, s in L]
ans = ''.join(H) + ''.join(Z) + ''.join(P) + ''.join(L)

l = ans.count('(')
r = ans.count(')')

if l == r and calc(ans) == 0:
    print('Yes')
else:
    print('No')