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:
#!python3

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

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


def main():
    l, r = [None] * N, [None] * N
    lstart, rstart = [], []
    for i in range(N):
        l[i] = S[i].count("(")
        r[i] = len(S[i]) - l[i]
        if S[i][0] == "(":
            lstart.append(i)
        if S[i][-1] == ")":
            rstart.append(i)
    
    if sum(l) != sum(r):
        print("No")
        return
    
    if len(lstart) == 0 or len(rstart) == 0:
        print("No")
        return
    
    if len(lstart) == 1 and len(rstart) == 1:
        if lstart[0] == rstart[0]:
            print("No")
            return
    
    print("Yes")


if __name__ == "__main__":
    main()

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

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

print('Yes' if tl and tr and L == R else 'No')

Submission status: Wrong Answer

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

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

A = [[], [], []]

u = 0

for i in range(n):
    a = 0
    b = 0
    for j in range(len(S[i])):
        if S[i][j] == "(":
            a += 1
        else:
            a -= 1
            b = min(b, a)
    u += a
    if a > 0:
        A[0].append([b, a])
    elif a == 0:
        A[1].append([b, a])
    else:
        A[2].append([a-b, a])



if u != 0:
    print("No")
    sys.exit()

# print(A)

A[0].sort(reverse=True)
A[2].sort(reverse=True)

# print(A)


ng = 0
a = 0
for i in range(len(A[0])):
    a += A[0][i][0]
    if a < 0:
        ng = 1
        break
    a += A[0][i][1]-A[0][i][0]
    if a < 0:
        ng = 1
        break

if ng == 0:
    for i in range(len(A[1])):
        a += A[1][i][0]
        if a < 0:
            ng = 1
            break
        a -= A[1][i][0]

if ng == 0:
    for i in range(len(A[2])):
        aa = A[2][i][1]
        bb = aa-A[2][i][0]
        a += aa
        if a < 0:
            ng = 1
            break
        a += bb-aa
        if a < 0:
            ng = 1
            break

# print(a)

if ng == 1:
    print("No")
else:
    print("Yes")

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# vim: set fileencoding=utf-8

# pylint: disable=unused-import, invalid-name, missing-docstring, bad-continuation


"""Module docstring
"""

import functools
import heapq
import itertools
import logging
import math
import random
import string
import sys
from argparse import ArgumentParser
from collections import defaultdict, deque
from copy import deepcopy
from typing import Dict, List, Optional, Set, Tuple


def solve(values: List[str]) -> bool:
    counts = []
    total_closing = 0
    total_opening = 0
    for v in values:
        opening = 0
        closing = 0
        for c in v:
            if c == ")":
                if opening == 0:
                    closing += 1
                else:
                    opening -= 1
            if c == "(":
                opening += 1
        if closing + opening != 0:
            counts.append((closing, opening))
            total_opening += opening
            total_closing += closing
    LOG.debug((counts))
    if not counts:
        return True
    for opening, closing in counts:
        if opening == total_closing - closing and closing == total_opening - opening:
            return True
    return False


def do_job():
    "Do the work"
    LOG.debug("Start working")
    # first line is number of test cases
    N = int(input())
    values = []
    for _ in range(N):
        values.append(input().strip())
    result = solve(values)
    print("Yes" if result else "No")


def print_output(testcase: int, result) -> None:
    "Formats and print result"
    if result is None:
        result = "IMPOSSIBLE"
    print("Case #{}: {}".format(testcase + 1, result))
    # 6 digits float precision {:.6f} (6 is the default value)
    # print("Case #{}: {:f}".format(testcase + 1, result))


def configure_log() -> None:
    "Configure the log output"
    log_formatter = logging.Formatter("%(lineno)d - " "%(message)s")
    handler = logging.StreamHandler(sys.stdout)
    handler.setFormatter(log_formatter)
    LOG.addHandler(handler)


LOG = None
# for interactive call: do not add multiple times the handler
if not LOG:
    LOG = logging.getLogger("template")
    configure_log()


