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())

Lflg = 0
Rflg = 0
LOver = 0

for i in range(N):
    S = input()
    lnum = S.count("(") - S.count(")")
    if S[0] == "(" and ((not S[-1] == ")") or Rflg == 1) and lnum >= 0:
        Lflg = 1
    if S[-1] == ")" and lnum <= 0:
        Rflg = 1
    LOver = LOver + lnum

if Lflg==1 and Rflg==1 and LOver==0:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
input = raw_input

n = int(input())

def f(s):
    l = 0
    n = len(s)
    si = None
    for i in range(n):
        if s[i] == ")":
            l -= 1
        else:
            si = i
            break
    r = 0
    if si is None:
        pass
    else:
        for i in range(si, n):
            if s[i] == "(":
                r += 1
            else:
                r -= 1
    return l, r


ind = 0
pairs = []
ls = []
rs = []

sum_ls = [0, 0]
sum_rs = [0, 0]

sum_l_2 = 0
sum_r_2 = 0

nokori_l = 0
nokori_r = 0

def g1():
    ii = 0
    sum_l = sum_ls[ii]
    sum_r = sum_rs[ii]

    sum_l1 = sum_l
    sum_r1 = r
    mid1 = sum_r + l
    if mid1 < 0:
        sum_l1 += mid1
    else:
        sum_r1 += mid1

    sum_l2 = l
    sum_r2 = sum_r
    mid2 = r + sum_l
    if mid2 < 0:
        sum_l2 += mid2
    else:
        sum_r2 += mid2

    if sum_r2 <= sum_r1:
        sum_l = sum_l2
        sum_r = sum_r2
    else:
        sum_l = sum_l1
        sum_r = sum_r1
    sum_ls[ii] = sum_l
    sum_rs[ii] = sum_r

def g2():
    ii = 1
    sum_l = sum_ls[ii]
    sum_r = sum_rs[ii]

    sum_l1 = sum_l
    sum_r1 = r
    mid1 = sum_r + l
    if mid1 < 0:
        sum_l1 += mid1
    else:
        sum_r1 += mid1

    sum_l2 = l
    sum_r2 = sum_r
    mid2 = r + sum_l
    if mid2 < 0:
        sum_l2 += mid2
    else:
        sum_r2 += mid2

    if sum_r2 <= sum_r1:
    #if sum_r2 < sum_r1:
        sum_l = sum_l2
        sum_r = sum_r2
    else:
        sum_l = sum_l1
        sum_r = sum_r1
    sum_ls[ii] = sum_l
    sum_rs[ii] = sum_r


for i in range(n):
    s = input()
    l, r = f(s)
    if l == 0 and r == 0:
        continue
    elif l != 0 and r != 0:
        g1()
        g2()
    else:
        if l != 0:
            nokori_l += l
        else:
            nokori_r += r

flag = False
for i in range(2):
    sum_l = sum_ls[i]
    sum_r = sum_ls[i]
    right_side = sum_r + nokori_l
    left_side = nokori_r + sum_l

    if left_side >= 0 and right_side <= 0:
        if left_side + right_side == 0:
            flag = True

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

Submission status: Wrong Answer

Solution code:
n = int(input())
l = 0
r = 0
cntl = 0
cntr = 0
fl = 0
fr = 0
exl = 0
exr = 0
only_r = 0
only_l = 0
maxl = 0
maxr = 0
exlr = []
for i in range(n):
    s = input()
    templ = 0
    tempr = 0
    temp_exl = 0
    temp_exr = 0
    fl = 0
    fr = 0
    for i in s:
        if i == "(":
            tempr += 1
        elif i == ")":
            tempr -= 1
            if tempr < 0:
                tempr = 0
                templ += 1
                fl = 1
    temp_exl += templ
    if tempr > 0:
        temp_exr += tempr
        fr = 1
    if fl == 1 and fr == 0:
        only_l += temp_exl
    elif fr == 1 and fl == 0:
        only_r += temp_exr
    elif temp_exl + temp_exr > 0:
        exl += temp_exl
        exr += temp_exr
        exlr.append([temp_exl,temp_exr])
    # maxl = max(maxl,temp_exl)
    # maxr = max(maxr,temp_exr)
