Problem:


Score : 600 points

Problem Statement

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

An empty string;

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

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

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

Constraints

1 \leq N \leq 10^6

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

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

Input

Input is given from Standard Input in the following format:

N
S_1
:
S_N

Output

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

Sample Input 1

2
)
(()

Sample Output 1

Yes

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

Sample Input 2

2
)(
()

Sample Output 2

No

Sample Input 3

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

Sample Output 3

Yes

Sample Input 4

3
(((
)
)

Sample Output 4

No



Sample input:
2
)
(()


Sample output:
Yes

Submission status: Wrong Answer

Solution code:
n = int(input())

all_change_depth = 0
required_depth = []

change_posi_zero = []
change_nega = []

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

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

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

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

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

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

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

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

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

Submission status: Wrong Answer

Solution code:
N = int(input())
LR = [[0]*2 for i in range(N)]
for i in range(N):
    S = input()
    M = len(S)
    L = 0
    R = 0
    R0 = 0
    t = 0
    if S[0]==")":
        while t<M:
            if S[t]==")":
                R0+=1
                t+=1
            else:
                t+=1
                break
    while t<M:
        if S[t]=="(":
            t+=1
            L+=1
        else:
            t+=1
            R+=1
    if L>R:
        LR[i][0]=L-R
        LR[i][1]=R0
    if L<R:
        LR[i][0]=0
        LR[i][1]=R0+R-L
    if L==R:
        LR[i][0]=0
        LR[i][1]=R0

LP = 0
RP = 0
minLS = float('inf')
minRS = float('inf')
LS = 0
RS = 0
for i in range(N):
    L = LR[i][0]
    R = LR[i][1]
    if (L==0)and(R==0):
        continue
    elif L==0:
        RP += R
    elif R==0:
        LP += L
    else:
        LS += L
        RS += R
        if LS < minLS:
            minLS = LS
        if RS < minRS:
            minRS = RS

if (LP==RP)and(LS==0)and(RS==0):
    print("Yes")

else:
    if LS>RS:
        RS = LS-RS+minRS
        LS = minLS
    elif LS<RS:
        RS = minRS
        LS = RS-LS+minRS
    elif LS==RS:
        RS = min(minLS,minRS)
        LS = min(minLS,minRS)
    if (LS<=RP)and(RS<=LP):
        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):
    u=st[i][0]
    l=len(u)
    now,mi=0,0
    for j in range(l):
        if u[j]=="(":
            now+=1
        else:
            now-=1
        mi=min(mi,now)
    st[i].append(mi)
st.sort(reverse=True,key=lambda z:z[2])
now2=0
for i in range(n):
    if now2+st[i][2]<0:
        print("No")
        break
    now2+=st[i][1]
else:
    print("Yes")

Submission status: Wrong Answer

Solution code:
import sys
import heapq
hpush = heapq.heappush
hpop = heapq.heappop
input = sys.stdin.readline
N = int(input())
ls = [0] * N
rs = [0] * N
h = []
base = 10 ** 7
for x in range(N):
  S = list(input())[: -1]
  for i in range(len(S)):
    if S[i] == "(": rs[x] += 1
    if S[i] == ")":
      if rs[x]: rs[x] -= 1
      else: ls[x] += 1
  hpush(h, ls[x] * base - rs[x])

if sum(ls) != sum(rs):
  print("No")
  exit(0)
if sum(ls) == 0:
  print("Yes")
  exit(0)
l = 0
r = 0
for i in range(N):
  if ls[i] == 0 and (rs[i] > 0): l = 1
  if rs[i] == 0 and (ls[i] > 0): r = 1
if l & r == 0:
  print("No")
  exit(0)

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

Submission status: Wrong Answer

Solution code:
N = int(input())
rd, ld, bd = 0, 0, [0, 0]

for _ in range(N):
    S = input()
    l, r = 0, 0
    for s in S:
        if s == ')' and l > 0:
            l -= 1
        elif s == ')':
            r += 1
        else:
            l += 1
    
    if r == 0:
        rd += l
    elif l == 0:
        ld += r
    elif bd == [0, 0]:
        bd = [r, l]
    else:
        bd = min([bd[0] + max(0, r - bd[1]), max(0, bd[1] - r) + l], [r + max(0, bd[0] - l), max(0, l - bd[0]) + bd[1]], key = lambda x: x[0]+x[1])

if (rd == 0 or ld == 0) and bd != [0, 0]:
    print('No')
elif rd + bd[0] == ld + bd[1]:
    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):
    l = []
    r = []
    b = [[0, 0]]
    for s in S:
        stack = []
        for c in s:
            if c == '(':
                stack.append('(')
            else:
                if stack and stack[-1] == '(':
                    stack.pop()
                else:
                    stack.append(')')
        lc = stack.count('(')
        rc = stack.count(')')
        if lc != 0 and rc != 0:
            b.append([lc, rc])
        elif lc != 0:
            l.append(lc)
        elif rc != 0:
            r.append(rc)

    if sum(l) != sum(r):
        return 'No'

    b.sort(key=lambda x: x[0]-x[1])
    while len(b) > 1:
        x = b.pop()
        y = b.pop()
        if x[1] < y[0]:
            z = [x[0] + y[0]-x[1], y[1]]
        else:
            z = [x[0], x[1]-y[0] + y[1]]
        b.append(z)


    sl = sum(l)
    sr = sum(r)
    sl -= b[0][0]
    sr -= b[0][1]

    if sl != sr or sl < 0 or sr < 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:
class SegmentTree():
    def __init__(self, arr, func=min, ie=2**63):
        self.n = 2**(len(arr) - 1).bit_length()
        self.ie = ie
        self.func = func
        self.tree = [ie for _ in range(2 * self.n)]
        for i in range(len(arr)):
            self.tree[self.n + i - 1] = arr[i]
        for i in range(self.n - 1)[::-1]:
            self.tree[i] = func(self.tree[2 * i + 1], self.tree[2 * i + 2])

    def set(self, idx, x):
        idx += self.n - 1
        self.tree[idx] = x
        while idx:
            idx = (idx - 1) // 2
            self.tree[idx] = self.func(self.tree[2 * idx + 1], self.tree[2 * idx + 2])

    def query(self, lt, rt):
        if rt <= lt:
            return self.ie
        lt += self.n - 1
        rt += self.n - 2
        tmp_l = self.ie
        tmp_r = self.ie
        while rt - lt > 1:
            if lt & 1 == 0:
                tmp_l = self.func(tmp_l, self.tree[lt])
            if rt & 1 == 1:
                tmp_r = self.func(self.tree[rt], tmp_r)
                rt -= 1
            lt = lt // 2
            rt = (rt - 1) // 2
        if lt == rt:
            tmp_l = self.func(tmp_l, self.tree[lt])
        else:
            tmp_l = self.func(self.func(tmp_l, self.tree[lt]), self.tree[rt])
        return self.func(tmp_l, tmp_r)

import sys
input = sys.stdin.readline

from bisect import bisect_left, bisect_right

INF = 10**18

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

D = []
E = []

for i in range(N):
    kakko = 0
    minkakko = 0
    for j in range(len(S[i])):
        if S[i][j] == '(':
            kakko += 1
        else:
            kakko -= 1
        minkakko = min(kakko, minkakko)
    D.append((minkakko, kakko))
    E.append(minkakko)

D.sort()
E = []

for i in range(N):
    E.append(D[i][0])


F = []
for i in range(N):
    F.append((D[i][1], D[i][0], i))

s = 0

st = SegmentTree(F, max, (-INF, -INF, 0))

for i in range(N):
    x = bisect_left(E, -s)

    if x >= N:

        print('No')
        break
    v = st.query(x, N + 1)
    if v[0] == -INF:
        print('No')

        break
    s += v[0]
    st.set(v[2], (-INF, v[1], v[2]))
    if s < 0:
        print('No')
        break
else:
    if s == 0:
        print('Yes')
    else:
        print('No')

Submission status: Wrong Answer

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


def main():
    N = int(input())

    nl = 0
    nr = 0

    buff_l = 0
    buff_r = 0

    for _ in range(N):
        S = input()
        for s in S:
            if s == '(':
                buff_l += 1
            elif s == ')':
                if buff_l > 0:
                    buff_l -= 1
                else:
                    buff_r += 1
        
        if buff_l == buff_r == 0:
            continue

        if buff_l > buff_r:
            nl += max(buff_l - nr, 0)
            nr = max(nr - buff_l, 0)
        elif buff_r > buff_l:
            nr += max(buff_r - nl, 0)
            nl = max(nl - buff_r, 0)
        else:
            if nr > nl:  # left
                nr = max(nr - buff_l, 0) + buff_r
                nl += max(buff_l - nr, 0)
            else:
                nr += max(buff_r - nl, 0)
                nl = max(nl - buff_r, 0) + buff_l

        buff_l = 0
        buff_r = 0

    if nr == nl == 0:
        print('Yes')
    else:
        print('No')


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop
import sys
input = sys.stdin.readline