def main(argv=None):
    "Program wrapper."
    if argv is None:
        argv = sys.argv[1:]
    parser = ArgumentParser()
    parser.add_argument(
        "-v",
        "--verbose",
        dest="verbose",
        action="store_true",
        default=False,
        help="run as verbose mode",
    )
    args = parser.parse_args(argv)
    if args.verbose:
        LOG.setLevel(logging.DEBUG)
    do_job()
    return 0


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    sys.exit(main())


class memoized:
    """Decorator that caches a function's return value each time it is called.
    If called later with the same arguments, the cached value is returned, and
    not re-evaluated.
    """

    def __init__(self, func):
        self.func = func
        self.cache = {}

    def __call__(self, *args):
        try:
            return self.cache[args]
        except KeyError:
            value = self.func(*args)
            self.cache[args] = value
            return value
        except TypeError:
            # uncachable -- for instance, passing a list as an argument.
            # Better to not cache than to blow up entirely.
            return self.func(*args)

    def __repr__(self):
        """Return the function's docstring."""
        return self.func.__doc__

    def __get__(self, obj, objtype):
        """Support instance methods."""
        return functools.partial(self.__call__, obj)

Submission status: Wrong Answer

Solution code:
import sys


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


N = int(input())
print('Yes') if sum(sum(1 if c == '(' else -1 for c in input()) for _ in range(N)) == 0 else print('No')

Submission status: Wrong Answer

Solution code:

import collections


def solve(n, strings):
    stringBalances = []
    totalBalance = 0

    for s in strings:
        bal = 0
        stack, isValid = [], True

        for ch in s:
            if ch == '(':
                bal += 1
                stack.append("(")
            else:
                bal -= 1

                if not stack:
                    isValid = False
                    continue

                stack.pop()

        stringBalances.append((bal, isValid and not stack))
        totalBalance += bal

    # print(stringBalances)
    sums = sum([isValid == False for bal, isValid in stringBalances])
    # print(totalBalance)
    # print(sums)

    return totalBalance == 0 and (sums % 2 == 0)


n = int(input().strip())

strings = []

for i in range(n):
    string = input().strip()
    strings.append(string)

print("Yes" if solve(n, strings) else "No")

Submission status: Wrong Answer

Solution code:
N=int(input())

cand=[]
for _ in range(N):
    cand.append(input())
    
cand.sort(key=lambda x : x.count(")")-x.count("("))

ans=("".join(cand))

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

Submission status: Wrong Answer

Solution code:
import sys
from operator import itemgetter

def solve():
    input = sys.stdin.readline
    N = int(input())
    Left = []
    leftZ, rightZ = [], []
    for _ in range(N):
        S = input().strip("\n")
        N = len(S)
        aL, aR = 0, 0
        #自身より左にある"("
        r = 0
        for i in range(N):
            if S[i] == ")":
                if r == 0: aL += 1
                else: r -= 1
            else: r += 1
        l = 0
        for i in range(N):
            if S[N-1-i] == "(":
                if l == 0: aR += 1
                else: l -= 1
            else: l += 1
        Left.append((aL, aR))
    Left.sort(key = itemgetter(1), reverse = True)
    Left.sort(key = itemgetter(0))
    
    #print(Left)
    rightOver = 0
    for aL, aR in Left:
        rightOver -= aL
        if rightOver < 0:
            print("No")
            break
        rightOver += aR
    else:
        if rightOver == 0: print("Yes")
        else: print("No")

    return  0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
n=int(input())
lipp = []
lipm = []
limm = []
allcnt = 0
for _ in range(n):
    s = input()
    cnt = 0
    mi = 0
    for x in s:
        if x == ')':
            cnt -= 1
            mi = min(mi,cnt)
        else:
            cnt += 1
    if mi == 0:
        lipp.append(cnt)
    elif cnt >= 0:
        lipm.append([mi,cnt])
    else:
        limm.append([mi,cnt])
    allcnt += cnt
if allcnt != 0:
    print('No')
    exit()

now = sum(lipp)
lipm.sort(reverse = True)
limm.sort(reverse = True)

for mi, cnt in lipm:
    if mi + now < 0:
        print('No')
        exit()
    now += cnt

