Problem:


Score : 600 points

Problem Statement

A bracket sequence is a string that is one of the following:

An empty string;

The concatenation of (, A, and ) in this order, for some bracket sequence A ;

The concatenation of A and B in this order, for some non-empty bracket sequences A and B /

Given are N strings S_i. Can a bracket sequence be formed by concatenating all the N strings in some order?

Constraints

1 \leq N \leq 10^6

The total length of the strings S_i is at most 10^6.

S_i is a non-empty string consisting of ( and ).

Input

Input is given from Standard Input in the following format:

N
S_1
:
S_N

Output

If a bracket sequence can be formed by concatenating all the N strings in some order, print Yes; otherwise, print No.

Sample Input 1

2
)
(()

Sample Output 1

Yes

Concatenating (() and ) in this order forms a bracket sequence.

Sample Input 2

2
)(
()

Sample Output 2

No

Sample Input 3

4
((()))
((((((
))))))
()()()

Sample Output 3

Yes

Sample Input 4

3
(((
)
)

Sample Output 4

No



Sample input:
2
)
(()


Sample output:
Yes

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    inf=10**9
    n=II()
    ss=[SI() for _ in range(n)]
    ms=[]
    for s in ss:
        mn=0
        now=0
        for c in s:
            if c=="(":now+=1
            else:now-=1
            if now<mn:mn=now
        ms.append((mn,now))
    ms.sort(reverse=True)
    #print(ms)
    cnt=0
    for mn,s in ms:
        if cnt+mn<0:
            print("No")
            exit()
        cnt+=s
    if cnt==0:print("Yes")
    else:print("No")

main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
ls = [0] * N
rs = [0] * N
empty = 0
for x in range(N):
  S = list(input())[: -1]
  if len(S) == 0: empty += 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
if sum(ls) != sum(rs):
  print("No")
  exit(0)
if sum(ls) == 0:
  if empty == 0:
    print("Yes")
    exit(0)
  else:
    print("No")
    exit(0)
l = 0
r = 0
for i in range(N):
  if ls[i] == 0 and (rs[i] > 0): l = 1
  if rs[i] == 0 and (ls[i] > 0): r = 1
if l & r:
  print("Yes")
else: print("No")

Submission status: Wrong Answer

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

MAX = 10**6
N = int(input())
Ss = [input().rstrip() for _ in range(N)]

def calc(S):
    stack = []
    for s in S:
        if s == ")" and stack and stack[-1] == "(":
            stack.pop()
        else:
            stack.append(s)
    le = 0
    ri = 0
    for s in stack:
        if s == ")":
            le += 1
        else:
            ri += 1
    return le, ri

Ps = [[] for _ in range(MAX+1)]
Qs = [[] for _ in range(MAX+1)]
for S in Ss:
    le, ri = calc(S)
    if ri >= le:
        Ps[le].append(ri-le)
    else:
        Qs[ri].append(le-ri)

T = 0
ok = True
for le, P in enumerate(Ps):
    if T < le:
        ok = False
        break
    else:
        T -= len(P)*le
        T += sum(P)

U = 0
for ri, Q in enumerate(Qs):
    if U < ri:
        ok = False
        break
    else:
        U -= len(Q)*ri
        U += sum(Q)

if T != U:
    ok = False
print("Yes" if ok else "No")

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
        counts.append((closing, opening))
        total_opening += opening
        total_closing += closing
    LOG.debug((counts))
    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:
#!/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([o-c,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[1]>cur:
            print("No")
            exit(0)
        cur+=a[0]
    
    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:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline

n = int(input())
increasing = []
decreasing = []
for _ in range(n):
    s = input().rstrip()
    minima = 0
    fin = 0
    for ch in s:
        if ch == ")":
            fin -= 1
            if fin < minima:
                minima = fin
        else:
            fin += 1
    if fin >= 0:
        increasing.append((minima, fin))
    else:
        decreasing.append((minima, -fin))

increasing.sort(reverse=True)
decreasing.sort()

current = 0
for minima, diff in increasing:
    if current + minima < 0:
        print("No")
        exit()
    current += diff
for minima, diff in decreasing:
    diff = -diff
    if current + minima < 0:
        print("No")
        exit()
    current += diff
if current != 0:
    print("No")
else:
    print("Yes")

Submission status: Wrong Answer

Solution code:
N = int(input())
outerleft = 0
outerright = 0
for x in range(N):
    S = input()
    point = 0
    for i in range(len(S)):
        if S[i] == ")" :
            if point <= 0:
                outerright += 1
            else:
                point -= 1
        else:
            point += 1
    if point > 0:
        outerleft += point
if outerright == outerleft:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

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

A = [(0,0)]*N
B = [(0,0)]*N
for i,T in enumerate(S):
    m = 0
    tot = 0
    for t in T:
        if t==")":
            tot -= 1
        else:
            tot += 1
        m = min(m,tot)
    if tot >= 0:
        A[i] = (m,tot)
    else:
        B[i] = (m,tot)

A.sort(reverse=True)
B.sort()

tot = 0
ans = True
for m,t in A:
    if tot + m < 0:
        ans = False
        break
    tot += t
for m,t in B:
    if tot < m:
        ans = False
        break
    tot += t
if tot != 0:
    ans = False

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

Submission status: Wrong Answer

Solution code:

import bisect
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))