N = int(input())
pos = []
zero = []
neg = []
for _ in range(N):
    S = input().rstrip()
    m = s = 0
    for c in S:
        if c == '(':
            s += 1
        else:
            s -= 1
            m = min(m, s)
    if s > 0:
        heappush(pos, (-m, s)) # take larger mins first
    elif s == 0:
        heappush(zero, (m, s))
    else:
        heappush(neg, (m, -s)) # take smaller mins first
num = 0
while pos:
    m, s = heappop(pos)
    if num - m < 0:
        print('No')
        exit()
    num += s
while zero:
    m, s = heappop(zero)
    if num + m < 0:
        print('No')
        exit()
while neg:
    m, s = heappop(neg)
    if num + m < 0:
        print('No')
        exit()
    num -= s
if num == 0:
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

Solution code:
import sys
import heapq
hpush = heapq.heappush
hpop = heapq.heappop
input = sys.stdin.readline
N = int(input())
ls = [0] * N
rs = [0] * N
h = []
base = 10 ** 7
for x in range(N):
  S = list(input())[: -1]
  for i in range(len(S)):
    if S[i] == "(": rs[x] += 1
    if S[i] == ")":
      if rs[x]: rs[x] -= 1
      else: ls[x] += 1
  hpush(h, ls[x] * base - rs[x])
"""
if sum(ls) != sum(rs):
  print("No")
  exit(0)"""
if sum(ls) == 0:
  print("Yes")
  exit(0)
l = 0
r = 0
for i in range(N):
  if ls[i] == 0 and (rs[i] > 0): l = 1
  if rs[i] == 0 and (ls[i] > 0): r = 1
if l & r == 0:
  print("No")
  exit(0)

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

Submission status: Wrong Answer

Solution code:
N = int(input())
S_info1 = []
S_info2 = []

tot = 0

for _ in range(N):
    s = input()
    score = 0
    maxv = 0
    minv = 0
    for c in s:
        if c == "(":
            score += 1
        else:
            score -= 1
        maxv = max(maxv, score)
        minv = min(minv, score)
    tot += score
    if score > 0:
        S_info1.append([s, score, maxv, minv])
    else:
        S_info2.append([s, score, maxv, minv])

if tot != 0:
    print("No")
else:
    S_info1.sort(key = lambda x:(-x[1], -x[3]))
    #print(S_info1)
    tot = 0
    flag = True
    for i in range(len(S_info1)):
        s, score, maxv, minv = S_info1[i]
        if tot < -minv:
            flag = False
        tot += score
    if not flag:
        print("No")
    else:
        S_info = S_info1 + S_info2
        flag = True
        tot = 0
        Maxv = 0
        Minv = 0
        Maxscore = 0
        for i in range(N):
            s, score, maxv, minv = S_info[i]
            tot += score
            Maxv = max(Maxv, maxv)
            Minv = min(Minv, minv)
            if score > 0:
                Maxscore += score
        if tot == 0 and Maxscore >= -Minv:
            print("Yes")
        else:
            print("No")

Submission status: Wrong Answer

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

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

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

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

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

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

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

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

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

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

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

Submission status: Wrong Answer

Solution code:
# import random
# import itertools

def checker(s):
    conflict = False
    left = 0
    for i in range(len(s)):
        if s[i] == "(":
            left += 1
        else:
            if left == 0:
                conflict = True
                break
            else:
                left -= 1
    if not conflict and left == 0:
        return True
    else:
        return False

# def gen():
#     l = random.randint(1,3)
#     arr = ["(",")"]
#     hoge = random.choices(arr,k=l)
#     return "".join(hoge)

n = int(input())
ronly = []
lonly = []
buf = []
for i in range(n):
    tp = input()
    if all([t==")" for t in tp ]):
        ronly.append(tp)
    elif all([t=="(" for t in tp ]):
        lonly.append(tp)
    else:
        buf.append(tp)

buf.sort()
at = lonly+buf+ronly
# print(buf)
# print(checker("".join(buf)))
if checker("".join(at)):
    print("Yes")
else:
    print("No")



# lonly = []
# ronly = []
# fuga = []
# for i in range(6):
#     tp = gen()
#     if all([t==")" for t in tp ]):
#         ronly.append(tp)
#     elif all([t=="(" for t in tp ]):
#         lonly.append(tp)
#     else:
#         fuga.append(tp)
#
# fuga.sort()
#
# at = lonly+fuga+ronly
# for o in itertools.permutations(fuga):
#     if checker("".join(o)):
#         print(o)
#         print("Yes")
# print(fuga)
# print(at)
# print(checker("".join(at)))