# print (exr,exl,only_r,only_l)
a = only_r
b = 0
exlr.sort()
# print(exlr)
for i in exlr:
    a -= i[0]
    if a<0:
        print("No")
        exit()
    a += i[1]
if exl+only_l == exr+only_r and exl-exr == only_r-only_l and only_l > 0 and only_r > 0:
    print("Yes")
elif exr+exl+only_l+only_r == 0:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
input = raw_input

n = int(input())

def f(s):
    l = 0
    n = len(s)
    si = None
    for i in range(n):
        if s[i] == ")":
            l -= 1
        else:
            si = i
            break
    r = 0
    if si is None:
        pass
    else:
        for i in range(si, n):
            if s[i] == "(":
                r += 1
            else:
                r -= 1
    return l, r


ind = 0
pairs = []
ls = []
rs = []

sum_ls = [0, 0]
sum_rs = [0, 0]

sum_l_2 = 0
sum_r_2 = 0

nokori_l = 0
nokori_r = 0

def g1():
    ii = 0
    sum_l = sum_ls[ii]
    sum_r = sum_rs[ii]

    sum_l1 = sum_l
    sum_r1 = r
    mid1 = sum_r + l
    if mid1 < 0:
        sum_l1 += mid1
    else:
        sum_r1 += mid1

    sum_l2 = l
    sum_r2 = sum_r
    mid2 = r + sum_l
    if mid2 < 0:
        sum_l2 += mid2
    else:
        sum_r2 += mid2

    if sum_r2 <= sum_r1:
        sum_l = sum_l2
        sum_r = sum_r2
    else:
        sum_l = sum_l1
        sum_r = sum_r1
    sum_ls[ii] = sum_l
    sum_rs[ii] = sum_r

def g2():
    ii = 1
    sum_l = sum_ls[ii]
    sum_r = sum_rs[ii]

    sum_l1 = sum_l
    sum_r1 = r
    mid1 = sum_r + l
    if mid1 < 0:
        sum_l1 += mid1
    else:
        sum_r1 += mid1

    sum_l2 = l
    sum_r2 = sum_r
    mid2 = r + sum_l
    if mid2 < 0:
        sum_l2 += mid2
    else:
        sum_r2 += mid2

    #if sum_r2 <= sum_r1:
    if sum_r2 < sum_r1:
        sum_l = sum_l2
        sum_r = sum_r2
    else:
        sum_l = sum_l1
        sum_r = sum_r1
    sum_ls[ii] = sum_l
    sum_rs[ii] = sum_r


for i in range(n):
    s = input()
    l, r = f(s)
    if l == 0 and r == 0:
        continue
    elif l != 0 and r != 0:
        g1()
        g2()
    else:
        if l != 0:
            nokori_l += l
        else:
            nokori_r += r

flag = False
for i in range(2):
    sum_l = sum_ls[i]
    sum_r = sum_ls[i]
    right_side = sum_r + nokori_l
    left_side = nokori_r + sum_l

    if left_side >= 0 and right_side <= 0:
        if left_side + right_side == 0:
            flag = True

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

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
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)]

sys.setrecursionlimit(1000000)
mod = 1000000007
class SegmentTree:
    def __init__(self, size, f=max, default=(-float("inf"),0)):
        self.size = 2**(size-1).bit_length()
        self.default = default
        self.dat = [default]*(self.size*2)
        self.f = f

    def update(self, i, x):
        i += self.size
        self.dat[i] = x
        while i > 0:
            i >>= 1
            self.dat[i] = self.f(self.dat[i*2], self.dat[i*2+1])

    def get(self, a, b=None):
        if b is None:
            b = a + 1
        l, r = a + self.size, b + self.size
        lres, rres = self.default, self.default
        while l < r:
            if l & 1:
                lres = self.f(lres, self.dat[l])
                l += 1

            if r & 1:
                r -= 1
                rres = self.f(self.dat[r], rres)
            l >>= 1
            r >>= 1
        res = self.f(lres, rres)
        return res