n = int(input())
minsum = [None] * n # (min, sum)
for i in range(n):
    tmp = list(map(int, " ".join(input()).replace("(", "1").replace(")", "-1").split()))
    c = 0
    m = 0
    for item in tmp:
        c += item
        m = min(c, m)
    minsum[i] = (m, sum(tmp))
minsum.sort()

if sum(item[1] for item in minsum)!=0:
    print("No")
else:
    c = 0
    for i in range(n):
        ind = bisect.bisect_right(minsum, (c, 10**9))
        m, s = minsum.pop(ind-1)
        if m+c<0:
            print("No")
            break
        c += s
    else:
        print("Yes")

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
    if x==0:f=1
    elif y==0:g=1
    a+=x
    b+=y
if a==b:
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

Solution code:
n = int(input())
bra = []
for _ in range(n):
  s = input()
  mini = 0
  now = 0
  l = len(s)
  for i in range(l):
    if s[i] == '(':
      now += 1
    else:
      now -= 1
      mini = min(mini,now)
  bra.append([-mini,now])
check = 0
for x in bra:
  #print(x)
  check += x[1]
if check != 0:
  print('No')
  exit()
bra.sort()
now = 0
here = -1
#print(bra)
import heapq
pool = []
for i in range(n):
  while here != n-1:
    if bra[here+1][0] <= now:
      here += 1
      heapq.heappush(pool,-bra[here][1])
    else:
      break
  #print(i,'#',pool)
  if not pool:
    print('No')
    exit()
  else:
    now -= heapq.heappop(pool)
print('Yes')

Submission status: Wrong Answer

Solution code:
n=int(input())
a=[]
for i in range(n):
    z=input()
    b,c,d=z.count('(')-z.count(')'),[],0
    for j in range(len(z)):
        d+=1 if z[j]=='(' else -1
        c.append(d)
    a.append([b,min(min(c),0)])
e=0
for i in range(n):
    e+=a[i][0]
if e!=0:
    print('No')
    exit()
e=0
a1,a2=[],[]
for i in range(n):
    if a[i][0]>=0 and a[i][1]==0:
        e+=a[i][0]
    elif a[i][0]>0:
        a1.append(a[i])
    else:
        a2.append(a[i])
a1=sorted(a1,key=lambda x:x[1],reverse=1)
a2=sorted(a2,key=lambda x:x[1],reverse=1)
for i in range(len(a1)):
    if e+a1[i][1]<0:
        print('No')
        exit()
    e+=a1[i][0]
for i in range(len(a2)):
    if e+a2[i][1]<0:
        print('No')
        exit()
    e+=a2[i][0]
print('Yes')

Submission status: Wrong Answer

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

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

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

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

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

P.sort()
L.sort(reverse=True)
P = [s for _, s in P]
L = [s for _, _, s in L]

ans = ''.join(H + P + L)
l = ans.count('(')
r = ans.count(')')

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

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [[] for i in range(1000010)]
b = [[] for i in range(1000010)]