Submission status: Wrong Answer

Solution code:
import sys
from operator import itemgetter

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

    return  0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
N=int(input())

slist=[]
for _ in range(N):
  s=input()
  while True:
    s_new=s.replace("()","")
    #print(s,s_new)
    if s_new==s:
      s=s_new
      break
    else:
      s=s_new
  slist.append(s)
#print(slist)

rl_list=[]
for i in range(N):
  s=slist[i]
  l=s.count("(")
  r=s.count(")")
  if l>0 or r>0:
    rl_list.append((l,r))
#print(rl_list)
  
lsum=rsum=0
lmin=rmin=float("inf")
for r,l in rl_list:
  rsum+=r
  lsum+=l
  lmin=min(lmin,l)
  rmin=min(rmin,r)
  
if rsum!=lsum:
  print("No")
elif rmin>0 or lmin>0:
  print("No")
else:
  print("Yes")

Submission status: Wrong Answer

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))

from collections import defaultdict, deque
from sys import exit
import math
import copy
from bisect import bisect_left

import sys
# sys.setrecursionlimit(1000000)
INF = 10 ** 17
MOD = 998244353

def main():
    n = getN()
    al, ar = 0, 0
    for i in range(n):
        s = input().strip()
        q = deque()
        l, r = 0, 0
        for c in s:
            if c == "(":
                r += 1
            else:
                if r == 0:
                    l += 1
                else:
                    r -= 1

        a,b,c,d = al, ar, l, r
        if c > b:
            nl = a + (c - b)
            nr = d
        else:
            nl = a
            nr = d + (b - c)
        nlen = nl + nr

        if a > d:
            nnl = c + (a - d)
            nnr = b
        else:
            nnl = c
            nnr = b + (d - a)
        nnlen = nnl + nnr

        if nlen < nnlen:
            al , ar = nl, nr
        else:
            al, ar = nnl, nnr

    if al == 0 and ar == 0:
        print("Yes")
    else:
        print("No")

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from heapq import *
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=[]
    wait=[]
    for s in ss:
        mn=0
        now=0
        for c in s:
            if c=="(":now+=1
            else:now-=1
            if now<mn:mn=now
        heappush(wait,(-mn,now))
    cnt=0
    can=[]
    while wait or can:
        while wait and wait[0][0]<=cnt:
            mn,s=heappop(wait)
            heappush(can,(-s,mn))
        if not can:
            print("No")
            exit()
        s,mn=heappop(can)
        s=-s
        #print(cnt,mn,s)
        if cnt-mn<0:
            print("No")
            exit()
        cnt+=s
    if cnt==0:print("Yes")
    else:print("No")

main()

Submission status: Wrong Answer

Solution code:
n,*s=open(0)
n=int(n)
f=g=h=a=b=m=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
    else:m+=1
    a+=x
    b+=y
if (h>1 or f and g) and a==b and not (m and (not f or not g)):
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

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

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

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

N = Int()
Sum = 0

A = []
Min = []
Now = []

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

#print(A)
# zipで二つの配列を統合
c = zip(Min, Now)
# 統合していた配列をもとに戻す
Min, Now = zip(*sorted(c))
    
if Sum!=0:
    print('No')
    sys.exit()

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

import bisect

count = 0
now = 0

#print(Min)
#print(Now)

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

print('Yes')

Submission status: Wrong Answer

Solution code:
from itertools import combinations

import numpy as np


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

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

    s_list_is_0 = s_list == 0


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

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


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

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


if __name__ == '__main__':
    run()

Submission status: Wrong Answer

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

plus.sort(key = lambda x:mins[x])
minus.sort(key = lambda x:mins[x])

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

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

Submission status: Wrong Answer

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

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

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

if L != 0 or R != 0:
    if bigl <= L / 2 and bigr <= R / 2:
        print('Yes' if tl and tr and L == R else 'No')
    else:
        print('No')
else:
    print('Yes')

Submission status: Wrong Answer

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

for i in range(N):
    S = input()

    memo = 0
    memo2 = -10**10
    for j in range(len(S)):
        if S[j] == "(":
            memo -= 1
        else:
            memo += 1
        memo2 = max(memo,memo2)
    
    li.append([memo,memo2,S])

li = sorted(li,key=lambda x:x[1])

# print(li)

cnt = 0
for i in range(len(li)):
    
    if cnt+li[i][1] > 0:
        print("No")
        break
    cnt += li[i][0]