def solve():
    n = I()
    a = [input() for i in range(n)]
    N = 10**6
    s = [[] for i in range(N+1)]
    for i in range(n):
        p = 0
        m = 0
        for j in a[i]:
            if j == "(":
                p += 1
            else:
                p -= 1
            if p < m:
                m = p
        s[-m].append(p)
    S = SegmentTree(N+1)
    j = [0]*(N+1)
    for m in range(N+1):
        if s[m]:
            S.update(m,(s[m][0],m))
    k = 0
    for _ in range(n):
        p,m = S.get(0,k+1)
        k += p
        if k < 0:
            print("No")
            return
        j[m] += 1
        if j[m] < len(s[m]):
            S.update(m,(s[m][j[m]],m))
        else:
            S.update(m,(-float("inf"),m))
    if k != 0:
        print("No")
    else:
        print("Yes")
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
# ()の問題は折れ線で捉えると良い

N = int(input())
ls = [] # 増減が正のもの(0を含む)
rs = [] # 増減が負のもの

for i in range(N):
    s = input()
    h = 0
    b = 0
    tot = 0
    for c in s:
        if c == "(":
            h += 1
        else:
            h -= 1
        b = min(b, h)
    if h >= 0:
        # 折れ線に対して上っていく奴ら
        ls.append([b, h])
    else:
        # 折れ線に対して下っていく奴ら
        # 右から(hから見るので、最下点は-hする)
        rs.append([b-h, -h])
    tot += h

ls.sort(key = lambda x:x[0], reverse=True)
rs.sort(key = lambda x:x[0], reverse=True)

def check(s):
    h = 0
    for p in s:
        if h+p[0] < 0:
            return False
        h += h+p[1]
    return True

if check(ls) and check(rs) and tot == 0:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


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


def main():
    N = int(input())
    plus = []
    minus = []
    for _ in range(N):
        S = input()
        stack = 0
        m = 0
        for s in S:
            if s == "(":
                stack += 1
            else:
                stack -= 1
            m = min(stack, m)

        if stack > 0:
            plus.append((m, stack))
        else:
            minus.append((m, stack))

    plus.sort(key=lambda x: x[0])
    minus.sort(key=lambda x: x[0], reverse=True)
    m = 0
    cur = 0
    for i, j in plus:
        m += i
        cur += j
        if m < 0:
            print("No")
            return

        m = cur

    for i, j in minus:
        m += i
        cur += j
        if m < 0:
            print("No")
            return

        m = cur

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


if __name__ == "__main__":
    main()

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:
import sys
from collections import deque
def input():
    return sys.stdin.readline().strip()

def check():
    s = input()
    m = 0
    res = 0
    for i in s:
        if i == "(":
            m += 1 
        else:
            m -= 1
            res = min(res,m)
    return [res,m]

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

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

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 a == 0 and b == 0:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
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)]

sys.setrecursionlimit(1000000)
mod = 1000000007
class SegmentTree:
    def __init__(self, size, f=max, default=(-float("inf"),0)):
        self.size = 2**(size-1).bit_length()
        self.default = default
        self.dat = [default]*(self.size*2)
        self.f = f

    def update(self, i, x):
        i += self.size
        self.dat[i] = x
        while i > 0:
            i >>= 1
            self.dat[i] = self.f(self.dat[i*2], self.dat[i*2+1])

    def get(self, a, b=None):
        if b is None:
            b = a + 1
        l, r = a + self.size, b + self.size
        lres, rres = self.default, self.default
        while l < r:
            if l & 1:
                lres = self.f(lres, self.dat[l])
                l += 1

            if r & 1:
                r -= 1
                rres = self.f(self.dat[r], rres)
            l >>= 1
            r >>= 1
        res = self.f(lres, rres)
        return res