for mi, cnt in limm:
    if now+mi < 0:
        print('No')
        exit()
    now += cnt
print("Yes")

Submission status: Wrong Answer

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def f(S):
    worst = 0
    res = 0
    for s in S:
        if(s=='('):
            res += 1
        else:
            res -= 1
        worst = min(worst, res)
    return worst, res
def main():
    N=I()
    S=[ST() for _ in range(N)]
    
    AB_nega=[]
    AB_nonnega=[]
    for i in range(N):
        a,b = f(S[i])
        if b<0:
            AB_nega.append((a,b))
        else:
            AB_nonnega.append((a,b))
    
    AB_nega.sort(key=lambda x:sum(x), reverse =True)
    AB_nonnega.sort(reverse = True)

    # print(AB_nega)
    # print(AB_nonnega)

    now = 0
    for a,b in AB_nonnega:
        if(now+a < 0):
            print("No")
            return
        now += b
        # print(now,"#######")
    
    
    for a,b in AB_nega:
        if(now+a<0):
            print("No")
            return
        now += b
        # print(now,"#########")
    if now == 0:
        print('Yes')
    else:
        print("No")


    
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
s = [input() for _ in range(n)]


def func(x):
    ret = []
    for i in range(len(x)):
        if len(ret) == 0:
            ret.append(x[i])
        else:
            if ret[-1] == '(' and x[i] == ')':
                ret.pop()
            else:
                ret.append(x[i])
    l = r = 0
    for i in range(len(ret)):
        if ret[i] == '(':
            l += 1
        else:
            r += 1
    return (r, l)  # ) (


t = []
for i in range(n):
    r, l = func(s[i])
    # print((r, l), '<-', s[i])
    if r + l == 0:
        continue
    t.append((r, l))
t.sort()
# print(*t, sep='\n')

is_possible = True
if len(t) > 0:
    r, l = t[0]
    if r != 0:
        is_possible = False
    else:
        for i in range(1, len(t)):
            r_i, l_i = t[i]
            if r_i <= l:
                l -= r_i
                l += l_i
            else:
                is_possible = False
        if l != 0:
            is_possible = False

ans = 'Yes' if is_possible else 'No'
print(ans)

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)

# log(ngs)

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("".join(strs))

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

Submission status: Wrong Answer

Solution code:
from collections import Counter, defaultdict, deque

(N,) = [int(x) for x in input().split()]
brackets = [input() for i in range(N)]

delta = []
minDelta = []
for s in brackets:
    balance = 0
    mn = 0
    for c in s:
        if c == "(":
            balance += 1
        else:
            balance -= 1
        mn = min(mn, balance)
    delta.append(balance)
    minDelta.append(mn)

if sum(delta) == 0:
    posIndices = [i for i in range(N) if delta[i] > 0]
    posIndices.sort(key=lambda i: (minDelta[i], -delta[i]))

    eqIndices = [i for i in range(N) if delta[i] == 0]

    negIndices = [i for i in range(N) if delta[i] < 0]
    negIndices.sort(key=lambda i: (-minDelta[i], delta[i]))
    balance = 0
    for i in posIndices + eqIndices + negIndices:
        if balance + minDelta[i] < 0 or balance + delta[i] < 0:
            print("No")
            exit()
        balance += delta[i]
    assert balance == 0

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

Submission status: Wrong Answer

Solution code:
n = int(input())
brackets = []  # (始めを0として、( = +1, ) = -1 として、最後はいくつか, 途中の最小値はいくつか)
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)
    brackets.append((total - mini, total, mini))
brackets.sort(reverse=True)

ct = 0
for _, t, m in brackets:
    if ct + m < 0:
        print('No')
        exit()
    ct += t
if ct == 0:
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

Solution code:
n = int(input())
s = [0] * n
inc = []
zeros = []
dec = []

for i in range(n):
    s[i] = input()
    start = 0
    minimum = 0
    now = 0
    for c in s[i]:
        if c == '(':now += 1
        else: now -= 1
        minimum = min(minimum, now)
    end = now
    
    if end == 0:
        zeros.append((minimum, i))
    elif start < end:
        inc.append((minimum, i))
    else:
        minimum = minimum - end
        dec.append((minimum, i))

