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:
def do(s):
    l, r = 0, 0
    for i in range(len(s)):
        if s[i] == "(":
            r += 1
        elif s[i] == ")":
            if r > 0:
                r -= 1
            else:
                l += 1
    #print(s, l, r)
    return (l,r)

n = int(input())
dat = []

maxr = -1
maxrind = 0
maxrtotal = -1

curl, curr = 0, 0
for i in range(n):
    s = input()
    l ,r = do(s)
    if l != 0 or r != 0:
        dat.append( [l,r] )
        continue

#print(curr, curl)
dat.sort(key=lambda x: -(x[0] + x[1]))
#print(dat)

for i in range(len(dat)):
    newl , newr = dat[i]
    #print("curl", curl, " curr", curr, " newl", newl, " newr", newr)
    caneraseL = min(curl, newr)
    caneraseR = min(curr, newl)
    if caneraseL == caneraseR:
        if curl > curr: # Lを消したい = newは左につける
            # 左につける ver00
            if curl >  newr: # いまのLの方が多いなら
                curl, curr = newl + (curl - newr), curr
            else:
                curl, curr = newl, curr + (newr - curl)
        else: # Rを消す = newは右につける
            # 右につける ver00
            if curr >  newl: # いまのRの方が多いなら
                curl, curr = curl, newr + (curr - newl)
            else:
                curl, curr = curl + (newl - curr), newr
    elif caneraseR > caneraseL:
        # 右につける ver00
        if curr > newl:  # いまのRの方が多いなら
            curl, curr = curl, newr + (curr - newl)
        else:
            curl, curr = curl + (newl - curr), newr
    else: # caneraseR < caneraseL
        # 左につける ver00
        if curl > newr:  # いまのLの方が多いなら
            curl, curr = newl + (curl - newr), curr
        else:
            curl, curr = newl, curr + (newr - curl)
#print(curl,curr)
print("Yes" if curl == curr == 0 else "No")

Submission status: Wrong Answer

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

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    a = [input() for i in range(n)]
    s = []
    for i in range(n):
        p = 0
        m = 0
        for j in a[i]:
            if j == "(":
                p += 1
            else:
                p -= 1
            if p < m:
                m = p
        s.append((m,p))
    s.sort(key=lambda x:(-x[0],-x[1]))
    q = []
    k = 0
    i = 0
    while q or (i < n):
        while i < n and s[i][0]+k >= 0:
            heappush(q,-s[i][1])
            i += 1
        if not q:
            print("No")
            return
        k -= heappop(q)
    if k > 0 or i < n:
        print("No")
    else:
        print("Yes")
    return

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

Submission status: Wrong Answer

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

n = int(input())
s = [input().rstrip() for _ in range(n)]
l = [0, 0]
r = [0, 0]
m = [0, 0]
for i in range(n):
    s_ = list(s[i])
    left = 0
    right = 0
    for j in s_:
        if j == ")":
            if left >= 1:
                left -= 1
            else:
                right += 1
        else:
            left += 1
    if left > right:
        l[0] += left
        l[1] += right
    elif right > left:
        r[0] += left
        r[1] += right
    else:
        m[0] += left
        m[1] += right
if l[0] - l[1] - m[1] == r[1] - r[0] - m[0] and l[0] - l[1] - m[1] >= 0:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
import math
import sys
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from functools import lru_cache, reduce
from heapq import heapify, heappop, heappush
from itertools import chain, combinations, permutations, product
from typing import List, Dict

# import numpy as np

sys.setrecursionlimit(10**6 + 1)
# input = sys.stdin.readline
write = sys.stdout.write


def read_item(cls=int):
    return cls(input())


def read_n_item(cls=int) -> list:
    return [cls(s) for s in input().split()]


def list2d(row, col, init_val=0) -> List[list]:
    return [[init_val] * col for _ in range(row)]


# MOD = 10**9 + 7
MOD = 998244353


def transfer(s):
    left = 0
    for ch in s:
        if left < 0 and ch == '(':
            break
        if ch == '(':
            left += 1
        else:
            left -= 1
    right = 0
    for ch in s[::-1]:
        if right < 0 and ch == ')':
            break
        if ch == ')':
            right += 1
        else:
            right -= 1
    return (-min(left, 0), -min(right, 0))