def solve():
    n = I()
    a = [input() for i in range(n)]
    N = 10**6
    s = [[] for i in range(N+1)]
    for i in range(n):
        p = 0
        m = 0
        for j in a[i]:
            if j == "(":
                p += 1
            else:
                p -= 1
            if p < m:
                m = p
        s[-m].append(p)
    S = SegmentTree(N+1)
    j = [0]*(N+1)
    for m in range(N+1):
        if s[m]:
            S.update(m,(s[m][0],m))
    k = 0
    for _ in range(n):
        p,m = S.get(k)
        k += p
        if k < 0:
            print("No")
            return
        j[m] += 1
        if j[m] < len(s[m]):
            S.update(m,(s[m][j[m]],m))
        else:
            S.update(m,(-float("inf"),m))
    if k != 0:
        print("No")
    else:
        print("Yes")
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
n = int(input())
a = []
aa = []
for i in range(n):
    c = 0
    c_min = n
    s = input()
    for ss in s:
        c += (ss == "(") * 2 - 1
        c_min = min([c_min, c])
    if c >= 0:
        a.append([c, c_min])
    else:
        aa.append([c, c_min])
    

import numpy as np

a = np.array(a)
aa = np.array(aa)
if len(a) > 0:
    a = a[np.argsort(a[:, 1])[::-1]]
if len(aa) > 0:
    aa = aa[np.argsort(aa[:, 1])[::-1]]
if len(a) > 0 and len(aa) > 0:
    a = np.vstack([a, aa])
elif len(a) > 0 and len(aa) == 0:
    a = a
else:
    a = aa
score = 0
flg = True
for ax in a:
    if score + ax[1] < 0:
        flg = False
        break
    else:
        score += ax[0]

if flg and score == 0:
    print("Yes")
else:
    print("No")

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], key=lambda x:[x[1], x[0]])[::-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:
import sys
n = int(input())
si = []
for _ in range(n):
    s = input()
    l = 0
    r = 0
    count = 0
    for i in range(len(s)):
        if s[i] == "(":
            count += 1
        else:
            count = max(0, count-1)
    l = count
    count = 0
    for i in range(len(s)-1, -1, -1):
        if s[i] == ")":
            count += 1
        else:
            count = max(0, count-1)
    r = count
    si.append((l, r))

if len(si) == 1:
    if si[0] == (0, 0):
        print("Yes")
        sys.exit()

index_l = -1
index_r = -1
maxi_l = 0
maxi_r = 0
for i in range(n):
    a, b = si[i]
    if a == 0:
        if maxi_l < b:
            maxi_l = b
            index_l = i
    if b == 0:
        if maxi_r < a:
            maxi_r = a
            index_r = i

if index_l == -1 or index_r == -1:
    print("No")
    sys.exit()

count = 0
if index_r < index_l:
    count += si.pop(index_l)[1]
    last = si.pop(index_r)
else:
    last = si.pop(index_r)
    count += si.pop(index_l)[1]

minus = []
plus = []
while si:
    a, b = si.pop()
    if a <= b:
        plus.append((a, b))
    else:
        minus.append((a, b))

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

for a, b in plus:
    if count >= a:
        count += b-a
    else:
        print("No")
        sys.exit()

for a, b in minus:
    if count >= a:
        count += b-a
    else:
        print("No")
        sys.exit()

count -= last[0]

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

Submission status: Wrong Answer

Solution code:
def check(s):
    pos = 0
    min_path = 0
    for chr in s:
        if chr == '(':
            pos += 1
        else:
            pos -= 1
            if min_path > pos:
                min_path = pos

    return min_path, pos  # p = 左側に ) が残っている, q = 右側に ( が残っている


n = int(input())
up_list = []
down_list = []
to_zero_down = 0


for _ in range(n):
    s = input()
    min_path, to = check(s)
    if to == 0:
        if to_zero_down > min_path:
            to_zero_down = min_path

    elif to > 0:
        up = to
        up_list.append((min_path, up))

    else:
        down = -to
        down_list.append((min_path, down))


up_list.sort()
down_list.sort()

count = 0
for min_path, up in up_list:
    if count + min_path < 0:
        print('No')
        exit()
    count += up

if count + to_zero_down < 0:
    print('No')
    exit()

for min_path, down in down_list:
    if count + min_path < 0:
        print('No')
        exit()
    count -= down

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

Submission status: Wrong Answer

Solution code:
n = int(input())
l = 0
r = 0
cntl = 0
cntr = 0
fl = 0
fr = 0
exl = 0
exr = 0
only_r = 0
only_l = 0
maxl = 0
maxr = 0
exlr = []
for i in range(n):
    s = input()
    templ = 0
    tempr = 0
    temp_exl = 0
    temp_exr = 0
    fl = 0
    fr = 0
    for i in s:
        if i == "(":
            tempr += 1
        elif i == ")":
            tempr -= 1
            if tempr < 0:
                tempr = 0
                templ += 1
                fl = 1
    temp_exl += templ
    if tempr > 0:
        temp_exr += tempr
        fr = 1
    if fl == 1 and fr == 0:
        only_l += temp_exl
    elif fr == 1 and fl == 0:
        only_r += temp_exr
    else:
        exl += temp_exl
        exr += temp_exr
    if temp_exl + temp_exr > 0:
        exlr.append([temp_exl,temp_exr])
    # maxl = max(maxl,temp_exl)
    # maxr = max(maxr,temp_exr)
# print (exr,exl,only_r,only_l)
a = 0
b = 0
exlr.sort()
# print(exlr)
for i in exlr:
    a = a + i[1] - i[0]
    if a<0:
        print("No")
        exit()

if exl+only_l == exr+only_r and exl-exr == only_r-only_l and only_l > 0 and only_r > 0:
    print("Yes")
elif exr+exl+only_l+only_r == 0:
    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 xr<0:
                    xl-=xr
                    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 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):
    r *= -1
    continue
  if l < x:
    print("No")
    exit(0)
  l += y - x
  #print(l, x, y)