inc.sort(reverse=True)
dec.sort()

exit()
ans = ""
for (m, i) in inc:
    ans += s[i]

for (m, i) in zeros:
    ans += s[i]

for (m, i) in dec:
    ans += s[i]

now = 0

for c in ans:
    if c == '(':now += 1
    else: now -= 1
    if now < 0:
        print("No")
        exit()

if now != 0:
    print("No")
else:
    print("Yes")

Submission status: Wrong Answer

Solution code:
import sys
# input = sys.stdin.readline
# sys.setrecursionlimit(10 ** 9)
MOD = 10 ** 9 + 7

N = int(input())


tmp = 0
lst = []
lst_append = lst.append

for i in range(N):
    S = list(input())
    min_ = 0
    total = 0
    for s in S:
        if s == '(':
            total += 1
        else:
            total -= 1
            min_ = min(min_, total)
    if min_ == 0:
       tmp += total
    else:
        lst_append([min_, total])

lst.sort(key = lambda x: x[0], reverse = False) #途中で小さくなるものから優先的に入れる

for a, b in lst:
    if tmp + a < 0:
        print ('No')
        exit()
    else:
        tmp -= b

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

Submission status: Wrong Answer

Solution code:
import heapq
import os

import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

N = int(sys.stdin.buffer.readline())
S = [sys.stdin.buffer.readline().decode().rstrip() for _ in range(N)]


def solve():
    diffs = []
    max_downs = []
    for s in S:
        diff = 0
        mi = 0
        for c in s:
            diff += 1 if c == '(' else -1
            mi = min(diff, mi)
        diffs.append(diff)
        max_downs.append(-mi)

    if sum(diffs) != 0:
        return False

    positives = []
    zeros = []
    negatives = []
    for i, d in enumerate(diffs):
        if d > 0:
            positives.append((max_downs[i], d, i))
        elif d < 0:
            negatives.append((-max_downs[i], d, i))
        else:
            zeros.append((max_downs[i], d, i))

    heapq.heapify(positives)
    heapq.heapify(zeros)
    heapq.heapify(negatives)
    pos = 0
    while positives:
        down, diff, i = heapq.heappop(positives)
        if down > pos:
            return False
        pos += diff

    while zeros:
        down, diff, i = heapq.heappop(zeros)
        if down > pos:
            return False
        pos += diff

    while negatives:
        down, diff, i = heapq.heappop(negatives)
        down = -down
        if down > pos:
            return False
        pos += diff
    assert pos == 0
    return True


ok = solve()
if ok:
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

Solution code:
def RunLengthEncoding(S):
    res = []
    N = len(S)
    i = 0
    while i < N:
        cnt = 1
        while i < N - 1 and S[i] == S[i + 1]:
            cnt += 1
            i += 1
        res.append([S[i], cnt])
        i += 1

    while True:
        res2 = omit(res)
        if res == res2:
            return res2
        res = res2


def omit(RLE):
    res = []
    i = 0
    while i < len(RLE):
        k, v = RLE[i]
        if k == ")":
            res.append([k, v])
            i += 1
            continue
        if i >= len(RLE) - 1:
            res.append([k, v])
            break

        kk, y = RLE[i + 1]
        if v > min(v, y):
            res.append([k, v - min(v, y)])
        if y > min(v, y):
            res.append([kk, y - min(v, y)])
        i += 2
    if res:
        res = merge(res)
    return res


def merge(RLE):
    res = []
    res.append(RLE[0])
    for i in range(1, len(RLE)):
        k, v = RLE[i]
        if res[-1][0] != k:
            res.append([k, v])
        else:
            res[-1][1] += v
    return res


if __name__ == "__main__":
    N = int(input())
    tmp = []
    for _ in range(N):
        RLE = RunLengthEncoding(input())
        if RLE:
            tmp.append(RLE)

    tmp.sort()
    match = 0
    for b in tmp:
        for k, v in b:
            if k == "(":
                match += v
            else:
                if match < v:
                    print("No")
                    exit()
                match -= v
    if match == 0:
        print("Yes")
    else:
        print("No")