N = read_item()
graph = defaultdict(list)
pos = defaultdict(int)

for _ in range(N):
    u, v = transfer(input())
    # print(u, v)
    graph[u].append(v)


def dfs(cur, lenth):
    if lenth == N and cur == 0:
        return True
    if pos[cur] < len(graph[cur]):
        pos[cur] += 1
        return dfs(graph[cur][pos[cur]-1], lenth+1)
    return False


if dfs(0, 1):
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

Solution code:
def check(s):
    p = 0
    stock_q = 0
    for chr in s:
        if chr == '(':
            stock_q += 1
        else:
            if stock_q:
                stock_q -= 1
            else:
                p += 1

    q = 0
    stock_p = 0
    for chr in s[::-1]:
        if chr == ')':
            stock_p += 1
        else:
            if stock_p:
                stock_p -= 1
            else:
                q += 1
    return p, q  # p = 左側に ) が残っている, q = 右側に ( が残っている


n = int(input())
pq_list = []
sum_p = 0
sum_q = 0

for _ in range(n):
    s = input()
    p, q = check(s)
    sum_p += p
    sum_q += q
    pq_list.append((p, q))

if sum_p != sum_q:
    print('No')
    exit()

pq_list.sort()

count = 0
for p, q in pq_list:
    count -= p
    if count < 0:
        print('No')
        exit()
    count += q

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

Submission status: Wrong Answer

Solution code:
n = int(input())
s = []
lst_1_any_hihu = []
lst_1_hihu_hu = []
lst_1_hu_hu = []
lst_0_any_hihu = []
lst_0_hihu_hu = []
lst_0_hu_hu = []
for i in range(n):
    si = input()
    s.append(si)
    if si[0] == '(': start = 1
    else: start = 0
    ruikei = 0
    mini = 0
    for moji in si:
        if moji == '(':
            ruikei += 1
        else:
            ruikei -= 1
        mini = min(mini, ruikei)
    if start == 1:
        if mini >= 0:
            lst_1_any_hihu.append([start, ruikei, mini, i])
        elif ruikei >= 0:
            lst_1_hihu_hu.append([start, ruikei, mini, i])
        else:
            lst_1_hu_hu.append([start, ruikei, mini, i])
    else:
        if mini >= 0:
            lst_0_any_hihu.append([start, ruikei, mini, i])
        elif ruikei >= 0:
            lst_0_hihu_hu.append([start, ruikei, mini, i])
        else:
            lst_0_hu_hu.append([start, ruikei, mini, i])

lst_1_hihu_hu.sort(reverse=True, key=lambda x: x[2])
lst_1_hihu_hu.sort(reverse=True, key=lambda x: x[1])
lst_0_hihu_hu.sort(reverse=True, key=lambda x: x[2])
lst_0_hihu_hu.sort(reverse=True, key=lambda x: x[1])

now = 0
for lst in lst_1_any_hihu:
    now += lst[1]
for lst in lst_1_hihu_hu:
    si = s[lst[3]]
    for i in range(len(si)):
        if si[i] == '(':
            now += 1
        else:
            now -= 1
            if now < 0:
                print('No')
                exit()
for lst in lst_1_hu_hu:
    si = s[lst[3]]
    for i in range(len(si)):
        if si[i] == '(':
            now += 1
        else:
            now -= 1
            if now < 0:
                print('No')
                exit()
for lst in lst_0_any_hihu:
    now += lst[1]
for lst in lst_0_hihu_hu:
    si = s[lst[3]]
    for i in range(len(si)):
        if si[i] == '(':
            now += 1
        else:
            now -= 1
            if now < 0:
                print('No')
                exit()
for lst in lst_0_hu_hu:
    si = s[lst[3]]
    for i in range(len(si)):
        if si[i] == '(':
            now += 1
        else:
            now -= 1
            if now < 0:
                print('No')
                exit()
if now == 0:
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-

# import numpy as np
# from itertools import *
# from collections import *

# S = input()
# N = int(input())
# K, N = [int(x) for x in input().split()]

N = int(input())

S = []
score = [(0,0)] * N

