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:
class SegmentTree:
    def __init__(self, data, default=0, func=lambda a,b:a+b):
        """initialize the segment tree with data"""
        self._default = default
        self._func = func
        self._len = len(data)
        self._size = _size = 1 << (self._len - 1).bit_length()

        self.data = [default] * (2 * _size)
        self.data[_size:_size + self._len] = data
        for i in reversed(range(_size)):
            self.data[i] = func(self.data[i + i], self.data[i + i + 1])

    def __delitem__(self, idx):
        self[idx] = self._default

    def __getitem__(self, idx):
        return self.data[idx + self._size]

    def __setitem__(self, idx, value):
        idx += self._size
        self.data[idx] = value
        idx >>= 1
        while idx:
            self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
            idx >>= 1

    def __len__(self):
        return self._len

    def query(self, start, stop):
        if start == stop:
            return self.__getitem__(start)
        stop += 1
        start += self._size
        stop += self._size

        res = self._default
        while start < stop:
            if start & 1:
                res = self._func(res, self.data[start])
                start += 1
            if stop & 1:
                stop -= 1
                res = self._func(res, self.data[stop])
            start >>= 1
            stop >>= 1
        return res

    def __repr__(self):
        return "SegmentTree({0})".format(self.data)


# ------------------- fast io --------------------
import os
import sys
from io import BytesIO, IOBase

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

# ------------------- fast io --------------------
from bisect import bisect_right, bisect_left
from fractions import Fraction

def pre(s):
    n = len(s)
    pi=[0]*n
    for i in range(1,n):
        j = pi[i-1]
        while j and s[i] != s[j]:
            j = pi[j-1]
        if s[i] == s[j]:
            j += 1
        pi[i] = j
    return pi

def prod(a):
    ans = 1
    for each in a:
        ans = (ans * each)
    return ans

from math import gcd
def lcm(a,b):return a*b//gcd(a,b)


n = int(input())

group1 = ['']
group2 = {}

for _ in range(n):
    s = input()
    c = 0
    minnc = 0
    for i in s:
        if i == "(": c += 1
        else: c -= 1
        minnc = min(minnc, c)
    if minnc >= 0:
        group1 += [s]
        continue

    if minnc not in group2:
        group2[minnc] = {c: [s]}
    elif c not in group2[minnc]:
        group2[minnc][c] = [s]
    else:
        group2[minnc][c] += [s]


ans = "".join(group1)

ok = sorted([i for i in group2])

for i in ok:
    ook = sorted([j for j in group2[i]], reverse=True)
    for j in ook:
        ans += "".join(group2[i][j])

#print(ans)
c = 0
minnc = 0
for i in ans:
    if i == "(": c += 1
    else: c -= 1
    minnc = min(minnc, c)

print("Yes" if c == 0 and minnc >= 0 else "No")

Submission status: Wrong Answer

Solution code:
import sys
n=int(input())
lr=[]
def g(s):
    i = 0
    l = [0]
    for j in s:
        if j =="(":
            i += 1
        else:
            i -= 1
        l.append(i)
    return min(l),max(l)
for _ in range(n):
    s = input()
    l = s.count("(")
    r = len(s) - l
    mi,ma =g(s)
    lr.append((mi,ma,l,r))
lr.sort(key=lambda x:-x[0])
cnt = 0
for mi,ma,l,r in lr:
    #print(cnt)
    if cnt+mi>=0:
        cnt += (l-r)
    else:
        print("No")
        sys.exit()
if cnt !=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 = 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)]

tozan = []
gezan = []

for res,m in S:
    if res >= 0:
        tozan.append([res,m])
    else:
        gezan.append([res-m,m])

tozan.sort(reverse=True)
gezan.sort(reverse=True)


b = 0

for _,m in tozan:
    b += m

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

if b == 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 lr:
    if llst-rlst==0:
        print("Yes")
    else:
        print("No")
    exit()

idleR=10**7

def main(n,xl,xr):
    X=xl+idleR*xr
    if  not dp[n][X]:
        dp[n][X]=1
        stack.append([n,xl,xr])
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]

        if r<L:
            main(n+1,L-r+l,R)
        else:
            main(n+1,l,R+r-L)

        if l<R:
            main(n+1,L,r+R-l)
        else:
            main(n+1,L+l-R,r)





    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:
# -*- coding: utf-8 -*-
import sys
# sys.setrecursionlimit(10**6)
buff_readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, S):
    b = []
    for s in S:
        bottom = 0
        cur = 0
        for c in s:
            if c == '(':
                cur += 1
            else:
                cur -= 1
            bottom = min(bottom, cur)
        b.append((bottom, cur))

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

    cur = 0
    for bt, ct in b:
        if cur + bt < 0:
            return 'No'
        cur += ct

    if cur != 0:
        return 'No'
    return 'Yes'



def main():
    N = read_int()
    S = [read_str() for _ in range(N)]
    print(slv(N, S))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

A = [0 for i in range(N)]

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

from operator import itemgetter

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

d = 0
e = 0

for i in range(N):
    if -e > A[i][1]:
        print('No')
        exit()
    else:
        d += A[i][0]
        e += A[i][0]
else:
    if d == 0 and e == 0:
        print('Yes')
    else:
        print('No')

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
# sys.setrecursionlimit(10**6)
buff_readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, S):
    b = []
    for s in S:
        bottom = 0
        cur = 0
        for c in s:
            if c == '(':
                cur += 1
            else:
                cur -= 1
            bottom = min(bottom, cur)
        b.append((bottom, cur))

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

    cur = 0
    for bt, ct in b:
        if cur < bt:
            return 'No'
        cur += ct

    if cur != 0:
        return 'No'
    return 'Yes'



def main():
    N = read_int()
    S = [read_str() for _ in range(N)]
    print(slv(N, S))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
s = [input() for _ in range(n)]
x = []
for i in range(n):
    cnt = 0
    for j in range(len(s[i])):
        if s[i][j] == '(':
            cnt += 1
        else:
            cnt -= 1
    x.append((cnt, s[i]))
x.sort(reverse=True)
f = deque()
b = deque()
stack = []
for _, v in x:
    if v[0] == '(':
        f.append(v)
    else:
        b.append(v)

while f:
    v = f.popleft()
    for i in v:
        if i == '(':
            stack.append(i)
        else:
            if stack:
                stack.pop()
            else:
                print('No')
                quit()
while b:
    v = b.popleft()
    for i in v:
        if i == '(':
            stack.append(i)
        else:
            if stack:
                stack.pop()
            else:
                print('No')
                quit()
if stack:
    print('No')
else:
    print('Yes')

Submission status: Wrong Answer

Solution code:
#!python3

def LI():
    return list(map(int, input().split()))

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


def main():
    pl, ml = [], []
    for i in range(N):
        l = 0
        b = 0
        for s in S[i]:
            if s == "(":
                l += 1
            else:
                l -= 1
                b = min(b, l)
        if l > 0:
            pl.append((-b, l))
        else:
            ml.append((-l, -b))
    pl.sort()
    ml.sort()

    x = 0
    for b, l in pl:
        if x + b < 0:
            print("No")
            return
        x += l
    for l, b in ml:
        if x - b < 0:
            print("No")
            return
        x -= l
    if x == 0:
        print("Yes")
    else:
        print("No")


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
n=int(input())
lr=[]
def g(s):
    i = 0
    l = [0]
    for j in s:
        if j =="(":
            i += 1
        else:
            i -= 1
        l.append(i)
    return min(l),max(l)
for _ in range(n):
    s = input()
    l = s.count("(")
    r = len(s) - l
    mi,ma =g(s)
    lr.append((mi,ma,l,r))
    
cnt = 0
for mi,ma,l,r in lr:
    #print(cnt)
    if cnt+mi>=0:
        cnt += (l-r)
    else:
        print("No")
        sys.exit()
if cnt !=0:
    print("No")
else:
    print("Yes")

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, down))


up_list.sort(reverse=True)
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:
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)
    ##下山するときには反転する(resが小さいものから貪欲にとる)
    if res < 0:
        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 = b + res
    if a < 0:
        print("No")
        exit()
    b += m