else:
    print("Yes")

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
l=[]
ln=[]
for i in range(n):
    s=input().rstrip()
    l.append(s)
    m=10**10
    temp=0
    for j in s:
        if j=='(':
            temp+=1
        else:
            temp-=1
        m=min(m,temp)
    ln.append((m,temp))
ln.sort(reverse=True)
s=0
for i in ln:
    if s+i[0]>=0:
        s+=i[1]
    else:
        print('No')
        sys.exit()
if s==0:
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

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

def count(s):
    n = len(s)
    n1 = 0
    n2 = 0
    for i in range(n):
        if s[i]=='(':
            n2 += 1
        else:
            if n2 > 0:
                n2 -= 1
            else:
                n1 += 1
    return n1,n2

l = []
for i in range(N):
    n1,n2 = count(S[i])
    if n1+n2!=0:
        l.append([n1,n2])

l.sort(key=lambda x:x[1]-x[0])
l.sort(key=lambda x:x[0])

N = len(l)
N0 = 2**(N-1).bit_length()
INF = 2**31-1
data = [[INF,INF]]*(4*N0) #長さが足りないことがある. 3*N0にすればいい?

# k番目の要素をxに更新
def update(k, x):
    k += N0-1
    data[k] = x
    while k >= 0:
        k = (k - 1) // 2
        data[k] = min(data[2*k+1], data[2*k+2])

# [l,r)の最小値
def query(l, r):
    L = l + N0; R = r + N0
    s = [INF,INF]
    while L < R:
        if R & 1:
            R -= 1
            s = min(s, data[R-1])

        if L & 1:
            s = min(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s

d = []
for i in range(N):    
    a,b = l[i]
    d.append(a)
    update(i, [a,a-b])

ans = True
n = 0
for i in range(N):
    i = bisect(d,n)-1
    c,i = query(0,i+1)
    if i == INF:
        ans = False
        break
    update(i,[INF,i])
    n -= c
if n!=0:
    ans = False
if ans:
    ans = 'Yes'
else:
    ans = 'No'
print(ans)

Submission status: Wrong Answer

Solution code:
import heapq

N=int(input())
S = [input() for _ in range(N)]
p1 = 0
p2 = []
p3 = []
for i,s in enumerate(S):
    depth = 0
    max_depth = 0
    min_depth = 0
    for chr in s:
        if chr=='(':
            depth += 1
            if depth > max_depth:
                max_depth = depth
        else:
            depth -= 1
            if depth < min_depth:
                min_depth = depth
    if depth >= 0 and min_depth >= 0:
        p1 += depth
    elif depth >= 0 and min_depth < 0:
        p2.append((min_depth,depth))
    else:
        p3.append((min_depth,depth))
pp2 = sorted(p2,reverse=True)
pp3 = sorted(p3)
# print(p1)
# print(p2)
# print(p3)

depth = p1
for p in pp2:
    if depth+p[0] < 0:
        print('No')
        exit()
    depth += p[1]
for p in pp3:
    if depth+p[0] < 0:
        print('No')
        exit()
    depth += p[1]
if depth != 0:
    print('No')
else:
    print('Yes')

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

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

n=n_in()

base=[]

for _ in range(n):
    s = s_in()

    c = s[0]
    cnt = 1
    ar = []
    for t in range(1,len(s)):
        if s[t-1] == s[t]:
            cnt += 1
        else:
            ar.append((c,cnt))
            c = s[t]
            cnt = 1
    ar.append((c,cnt))

    start = 0
    if ar[0][0] == ")":
        start = 1

    r = 0 # ( の数
    sgn = 1
    for c,cnt in ar[start:]:
        r += sgn*cnt
        sgn *= -1


    res = ()
    if ar[0][0] == ")":
        if r >= 0:
            res = (ar[0][1], r)
        else:
            res = (ar[0][1]-r,0)
    else:
        if r >= 0:
            res = (0, r)
        else:
            res = (r, 0)

    base.append(res)

i_cnt = 0
j_cnt = 0

base2 = []

for i,j in base:
    i_cnt += i
    j_cnt += j

    if j > 0:
        base2.append((i,-(j-i),j))

if i_cnt != j_cnt:
    print("No")
    exit()

base2.sort()

current = 0

for i,p,j in filter(lambda x: x[1] <= 0 ,base2):
    if current < i:
        print("No")
        exit()
    current -= i
    current += j

for i,p,j in filter(lambda x: x[1] > 0 ,base2):
    if current < i:
        print("No")
        exit()
    current -= i
    current += j
    
print("Yes")

Submission status: Wrong Answer

Solution code:
print("No")