for i in range(n):
    s = input()
    x = 0
    y = 0
    for c in s:
        if c == '(':
            y += 1
        else:
            if y >= 1:
                y -= 1
            else:
                x += 1
    if x <= y:
        a[x].append(y)
    else:
        b[y].append(x)


resx = 0
x = 0
while x <= 1000000 and x <= resx:
    for y in a[x]: resx += y-x
    x += 1

resy = 0
y = 0
while y <= 1000000 and y <= resy:
    for x in b[y]: resy += x-y
    y += 1

flag = True
for i in range(x, 1000010):
    if len(a[i]) > 0:
        flag = False
for i in range(y, 1000010):
    if len(b[i]) > 0:
        flag = False

if not flag:
    print("No")
else:
    print("Yes" if resx == resy else "No")

Submission status: Wrong Answer

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

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

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

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

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

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

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

INF = 999999999999999999999999
MOD = 10**9+7

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

left = 0
right = 0

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

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
                break
    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もだめなやつをL-Rが多い順に並べる
ngs = []
for i in range(n):
    if not l_ok[i] and not r_ok[i]:
        ngs.append((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:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10 ** 7)

    N = int(input())

    g = tuple(set() for _ in range(10 ** 6 + 1))
    i = 0
    for _ in range(N):
        s = input().rstrip()

        open_ = 0
        close_ = 0
        for c in s:
            if c == '(':
                open_ += 1
            else:
                if open_:
                    open_ -= 1
                else:
                    close_ += 1

        if close_ or open_:
            g[close_].add((open_, i))
            i += 1

    used = [False] * len(g)

    def dfs(close_=0, cnt=0):
        if cnt == i:
            return True
        for open_, u in g[close_]:
            if used[u]: continue
            used[u] = True
            if dfs(open_, cnt + 1):
                return True
            used[u] = False
        return False

    cond = dfs()
    print('Yes' if cond else 'No')


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
from 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)]
lr=[]
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)
    lr.append([l,r])
#lr.sort(key=lambda x:x[0]*x[1],reverse=True)
idleR=10**7
L,R=lr[0]
stack=[[L,R]]
for n in range(1,N):
    #print(stack)
    L,R=lr[n]
    visited=set()
    nstack=[]
    while stack:
        l,r=stack.pop()
        for xl,xr in [[l+L,r+R],[l,r+R-l],[l+L-R,r-l],[l-R,r-L]]:

            X=xl+idleR*xr
            if not X in visited:
                visited.add(X)
                nstack.append([xl,xr])


    stack=nstack
#print(stack)
if [0,0] in stack:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
import sys
import heapq as hq

readline = sys.stdin.readline
readlines = sys.stdin.readlines
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')

n = ni()
l = [ns() for _ in range(n)]
gu = list()
gd = list()
c = 0
for i in range(n):
    s = l[i]
    t = 0
    m = 0
    for x in s:
        if x == '(':
            t += 1
        else:
            t -= 1
            if m > t:
                m = t
    c += t
    if t > 0:
        gu.append((m, t))
    else:
        gd.append((m, -t))
if c != 0:
    print('No')
    exit(0)
gu.sort(reverse=True)
gd.sort()
cur = 0
q = list()
for m, t in gu:
    if cur + m < 0:
        print('No')
        exit(0)
    cur += t
for m, t in gd:
    if cur + m < 0:
        print('No')
        exit(0)
    cur -= t

print('Yes')

Submission status: Wrong Answer

Solution code:
def main():

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

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

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
from collections import deque
from fractions import gcd
from functools import lru_cache


#############
# Constants #
#############

MOD = 998244353
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#############
# Main Code #
#############

N = inputI()
S = inputSLs(N)


s = 0
is_start = 0
is_end = 0
is_both = 0
for item in S:
  if item[0] == "(" and item[-1] == ")":
    is_both += 1
  elif item[0] == "(":
    is_start += 1
  elif item[-1] == ")":
    is_end += 1
  for i in item:
    if i == "(":
      s += 1
    else:
      s -= 1