Submission status: Wrong Answer

Solution code:
N=int(input())
S=[input() for _ in range(N)]
nums=[0]*N
hefo=0
head=0
foot=0
for i in range(N):
  x=len(S[i])
  tmp=S[i].count('(')
  nums[i]=tmp-(x-tmp)
  
  if S[i][0]=='(':
    if S[i][-1]==')':
      hefo+=1
    else:
      head+=1
  elif S[i][-1]==')':
    foot+=1
    
if sum(nums)==0:
  if head>0 and foot>0:
    print('Yes')
  elif head>0 and hefo>0:
    print('Yes')
  elif foot>0 and hefo>0:
    print('Yes')
  elif hefo>=2:
    print('Yes')
  else:
    print('No')
else:
  print('No')

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
import os
import sys
from io import BytesIO, IOBase

def main():
    n=int(input())
    N=10**6+2

    pv=[]
    nv=[]


    for _ in range(n):
        c,o=0,0
        for x in input():
            if x=='(':
                o+=1
            else:
                if o:
                    o-=1
                else:
                    c+=1
        if o>=c:
            pv.append([c,o-c])
        else:
            nv.append([c,o-c])
        # c par o-c add kardo

    # print(pv)
    # print(nv)
    pv.sort()
    nv.sort()
    nv=nv[::-1]
    # print(pv)
    # print(nv)
    
    cur=0
    for a in pv:
        if a[0]>cur:
            print("No")
            exit(0)
        cur+=a[1]
    
    for a in nv:
        if a[0]>cur:
            print("No")
            exit(0)
        cur+=a[1]
    
    print("Yes" if cur==0 else "No")


# region fastio

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

# endregion

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n,*s=open(0)
n=int(n)
if n==1:
    t=s[0]
    c=l=r=d=0
    for u in t[:-1]:
        if u=='(':
            if d<0:d=0
            d+=1
            r+=1
        else:
            d-=1
            if d>=0:c+=1
            l+=1
    x=r-c
    y=l-c
    if x==y==0:
        print('Yes')
    else:
        print('No')
    exit()
f=g=h=a=b=0
for t in s:
    c=l=r=d=0
    for u in t[:-1]:
        if u=='(':
            if d<0:d=0
            d+=1
            r+=1
        else:
            d-=1
            if d>=0:c+=1
            l+=1
    x=r-c
    y=l-c
    if x==y==0:h+=1
    elif x==0:f=1
    elif y==0:g=1
    a+=x
    b+=y
if (h > 1 or (h and (f or g)) or f and g) and a==b:
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.read

n = int(input())
ss = read().split()

cnt_p = []
cnt_m = []
for i in range(n):
    left = 0
    right = 0
    for s in ss[i]:
        if(s == '('):
            left += 1
        elif(s == ')'):
            if(left > 0):
                left -= 1
            else:
                right += 1
    if(left-right > 0):
        cnt_p.append((right,left))
    else:
        cnt_m.append((right,left))


cnt_p = sorted(cnt_p, key=lambda x: (x[0]))
cnt_m = sorted(cnt_m, key=lambda x: (x[0]*-1))
cnt = cnt_p + cnt_m
num = 0
for right,left in cnt:
    num -= right
    if(num < 0):
        print('No')
        exit()
    num += left

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

Submission status: Wrong Answer

Solution code:
import heapq
n = int(input())
s = [input() for _ in range(n)]
t = [None] * n
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)
    t[i] = (-m, k)
t.sort()
hq = []
d = 0
idx = 0
ans = ''
for i in range(n):
    while idx < n and d >= t[idx][0]:
        m, k = t[idx]
        heapq.heappush(hq, -k)
        idx += 1
    if hq:
        k = heapq.heappop(hq)
    else:
        print('No')
        break
    d -= k
else:
    if d == 0:
        print('Yes')
    else:
        print('No')