if l + r: print("No")
else: print("Yes")

Submission status: Wrong Answer

Solution code:
def ques():
    n=input()
    open=0
    close=0
    lis=[]
    for _ in range(int(n)):
        co=0
        cc=0
        t=input()
        for i in t:
            if i=="(":
                co+=1
            if i==")":
                if co>=1:
                    co-=1
                else:
                    cc+=1
        if (co,cc)!=(0,0):
            lis.append((cc,co))
    # print(lis)
    if not lis:
        print("Yes")
        return
    lis.sort()
    curr_open=0
    i=0
    while(i<len(lis) and lis[i][0]==0):
        curr_open+=lis[i][1]
        i+=1
    if curr_open==0:
        print("No")
        return
    while(i<len(lis) and curr_open>0):
        curr_open-=lis[i][0]
        if curr_open<0:
            print("No")
            return
        curr_open+=lis[i][1]
        i+=1
    if curr_open==0:
        print("Yes")
    else:
        print("No")
ques()

Submission status: Wrong Answer

Solution code:
n = int(input())
l = 0
r = 0
cntl = 0
cntr = 0
fl = 0
fr = 0
exl = 0
exr = 0
only_r = 0
only_l = 0
maxl = 0
maxr = 0
exlr = []
for i in range(n):
    s = input()
    templ = 0
    tempr = 0
    temp_exl = 0
    temp_exr = 0
    fl = 0
    fr = 0
    for i in s:
        if i == "(":
            tempr += 1
        elif i == ")":
            tempr -= 1
            if tempr < 0:
                tempr = 0
                templ += 1
                fl = 1
    temp_exl += templ
    if tempr > 0:
        temp_exr += tempr
        fr = 1
    if fl == 1 and fr == 0:
        only_l += temp_exl
    elif fr == 1 and fl == 0:
        only_r += temp_exr
    else:
        exl += temp_exl
        exr += temp_exr
    if temp_exl + temp_exr > 0:
        exlr.append([temp_exl,temp_exr])
    # maxl = max(maxl,temp_exl)
    # maxr = max(maxr,temp_exr)
print (exr,exl,only_r,only_l)
a = 0
b = 0
exlr.sort()
# print(exlr)
for i in exlr:
    a = a + i[1] - i[0]
    if a<0:
        print("No")
        exit()