if s == 0:
  if is_start>0 and is_end >0:
    print("Yes")
    exit()
  elif is_start == 0 and is_end >0:
    if is_both >= 1:
      print("Yes")
      exit()
  elif is_start > 0 and is_end ==0:
    if is_both >= 1:
      print("Yes")
      exit()
  else:
    if is_both >= 2:
      print("Yes")
      exit()    
print("No")

Submission status: Wrong Answer

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

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

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

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

P.sort(key = lambda x:x[1])
for x, y in P:
  if y > cnt:
    print("No")
    exit()
  cnt += x

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

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

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

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

Submission status: Wrong Answer

Solution code:
n = int(input())
s = [""]*n
dp = [[] for i in range(n+1)]
plus = []
minas = []
kosu = 0
for i in range(n):
    s[i] = input()
    dp[i] = [0]*(len(s[i]) + 2)
    check = True
    kosu += len(s[i])
    for j in range(len(s[i])):
        p = 0
        if s[i][j] == '(':p = 1
        else:p = -1
        dp[i][j+1] = dp[i][j] + p
        if dp[i][j+1] < 0:
            check = False
    if check:plus.append(i)
    else:minas.append(i)

ruiseki = [0]*(10**6+5)
idx = 0
for i in plus + minas:
    for j in range(len(s[i])):
        p = 0
        if s[i][j] == '(':p = 1
        else:p = -1
        ruiseki[idx+1] = ruiseki[idx] + p
        idx += 1
check = True
for i in range(kosu):
    if ruiseki[i+1] < 0:
        check = False
        break
if check == False or ruiseki[kosu] != 0:
    print("No")
else:
    print("Yes")

Submission status: Wrong Answer

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

MAX = 10**6
N = int(input())
Ss = [input().rstrip() for _ in range(N)]

def calc(S):
    stack = []
    for s in S:
        if s == ")" and stack and stack[-1] == "(":
            stack.pop()
        else:
            stack.append(s)
    le = 0
    ri = 0
    for s in stack:
        if s == ")":
            le += 1
        else:
            ri += 1
    return le, ri

Ps = [[] for _ in range(MAX+1)]
Qs = [[] for _ in range(MAX+1)]
for S in Ss:
    le, ri = calc(S)
    if ri >= le:
        Ps[le].append(ri-le)
    else:
        Qs[ri].append(le-ri)

T = 0
ok = True
for le, P in enumerate(Ps):
    if T < len(P)*le:
        ok = False
        break
    else:
        T -= len(P)*le
        T += sum(P)

U = 0
for ri, Q in enumerate(Qs):
    if U < len(Q)*ri:
        ok = False
        break
    else:
        U -= len(Q)*ri
        U += sum(Q)

if T != U:
    ok = False
print("Yes" if ok else "No")

Submission status: Wrong Answer

Solution code:
N = int(input())
A = ""
sum = 0
for i in range(N):
    S = input()
    m = 0
    t = 0
    for s in S:
        if s == "(":
            t += 1
        else:
            t -= 1
        if m >= t:
            m = t
    if m == 0:
        A = S+A
    else:
        A = A+S
sum = 0
state = "Yes"
for s in A:
    if s == "(":
        sum += 1
    else:
        sum -= 1
    if sum < 0:
        state = "No"
        break
if sum != 0:
    state = "No"
print(state)

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 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:
def count(s):
    ret = 0
    max_down = 0
    for c in s:
        if c=="(": ret += 1
        else: ret -= 1
        max_down = min(max_down,ret)
    return max_down, ret

n = int(input())
s_count = []
for i in range(n):
    si = input()
    s_count.append(count(si))

s_count.sort(reverse=True)

ans = "No"
count_sum = 0
for down, num in s_count:
    if count_sum < -down: break
    count_sum += num
else:
    if count_sum == 0: ans = "Yes"

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
input = lambda:sys.stdin.readline().rstrip()
from heapq import heappop, heappush
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)
    S.sort()

    if sum(S[i][1] for i in range(n)) != 0:
        print("No")
        return

    now = 0
    while S:
        min_balance, balance = S.pop()
        if now + min_balance < 0:
            print("No")
            return
        now += balance

    print("Yes")
resolve()