if b == 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()
from functools import cmp_to_key
def resolve():
    n = int(input())
    S = [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)
        S[i] = (min_balance, balance)

    def cmp(s1, s2):
        m1, b1 = s1
        m2, b2 = s2
        return -1 if min(m1, b1 + m2) > min(m2, b2 + m1) else 1

    S.sort(key = cmp_to_key(cmp))
    now = 0
    for min_balance, balance in S:
        if now + min_balance < 0:
            print("No")
            return
        now += balance

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

Submission status: Wrong Answer

Solution code:
from collections import deque,defaultdict
import bisect
N = int(input())
S = [input() for i in range(N)]

class SegmentTree:
    def __init__(self,data,op,default):
        N = len(data)
        self.N = N
        self.op = op
        self.default = default
        self.l = 2**((N-1).bit_length())
        self.data = [default]*self.l + data + [default]*(self.l-N)
        for i in range(self.l-1,0,-1):
            self.data[i] = op(self.data[2*i], self.data[2*i+1])

    def set(self,i,val):
        i += self.l
        self.data[i] = val
        i = i//2
        while i > 0:
            self.data[i] = self.op(self.data[2*i], self.data[2*i+1])
            i = i//2

    def get(self,i,j):
        i += self.l
        j += self.l
        s = self.default 
        while j-i > 0:
            if i & 1:
                s = self.op(s,self.data[i])
                i += 1
            if j & 1:
                s = self.op(s,self.data[j-1])
                j -= 1
            i = i//2
            j = j//2
        return s

def bend(s):
    res = 0
    k = 0
    for th in s:
        if th == '(':
            k += 1
        else:
            k -= 1
        res = min(k,res)
    return res

LmR = defaultdict(list)
inf = -10**7
for s in S:
    LmR[bend(s)].append(s.count('(')-s.count(')'))
LmR = dict(LmR)
for k in LmR.keys():
    LmR[k].append(inf)
    LmR[k].sort(reverse=True)
    LmR[k] = deque(LmR[k])

keys = sorted(LmR.keys())
nk = len(keys)

comp = {k:i for i,k in enumerate(keys)}
seg = SegmentTree([(LmR[k].popleft(),k) for k in keys], lambda x,y : (x if x[0] > y[0] else y), (inf,inf))

cumsum = 0
for i in range(N):
    ind = bisect.bisect_left(keys,-cumsum)
    m,n = seg.get(ind,nk)
    if n == inf or m == inf:
        print('No')
        exit()
    if cumsum + n < 0:
        print('No')
        exit()
    cumsum += m
    new = LmR[n].popleft()
    seg.set(comp[n], (new,n))

if cumsum == 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, down))


up_list.sort(reverse=True)
down_list.sort(reverse=True)

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:
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[2]>=0,st)),list(filter(lambda x:x[2]<0,st))
v.sort(reverse=True,key=lambda z:z[1])
#v.sort(reverse=True,key=lambda z:z[2])
lu=len(u)
now2=0
for i in range(n):
    if i<lu:
        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

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], reverse=True)
    minus.sort(key=lambda x: x[0])
    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:
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 = []
 
n_cond = 2
sum_ls = [0, 0]
sum_rs = [0, 0]
nokori_l = 0
nokori_r = 0
for i in range(n):
    s = input()
    l, r = f(s)
    if l == 0 and r == 0:
        continue
    elif l != 0 and r != 0:
        for cond_i in range(n_cond):
            sum_l = sum_ls[cond_i]
            sum_r = sum_rs[cond_i]

            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 cond_i == 0:
                if sum_r2 <= sum_r1:
                    sum_l = sum_l2
                    sum_r = sum_r2
                else:
                    sum_l = sum_l1
                    sum_r = sum_r1
            else:
                if sum_r2 < sum_r1:
                    sum_l = sum_l2
                    sum_r = sum_r2
                else:
                    sum_l = sum_l1
                    sum_r = sum_r1

            sum_ls[cond_i] = sum_l
            sum_rs[cond_i] = sum_r

    else:
        if l != 0:
            nokori_l += l
        else:
            nokori_r += r
 
flag = False
for cond_i in range(n_cond):
    sum_l = sum_ls[cond_i]
    sum_r = sum_rs[cond_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:
            #print("Yes")
            flag = True
        else:
            #print("No")
            pass
    else:
        #print("No")
        pass

if flag:
    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[2]>=0,st)),list(filter(lambda x:x[2]<0,st))