if exl+only_l == exr+only_r and exl-exr == only_r-only_l and only_l > 0 and only_r > 0:
    print("Yes")
elif exr+exl+only_l+only_r == 0:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
n = int(input())
s = []
for i in range(n):
    a = input()
    b = []
    for j in range(len(a)):
        if a[j]=='(':
            b.append(1)
        else:
            b.append(-1)
    s.append(b)

l = []
r = []
for x in s:
    b = 0
    c = 0
    for y in x:
        c+=y
        b = min(b,c)
    z = len(x)
    d = 0
    e = 0
    for j in range(z):
        e += x[z-j-1]
        d = max(d,e)
    if c>0:
        l.append([b,c])
    else:
        r.append([d,c])
l.sort()
r.sort()

flag = 1
x = 0
z =len(l)
for i in range(z):
    b,c = l[z-i-1]
    x += c
    if x+b<0:
        flag = 0
y = 0
for d,c in r:
    y += c
    if y+d>0:
        flag = 0


if y+x!=0:
    flag = 0
print('Yes' if flag else'No')

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


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


def main():
    N = int(input())
    plus = []
    minus = []
    for _ in range(N):
        S = input()
        stack = 0
        m = 0
        for s in S:
            if s == "(":
                stack += 1
            else:
                stack -= 1
            m = min(stack, m)

        if stack > 0:
            plus.append((m, stack))
        else:
            minus.append((m, stack))

    plus.sort(key=lambda x: x[0])
    minus.sort(key=lambda x: x[0], reverse=True)
    m = 0
    cur = 0
    for i, j in plus:
        m += i
        cur += j
        if m < 0:
            print("No")
            return

    for i, j in minus:
        m += i
        cur += j
        if m < 0:
            print("No")
            return

    print("Yes")


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())

Lflg = 0
Rflg = 0
LOver = 0

for i in range(N):
    S = input()
    if S[0] == "(" and ((not S[-1] == ")") or Rflg == 1):
        Lflg = 1
    if S[-1] == ")":
        Rflg = 1
    LOver = LOver + S.count("(") - S.count(")")

if Lflg==1 and Rflg==1 and LOver==0:
    print("Yes")
else:
    print("No")

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])
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())
si = []
for _ in range(n):
    s = input()
    l = 0
    r = 0
    count = 0
    for i in range(len(s)):
        if s[i] == "(":
            count += 1
        else:
            count = max(0, count-1)
    l = count
    count = 0
    for i in range(len(s)-1, -1, -1):
        if s[i] == ")":
            count += 1
        else:
            count = max(0, count-1)
    r = count
    si.append((l, r))

if len(si) == 1:
    if si[0] == (0, 0):
        print("Yes")
        sys.exit()

index_l = -1
index_r = -1
maxi_l = 0
maxi_r = 0
for i in range(n):
    a, b = si[i]
    if a == 0:
        if maxi_l < b:
            maxi_l = b
            index_l = i
    if b == 0:
        if maxi_r < a:
            maxi_r = a
            index_r = i

if index_l == -1 or index_r == -1:
    print("No")
    sys.exit()

count = 0
if index_r < index_l:
    count += si.pop(index_l)[1]
    last = si.pop(index_r)
else:
    last = si.pop(index_r)
    count += si.pop(index_l)[1]

minus = []
plus = []
while si:
    a, b = si.pop()
    if a <= b:
        plus.append((a, b))
    else:
        minus.append((a, b))

plus.sort()
minus.sort(reverse = True)

for a, b in plus:
    if count >= a:
        count += b-a
    else:
        print("No")
        sys.exit()
for a, b in minus:
    if count >= a:
        count += b-a
    else:
        print("No")
        sys.exit()

count -= last[0]

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

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 = [(m[i], s[i]) for i in range(N)]
    ss.sort(key=lambda x: (x[0], x[1]), reverse=True)
    tmp = 0
    for x, y in ss:
        if tmp + x < 0:
            print("No")
            exit(0)
        tmp += y

    print("Yes")

else:
    print("No")

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], reverse=True)
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")