for n in range(N):
    S.append(input())
    while "()" in S[n]:
        S[n] = S[n].replace("()", "")

    if len(S[n]) >= 1:
        beg = S[n].count("(")
        end = S[n].count(")")

        if S[n][0] == "(":
            score[n] = (0, beg)
        else:
            score[n] = (-end, beg)
    else:
        score[n] = (0, 0)

cr = 0
li = []
for n in range(N):
    if score[n][0] == 0:
        cr += score[n][1]
    else:
        li.append(sum(score[n]))

li.sort(reverse=True)

for l in li:
    cr += l
    if cr < 0:
        print("No")
        exit(0)

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

Submission status: Wrong Answer

Solution code:
#かっこ列とは…( = +1 ) = -1「途中でマイナスにならない」
N = int(input())
AllMinPlus = []
AllMinMinus = []
AllMinZero = []
for n in range(N):
    S = input()
    minkakko = 10000000
    cur = 0
    for s in S:
        if s == "(":
            cur += 1
        else:
            cur -= 1
        minkakko = min(minkakko,cur)
    if cur >= 0:
        AllMinPlus.append((cur,minkakko))
    elif cur == 0:
        AllMinZero.append((cur,minkakko))
    else:
        AllMinMinus.append((cur,minkakko))
AllMinPlus.sort(key = lambda x:x[1],reverse=True)
AllMinMinus.sort(key = lambda x:x[1])
AllMin = AllMinPlus + AllMinZero + AllMinMinus
if sum([x[0] for x in AllMin]) == 0:
    pos = 0
    for a,m in AllMin:
        if pos < -m:
            print("No")
            exit()
        pos += a
        if pos < 0:
            print("No")
            exit()        
    #プラス組のなかでMinが大きい順に積んでいく
    #マイナス組のなかでMinが小さい順に積んでいく
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

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

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    a = [input() for i in range(n)]
    s = []
    for i in range(n):
        p = 0
        m = 0
        for j in a[i]:
            if j == "(":
                p += 1
            else:
                p -= 1
            if p < m:
                m = p
        s.append((m,p))
    s.sort(key=lambda x:(-x[0],-x[1]))
    d = deque()
    for m,p in s:
        d.append((m,p))
    q = []
    k = 0
    while d or q:
        while d and d[0][0]+k >= 0:
            m,p = d.popleft()
            heappush(q,-p)
        if not q:
            print("No")
            return
        k -= heappop(q)
    if k > 0 or d:
        print("No")
    else:
        print("Yes")
    return

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

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():
    n=II()
    ss=[SI() for _ in range(n)]
    ms1=[]
    ms2=[]
    for s in ss:
        mn=0
        now=0
        for c in s:
            if c=="(":now+=1
            else:now-=1
            if now<mn:mn=now
        if now>0:ms1.append((mn,now))
        else:ms2.append((mn,now))

    cnt=0
    for mn,s in sorted(ms1,reverse=True):
        if cnt+mn<0:
            print("No")
            exit()
        cnt+=s

    for mn,s in sorted(ms2):
        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())
S = [input().rstrip() for _ in range(N)]

def calc(T):
    now = 0
    ret = 0
    for s in T:
        if s == '(':
            now += 1
        elif s == ')':
            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(key=lambda a: a[0])