Submission status: Wrong Answer

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

N = int(readline())
S = [readline().strip() for i in range(N)]

D = []
L, R = [], []
for s in S:
    l, r = 0, 0
    for c in s:
        if c == ')':
            if l > 0:
                l -= 1
            else:
                r += 1
        else:
            l += 1
    if l == 0 and r == 0:
        pass
    elif l == 0:
        R.append(r)
    elif r == 0:
        L.append(l)
    else:
        D.append((l, r))

if len(L) == 0 or len(R) == 0:
    print('No')
    exit(0)

L = sum(L)
R = sum(R)

for i, (l,r) in enumerate(D):
    L -= r
    if L < 0:
        print('No')
        exit(0)
    L += l

if L == R:
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
N = int(input())
def I():
    s = input()
    mi = 0
    su = 0
    t = 0
    for a in s:
        if a == "(":
            t += 1
        else:
            t -= 1
            mi = min(mi, t)
    return (mi, t)

X = [I() for _ in range(N)]
if sum([x[1] for x in X]):
    print("No")
    exit()

X = sorted(X, key = lambda x: -10**10 if x[0] == 0 else -10**9 + x[0] if x[1] > 0 else x[0] - x[1])
T = 0
for mi, t in X:
    if T + mi < 0:
        print("No")
        exit()
    T += t
print("Yes")

Submission status: Wrong Answer

Solution code:
n=int(input())
lipp = []
lipm = []
limm = []
allcnt = 0
for _ in range(n):
    s = input()
    cnt = 0
    mi = 0
    for x in s:
        if x == ')':
            cnt -= 1
            mi = min(mi,cnt)
        else:
            cnt += 1
    if mi == 0:
        lipp.append(cnt)
    elif cnt >= 0:
        lipm.append([mi,cnt])
    else:
        limm.append([mi,cnt])
    allcnt += cnt
if allcnt != 0:
    print('No')
    exit()

now = sum(lipp)
lipm.sort()
limm.sort()

for mi, cnt in lipm:
    if mi + now < 0:
        print('No')
        exit()
    now += cnt

for mi, cnt in limm:
    if now+mi < 0:
        print('No')
        exit()
    now += cnt
print("Yes")

Submission status: Wrong Answer

Solution code:
n = int(input())
left = []
mid = []
right = []
L = []
R = []

for i in range(n):
    s = input()
    l = 0
    r = 0
    for x in s:
        if x == '(':
            l += 1
        else:
            if l > 0:
                l -= 1
            else:
                r += 1
    if l > 0 and r == 0:
        left.append((l, r))
    elif l > 0 and r > 0:
        mid.append((r, l)) # a,b
    elif l == 0 and r > 0:
        right.append((l, r))
    L.append(l)
    R.append(r)

if sum(L) != sum(R):
    print('No')
    exit()

A = 0
B = 0
for x in left:
    A += x[0]
for x in right:
    B += x[1]

mid = sorted(mid)
l = A
r = 0
for a,b in mid:
    if l < a:
        print('No')
        exit()
    l -= a
    l += b

print('Yes')

Submission status: Wrong Answer

Solution code:
from collections import Counter, defaultdict, deque

(N,) = [int(x) for x in input().split()]
brackets = [input() for i in range(N)]

delta = []
minDelta = []
for s in brackets:
    balance = 0
    mn = 0
    for c in s:
        if c == "(":
            balance += 1
        else:
            balance -= 1
        mn = min(mn, balance)
    delta.append(balance)
    minDelta.append(mn)

if sum(delta) == 0:
    posIndices = [i for i in range(N) if delta[i] > 0]
    posIndices.sort(key=lambda i: minDelta[i])

    eqIndices = [i for i in range(N) if delta[i] == 0]

    negIndices = [i for i in range(N) if delta[i] < 0]
    negIndices.sort(key=lambda i: -minDelta[i])
    balance = 0
    for i in posIndices + eqIndices + negIndices:
        if balance + minDelta[i] < 0 or balance + delta[i] < 0:
            print("No")
            exit()
        balance += delta[i]
    assert balance == 0

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