v.sort(reverse=True,key=lambda z:z[1])
v.sort(reverse=True,key=lambda z:z[2])
lu=len(u)
now2=0
for i in range(n):
    if i<lu:
        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:
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:
    sp = [(m[i], s[i]) for i in range(N) if s[i] > 0]
    mp = [(-(s[i]-m[i]), -s[i]) for i in range(N) if s[i] <= 0]
    sp.sort(key=lambda x: x[0], reverse=True)
    tmp = 0
    for x, y in sp:
        if tmp + x < 0:
            print("No")
            exit(0)
        tmp += y
    mp.sort(key=lambda x: x[0], reverse=True)
    tmp2 = 0
    for x, y in sp:
        if tmp2 + x < 0:
            print("No")
            exit(0)
        tmp2 += y
    print("Yes")

else:
    print("No")

Submission status: Wrong Answer

Solution code:
import sys
from itertools import permutations
readline = sys.stdin.readline

n = int(readline())
s = [readline().strip() for i in range(n)]

comb_s = list(permutations(s, n))

def checker(x):
    if not x: return 0

    if x[0] != '(' or x[-1] != ')': return 0

    r = x.count('(')
    l = x.count(')')
    if r != l: return 0

    return 1

def main():
    for i in range(len(comb_s)):
        print(''.join( [j for j in comb_s[i]]))
        jud = checker(''.join( [j for j in comb_s[i]]))
        if jud == 1:
            print('Yes')
            return

    print('No')
    return

main()

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 = []
 
n_cond = 2
sum_ls = [0, 0]
sum_rs = [0, 0]
nokori_l = 0
nokori_r = 0
for i in range(n):
    s = input()
    l, r = f(s)
    if l == 0 and r == 0:
        continue
    elif l != 0 and r != 0:
        for cond_i in range(n_cond):
            sum_l = sum_ls[cond_i]
            sum_r = sum_rs[cond_i]

            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 cond_i == 0:
                if sum_r2 <= sum_r1:
                    sum_l = sum_l2
                    sum_r = sum_r2
                else:
                    sum_l = sum_l1
                    sum_r = sum_r1
            else:
                if sum_r2 <= sum_r1:
                    sum_l = sum_l2
                    sum_r = sum_r2
                else:
                    sum_l = sum_l1
                    sum_r = sum_r1

            sum_ls[cond_i] = sum_l
            sum_rs[cond_i] = sum_r

    else:
        if l != 0:
            nokori_l += l
        else:
            nokori_r += r
 
flag = False
for cond_i in range(n_cond):
    sum_l = sum_ls[cond_i]
    sum_r = sum_rs[cond_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:
            #print("Yes")
            flag = True
        else:
            #print("No")
            pass
    else:
        #print("No")
        pass

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

Submission status: Wrong Answer

Solution code:
n = int(input())
li = []

for _ in range(n):
    s = input()
    count = 0
    while True:
        if count + 1 >= len(s):
            break
        if s[count] == '(' and s[count+1] == ')':
            s = s[:count] + s[count+2:]
            count = max(0, count-1)
        else:
            count += 1
    li.append(s)

li2 = []
for i in li:
    count = 0
    for j in range(len(i)):
        if i[j] == ')':
            count += 1
        else:
            break
    li2.append((len(i) - count, count))

now = [0,0]
for l,r in li2:
    if l == 0 and r == 0:
        pass
    elif r == 0:
        if now[1] == 0:
            now[0] += l
        elif 0 < now[1] <= l:
            now[0] += l - now[1]
            now[1] = 0
        else:
            now[1] -= l
    elif l == 0:
        if now[0] == 0:
            now[1] += r
        elif 0 < now[0] <= r:
            now[1] += r - now[0]
            now[0] = 0
        else:
            now[0] -= r
    else:
        if min(now[0], l) > min(now[1], r):
            if now[0] > l:
                now[0] -= l
            else:
                now[1] += l - now[0]
                now[0] = 0
        else:
            if now[1] > r:
                now[1] -= r
            else:
                now[0] += r - now[1]
                now[1] = 0

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

else:
    print("No")