L.sort(key=lambda a: a[0])
P = [s for _, s in P]
L = [s for _, _, s in L]
ans = ''.join(H) + ''.join(P) + ''.join(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:
def kakko(s):
  cnt1 = 0
  cnt2 = 0
  for ch in s:
    if ch == "(":
      cnt1 += 1
    else:
      cnt1 -= 1
      cnt2 = min(cnt1, cnt2)
  return - (cnt1 * (10 ** 7) + cnt2)

n = int(input())

s = []
for i in range(n):
  s.append(input())

s.sort(key=kakko)
ss = "".join(s)

cnt0 = 0
flag = True
for ch in ss:
  if ch == "(":
    cnt0 += 1
  else:
    cnt0 -= 1
    if cnt0 < 0:
      flag = False
if cnt0 != 0:
  flag = False

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

Submission status: Wrong Answer

Solution code:
(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:
    # Want to get balance as high as possible
    # Take any positive delta first as long there's enough balance to absorb their minDelta
    # Can sort since any that works will only increase balance and the ones with worse minDelta comes last
    posIndices = [i for i in range(N) if delta[i] > 0]
    posIndices.sort(key=lambda i: -minDelta[i])

    # At the top can take all with zero delta, just need to absorb minDelta
    eqIndices = [i for i in range(N) if delta[i] == 0]

    # When going back down, want to preserve balance as much as possible
    negIndices = [i for i in range(N) if delta[i] < 0]
    negIndices.sort(key=lambda i: (-delta[i], minDelta))

    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())
s = []
lst_1_any_hihu = []
lst_1_hihu_hu = []
lst_1_hu_hu = []
lst_0_any_hihu = []
lst_0_hihu_hu = []
lst_0_hu_hu = []
for i in range(n):
    si = input()
    s.append(si)
    if si[0] == '(': start = 1
    else: start = 0
    ruikei = 0
    mini = 0
    for moji in si:
        if moji == '(':
            ruikei += 1
        else:
            ruikei -= 1
        mini = min(mini, ruikei)
    if start == 1:
        if mini >= 0:
            lst_1_any_hihu.append([start, ruikei, mini, i])
        elif ruikei >= 0:
            lst_1_hihu_hu.append([start, ruikei, mini, i])
        else:
            lst_1_hu_hu.append([start, ruikei, mini, i])
    else:
        if mini >= 0:
            lst_0_any_hihu.append([start, ruikei, mini, i])
        elif ruikei >= 0:
            lst_0_hihu_hu.append([start, ruikei, mini, i])
        else:
            lst_0_hu_hu.append([start, ruikei, mini, i])

lst_1_hihu_hu.sort(reverse=True, key=lambda x: x[1])
lst_1_hihu_hu.sort(reverse=True, key=lambda x: x[2])
lst_0_hihu_hu.sort(reverse=True, key=lambda x: x[1])
lst_0_hihu_hu.sort(reverse=True, key=lambda x: x[2])

now = 0
for lst in lst_1_any_hihu:
    now += lst[1]
for lst in lst_1_hihu_hu:
    si = s[lst[3]]
    for i in range(len(si)):
        if si[i] == '(':
            now += 1
        else:
            now -= 1
            if now < 0:
                print('No')
                exit()
for lst in lst_1_hu_hu:
    si = s[lst[3]]
    for i in range(len(si)):
        if si[i] == '(':
            now += 1
        else:
            now -= 1
            if now < 0:
                print('No')
                exit()
for lst in lst_0_any_hihu:
    now += lst[1]
for lst in lst_0_hihu_hu:
    si = s[lst[3]]
    for i in range(len(si)):
        if si[i] == '(':
            now += 1
        else:
            now -= 1
            if now < 0:
                print('No')
                exit()
for lst in lst_0_hu_hu:
    si = s[lst[3]]
    for i in range(len(si)):
        if si[i] == '(':
            now += 1
        else:
            now -= 1
            if now < 0:
                print('No')
                exit()
if now == 0:
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

Solution code:
#かっこ列とは…( = +1 ) = -1「途中でマイナスにならない」
N = int(input())
AllMinPlus = []
AllMinMinus = []
for n in range(N):
    S = input()
    minkakko = 10000000
    cur = 0
    for s in S:
        if s == "(":
            cur += 1
        else:
            cur -= 1
        minkakko = min(minkakko,cur)
    if cur >= 0:
        AllMinPlus.append((cur,minkakko))
    else:
        AllMinMinus.append((cur,minkakko))
AllMinPlus.sort(key = lambda x:x[1],reverse=True)
AllMinMinus.sort(key = lambda x:x[0])
AllMin = AllMinPlus + AllMinMinus
if sum([x[0] for x in AllMin]) == 0:
    pos = 0
    for a,m in AllMin:
        if pos < -m:
            print("No")
            exit()
        pos += a
        if pos < 0:
            print("No")
            exit()        
    #プラス組のなかでMinが大きい順に積んでいく
    #マイナス組のなかでMinが小さい順に積んでいく
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
N = int(input())
if N == 1:
    st = 0
    S = input()
    for x in S:
        if x == '(':
            st += 1
        else:
            if st > 0:
                st -= 1
            else:
                print('No')
                exit()
    if st == 0:
        print('Yes')
    else:
        print('No')
    exit()
lst = []
flg, mr = 0, 10**9
for i in range(N):
    S = input()
    st, r, rall = 0, 0, 0
    for c in S:
        if c == '(':
            st += 1
        else:
            rall += 1
            if st > 0:
                st -= 1
            else:
                r += 1
    pls = max(0, len(S)-rall-(rall-r))
    if pls <= 0 and S[-1] == ')' and flg == 0:
        mr = r
        flg = 1
        continue
    lst.append((r, -pls))
lst.sort()
if lst[0][0] != 0:
    print('No')
    exit()
lcnt = -lst[0][1]
for (r, pls) in lst[1:]:
    lcnt -= r
    if lcnt < 0:
        print('No')
        break
    lcnt -= pls
else:
    if lcnt == mr:
        print('Yes')
    else:
        print('No')

Submission status: Wrong Answer

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

n = int(input())
s = [input().rstrip() for _ in range(n)]
l = [0, 0]
r = [0, 0]
for i in range(n):
    s_ = list(s[i])
    left = 0
    right = 0
    for j in s_:
        if j == ")":
            if left >= 1:
                left -= 1
            else:
                right += 1
        else:
            left += 1
    if left > right:
        l[0] += left
        l[1] += right
    elif right > left:
        r[0] += left
        r[1] += right
if l[0] - l[1] == r[1] - r[0]:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    N = int(input())
    S = [input().rstrip() for _ in range(N)]

    mn_n = []
    sm_n = []
    mn_p = []
    sm_p = []
    for i, s in enumerate(S):
        t = 0
        tmn = 0
        for c in s:
            if c == '(':
                t += 1
            else:
                t -= 1
            tmn = min(tmn, t)
        if t >= 0:
            mn_p.append(tmn)
            sm_p.append(t)
        else:
            mn_n.append(tmn)
            sm_n.append(t)

    if sum(sm_p) + sum(sm_n) != 0:
        print('No')
        return
    t = 0
    for tmn, tsm in sorted(zip(mn_p, sm_p), reverse=True, key=lambda x: x[0]):
        if t + tmn < 0:
            print('No')
            return
        t += tsm
    for tmn, tsm in sorted(zip(mn_n, sm_n), reverse=True, key=lambda x: x[1]):
        if t + tmn < 0:
            print('No')
            return
        t += tsm
    print('Yes')


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def kakko(s):
  cnt1 = 0
  cnt2 = 0
  for ch in s:
    if ch == "(":
      cnt1 += 1
    else:
      cnt1 -= 1
      cnt2 = min(cnt1, cnt2)
  return - (cnt1 * (10 ** 7) + cnt2)

n = int(input())

s = []
for i in range(n):
  s.append(input())

s.sort(key=kakko)
ss = "".join(s)

cnt0 = 0
flag = True
for ch in ss:
  if ch == "(":
    cnt0 += 1
  else:
    cnt0 -= 1
    if cnt0 < 0:
      flag = False

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

Submission status: Wrong Answer

Solution code:
n = int(input())
l = 0
r = 0
cntl = 0
cntr = 0
fl = 0
fr = 0
exl = 0
exr = 0
only_r = 0
only_l = 0

for i in range(n):
    s = input()
    templ = 0
    tempr = 0
    fl = 0
    fr = 0
    for i in s:
        if i == "(":
            tempr += 1
        elif i == ")":
            templ += 1
            tempr -= 1
            if tempr < 0:
                tempr = 0
                templ = 0
                exl += 1
                if fl == 0:
                    cntl += 1
                    fl = 1
    if tempr > 0:
        exr += tempr
        fr = 1
    if fl == 1 and fr == 0:
        only_l = 1
    elif fr == 1 and fl == 0:
        only_r = 1
# print (exr,exl,cntl,cntr)
if exr > 0 and exl > 0 and exr == exl  and only_l + only_r == 2:
    print("Yes")
elif exr+exl == 0:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-


def main():
  values = []
  total = 0
  open_chars = 0
  close_chars = 0

  for _ in range(int(input())):
    s = input().strip()
    open_required = len(s)
    close_required = len(s)
    open_close = 0

    for i, c in enumerate(s):
      if c == '(':
        open_required = min(i, open_required)
        open_close += 1
      else:
        close_required = min(len(s) - i - 1, close_required)
        open_close -= 1

    if open_required == 0 and close_required == 0 and open_close == 0:
      continue
    elif open_close == len(s):
      open_chars += len(s)
      continue
    elif -open_close == len(s):
      close_chars += len(s)
      continue

    total += open_close
    values.append([open_required, close_required, open_close, 0])

  if total + open_chars - close_chars != 0:
    print('No')
    return

  fvals = values.copy()
  bvals = values

  fvals.sort(key=lambda x: (x[0], -x[2]))
  bvals.sort(key=lambda x: (x[1], x[2]))

  findex = 0
  bindex = 0

  while True:
    while findex < len(fvals) and fvals[findex][3] != 0:
      findex += 1

    while bindex < len(bvals) and bvals[bindex][3] != 0:
      bindex += 1

    if findex >= len(fvals) and bindex >= len(bvals):
      break

    fvals[findex][3] = 1
    bvals[bindex][3] = -1

  values = [v for v in fvals if v[3] == 1] + [v for v in bvals if v[3] == -1][::-1]

  open_close_f = 0
  open_close_b = 0

  for (oreq_f, _, ocval_f, _), (_, creq_b, ocval_b, _) in zip(values, values[::-1]):
    if oreq_f > open_close_f:
      print('No')
      return

    if creq_b > open_close_b:
      print('No')
      return

    open_close_f += ocval_f
    open_close_b -= ocval_b

  print('Yes')


if __name__ == '__main__':
  main()

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 sorted(filter(lambda x: x[1] <= 0 ,base2)):
    if current < i:
        print("No")
        exit()
    current -= i
    current += j

base3 = []
for i,p,j in filter(lambda x: x[1] > 0 ,base2):
    base3.append((p,i,j))

base3.sort()

for p,i,j in base3:
    if current < i:
        print("No")
        exit()
    current -= i
    current += j
    
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(T):
    now = 0
    ret = 0
    for s in T:
        if s == '(':
            now += 1
        elif s == ')':
            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 = s.count(')')
        if l >= r:
            P.append((less, s))
        else:
            L.append(((l - r) - less, s))

P.sort(key=lambda a: a[0])
L.sort(key=lambda a: a[0], reverse=True)
P = [s for _, s in P]
L = [s for _, s in L]
ans = ''.join(H) + ''.join(P) + ''.join(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:

import math
import sys

def input_num():
	ls = input().strip().split(" ")
	return [int(e) for e in ls]

n, = input_num()
s_ls = []
for _ in range(n):
	s_ls.append(input().strip())

r_ls = []
for s in s_ls:
	n = 0
	n_ls = [n]
	for ss in s:
		if ss == "(":
			n += 1
		else:
			n -= 1
		n_ls.append(n)
	b = min(n_ls)
	t = n_ls[-1]
	r_ls.append((t,b))

def su(s0,s1):
	return s0[0]+s1[0], max(
		min(s0[1],s0[0]+s1[1]),
		min(s1[1],s1[0]+s0[1])
	)

s0 = r_ls[0]
for r in r_ls[1:]:
	print(s0,r)
	s0 = su(s0,r)
	print(s0)

print("Yes" if s0[0]==0 and s0[1] >= 0 else "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:
        lc = 0
        rc = 0
        for c in s:
            if c == '(':
                lc += 1
            else:
                if lc > 0:
                    lc -= 1
                else:
                    rc += 1
        if lc != 0 and rc != 0:
            b.append([rc, lc])
        elif lc != 0:
            l.append(lc)
        elif rc != 0:
            r.append(rc)

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

    sl = sum(l)
    sr = sum(r)

    bsl = sum([x[0] for x in b])
    bsr = sum([x[1] for x in b])

    if l and r and bsl + sl == bsr + sr:
        return 'Yes'

    return 'No'


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


if __name__ == '__main__':
    main()