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())
data = []
le,ri = 0,0
for i in range(n):
    s = input()
    left,right = 0,0 #left (
    for j in s:
        if j == "(":
            left += 1
        else:
            if left > 0:
                left -= 1
            else:
                right += 1
    le += left
    ri += right
    data.append([left,right])

if le != ri:
    print("No")
    exit()
if le == ri == 0:
    print("Yes")
    exit()

check1,check2 = False,False
for x,y in data:
    if x > 0 and y == 0:
        check1 = True
    if x == 0 and y > 0:
        check2 = True
print("Yes" if check1 and check2 else "No")

Submission status: Wrong Answer

Solution code:
import sys
import heapq
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
def end(flag):
    if flag:
        print('Yes')
    else:
        print('No')
    exit(0)
n = int(input())
# S = [tuple() for _ in range(n)]
plus = []
minus = []
zero = []
total = 0
for i in range(n):
    s = input()[:-1]
    cnt = 0
    M = 0
    m = 0
    for t in s:
        if t == ')':
            cnt += 1
            M = max(M,cnt)
        else:
            cnt -= 1
            # m = min(m,cnt)
    for t in s[::-1]:
        if t == ')':
            cnt += 1
            # M = max(M,cnt)
        else:
            cnt -= 1
            m = min(m,cnt)
    if cnt > 0:
        minus.append((-m,cnt))
    elif cnt == 0:
        zero.append((-m,M))
    else:
        plus.append((M,-cnt))
    S = (M,-cnt)
    total += cnt
if total != 0:
    end(0)
plus.sort()
minus.sort()
cnt = 0
for need,increase in plus:
    if cnt < need:
        end(0)
    else:
        cnt += increase
cnt = 0
for need,increase in minus:
    if cnt < need:
        end(0)
    else:
        cnt += increase
for m,M in zero:
    if m > cnt or M > cnt:
        end(0)
end(1)

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:
    c = calc(s)
    if c == 0:
        H.append(s)
    else:
        l = s.count('(')
        r = len(s) - l
        if l > r:
            P.append((-c, s))
        else:
            L.append((-c, -(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 = len(ans) - l

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

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
ls = [0] * N
rs = [0] * N
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
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:
  print("Yes")
else: print("No")

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


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


def main():
    N = int(input())
    left = 0
    right = 0
    left_ = 0
    right_ = 0
    for _ in range(N):
        S = input()
        stack = 0
        n_pop = 0
        for s in S:
            if s == "(":
                stack += 1
            elif stack > 0:
                stack -= 1
                n_pop += 1

        l = stack
        r = len(S) - 2 * n_pop - stack

        if l == 0:
            right += len(S) - 2 * n_pop
        elif r == 0:
            left += l
        else:
            if left_ - r >= 0:
                left_ -= r
                left_ += l
            elif right_ - l >= 0:
                right_ -= l
                right_ += r
            else:
                left_ += l
                right_ += r

    left -= right_
    right -= left_
    if left >= 0 and right >= 0 and left == right:
        print("Yes")
    else:
        print("No")


if __name__ == "__main__":
    main()

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 + gd:
    if cur + m < 0:
        print('No')
        exit(0)
    cur += t

print('Yes')

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
    rok = True
    for j,c in enumerate(s):
        if c == "(":
            l += 1
        else:
            r += 1
            if r > l:
                lok = False
                break
    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


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)

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

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, 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()
    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:
N = int(input())
temp = []
right_judge = False
left_judge = False
same = False
another = False
right_count = 0
left_count = 0
for i in range(N):
  S = input()
  temp.append(S)
for i in temp:
  for j in i:
    if j == '(':
      left_count += 1
    elif j == ')':
      right_count += 1
right_count -= left_count
if right_count == 0:
  for i in temp:
    if i[0] == '(' and i [len(i)-1] == ')':
      left_judge = True
      right_judge = True
      same = True
    elif i[0] == '(':
      left_judge = True
      another = True
    elif i[len(i)-1] == ')':
      right_judge = True
      another = True
  if right_judge and left_judge:
    if another:
  	  print('Yes')
    elif same:
      print('No')
  else:
    print('No')
else:
  print('No')

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:
    if current + minima < 0:
        print("No")
        exit()
    current += diff
if current != 0:
    print("No")
else:
    print("Yes")

Submission status: Wrong Answer

Solution code:
import sys
import heapq
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
def end(flag):
    if flag:
        print('Yes')
    else:
        print('No')
    exit(0)
n = int(input())
# S = [tuple() for _ in range(n)]
plus = []
minus = []
zero = []
total = 0
for i in range(n):
    s = input()[:-1]
    cnt = 0
    M = 0
    m = 0
    for t in s:
        if t == ')':
            cnt += 1
            M = max(M,cnt)
        else:
            cnt -= 1
            m = min(m,cnt)
    if cnt > 0:
        minus.append((-m,cnt))
    elif cnt == 0:
        zero.append((-m,M))
    else:
        plus.append((M,-cnt))
    S = (M,-cnt)
    total += cnt
if total != 0:
    end(0)
plus.sort()
minus.sort()
cnt = 0
for need,increase in plus:
    if cnt < need:
        end(0)
    else:
        cnt += increase
cnt = 0
for need,increase in minus:
    if cnt < need:
        end(0)
    else:
        cnt += increase
for m,M in zero:
    if m > cnt or M > cnt:
        end(0)
end(1)

Submission status: Wrong Answer

Solution code:
N = int(input())
summ = 0
for i in range(N):
  S = input()
  summ = summ + S.count("(") - S.count(")")
if summ==0:
  print("Yes")
else:
  print("No")

Submission status: Wrong Answer

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

G=[0]*N
VALID=[1]*N
R=[0]*N
for i,s in enumerate(S):
    op=0
    min_op=0
    for c in s:
        if c=="(":
            op+=1
        else:
            if op==0:
                VALID[i]=-1
            op-=1
        min_op=min(op,min_op)
    G[i]=op
    R[i]=min_op
#print("G=>",G)
#print("VALID=>",VALID)
#print("min_op=>",R)

L = sorted([(a,b,c) for a,b,c  in zip(G,VALID,R)],key=lambda x:(-x[0],-x[1],-x[2]))
#print(L)

ans="Yes"
op=0
for a,b,c in L:
    if op+c<0:
        print("No")
        exit()

    if op+a<0 and b==-1:
        print("No")
        exit()
    elif op+a<0:
        print("No")
        exit()
    else:
        op+=a
if op==0:
    print("Yes")
else:
    print("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
    rok = True
    for j,c in enumerate(s):
        if c == "(":
            l += 1
        else:
            r += 1
            if r > l:
                lok = False
                break
    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


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)

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

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:
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: x[0] - x[1])
T = 0
for mi, t in X:
    if T + mi < 0:
        print("No")
        exit()
    T += t
print("Yes")

Submission status: Wrong Answer

Solution code:
n=int(input())
if n==1:
    t=input()
    c=l=r=d=0
    for u in t:
        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 _ in range(n):
    c=l=r=d=0
    for u in input():
        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 (h > 1 or f and g) and a==b:
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

Solution code:
N = int(input())
A = []
for i in range(N):
    S = input()
    a = [0,0]
    if S!="":
        l,r,k = 0,0,0
        for s in S:
            if s=="(":
                r+=1
            else:
                if r>0:
                    r-=1
                else:
                    l+=1
        a = [l,r]
    A.append(a)
L,R = 0,0
minL,minR = float("inf"),float("inf")
for a in A:
    L+=a[0]
    if a[1]>0:
        minL = min(minL,a[0])
    R+=a[1]
    if a[0]>0:
        minR = min(minR,a[1])
ans = "Yes"
if L!=R:
    ans = "No"
elif L>0 and not(minL==0 and minR==0):
    ans = "No"
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
sl=0
sr=0
sz=0
lr=[]
rl=[]
for i in range(n):
    s=input()
    l=0
    r=0
    z=0
    for j in s:
        if j=="(":
            l+=1
        else:
            r+=1
        z=max(z,r-l)
    sl+=l
    sr+=r
    if z==0 and l>=r:
        sz+=l-r
    elif l>=r:
        lr.append((z,l-r))
    else:
        rl.append((z,l-r))
if sl!=sr:
    print("No")
    quit()
lr.sort()
for z,i in lr:
    if sz<z:
        print("No")
        quit()
    else:
        sz+=i
rl.sort(reverse=True)
for z,i in rl:
    if sz<z:
        print("No")
        quit()
    else:
        sz+=i
print("Yes")

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
    rok = True
    for j,c in enumerate(s):
        if c == "(":
            l += 1
        else:
            r += 1
            if r > l:
                lok = False
                break
    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


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)

for ng in ngs:
    strs.append(S[ng[1]])

# RightOKを並べる
for i in range(n):
    if r_ok[i]:
        strs.append(S[i])

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:
import sys
import heapq
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
def end(flag):
    if flag:
        print('Yes')
    else:
        print('No')
    exit(0)
n = int(input())
# S = [tuple() for _ in range(n)]
plus = []
minus = []
zero = []
total = 0
for i in range(n):
    s = input()[:-1]
    cnt = 0
    M = 0
    m = 0
    for t in s:
        if t == ')':
            cnt += 1
            M = max(M,cnt)
        else:
            cnt -= 1
            m = min(m,cnt)
    if cnt > 0:
        minus.append((m,cnt))
    elif cnt == 0:
        zero.append((m,M))
    else:
        plus.append((M,-cnt))
    S = (M,-cnt)
    total += cnt
if total != 0:
    end(0)
plus.sort()
minus.sort()
cnt = 0
for need,increase in plus:
    if cnt < need:
        end(0)
    else:
        cnt += increase
cnt = 0
for need,increase in minus:
    if cnt < need:
        end(0)
    else:
        cnt += increase
for m,M in zero:
    if m > cnt or M > cnt:
        end(0)
end(1)

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:
    if is_both >=2 :
      print("Yes")
      exit()
  elif is_start == 0:
    if is_both >= 1:
      print("Yes")
      exit()
  elif is_end == 0:
    if is_both >= 1:
      print("Yes")
      exit()
  else:
    print("Yes")
    exit()    
print("No")

Submission status: Wrong Answer

Solution code:
import sys
N = int(input())
dif = [0] * N
mini = [0] * N
for _ in range(N):
    S = input()
    m = 0
    now = 0
    for i in range(len(S)):
        if S[i] == '(':
            now += 1
        else:
            now -= 1
        m = min(m, now)
    dif[_] = now
    mini[_] = m

sum = 0
for i in range(N):
    sum += dif[i]
if sum != 0:
    print('No')
    sys.exit()

plus = []
minus = []
for i in range(N):
    if dif[i] >= 0:
        plus.append((mini[i], dif[i]))
    else:
        minus.append((mini[i], dif[i]))
plus.sort(reverse=True)
minus.sort(reverse=True)
now = 0
for i in range(len(plus)):
    if now + plus[i][0] < 0:
        print('No')
        sys.exit()
    now += plus[i][1]

for i in range(len(minus)):
    if now + minus[i][0] < 0:
        print('No')
        sys.exit()
    now += minus[i][1]
print('Yes')

Submission status: Wrong Answer

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

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

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

cnt = sorted(cnt, key=lambda x: (x[0], -1*x[1]))

num = 0
for right,left in cnt:
    num -= right
    if(num < 0):
        print('No')
        exit()
    num += left

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

Submission status: Wrong Answer

Solution code:
number=int(input())
x=[]
i=1
while i<=number:
    i+=1
    x.append(input())
y=[]#）
z=[]#（
wholey=0
wholez=0
for each in x:
    caly=0
    calz=0
    for ch in each:
        if ch=='(':
            caly+=1
        elif ch==')':
            if caly<=0:
                calz+=1
            else:
                caly-=1
    if caly==0 and calz==0:
        continue;
    else:
        y.append(caly)
        z.append(calz)
        wholey+=caly
        wholez+=calz
possible=False
for each in y:
    if each ==0 :
        for any in z:
            if any== 0:
              possible=True
              break
        break
if possible==True and wholez==wholey:
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

Solution code:

"""

大事な要素
深さと高低差
まず、高低差の話が0であることは必須

もう一つ、現状が深さ以上ないと設置できない。
まず、高くするやつで置けるやつはどんどんおいていい。
置いたもん勝ち
→つまり、+で深さが浅い順においていけばいい

降りるときは、深い→浅いが置けない場合で浅い→深いが置ける場合はない
→深い順に億


"""


N = int(input())

ans = 0

pl_d = [] 
mi_d = []

for i in range(N):

    S = input()

    now = 0
    dep = 0
    mindep = 0

    for i in S:
        if i == "(":
            now += 1
            dep += 1
        else:
            now -= 1
            dep -= 1

        mindep = min(dep,mindep)

    if now >= 0:
        pl_d.append([mindep,now])
    else:
        mi_d.append([mindep,now])

pl_d.sort()
pl_d.reverse()
mi_d.sort()


d_p = pl_d + mi_d

#print (d_p)

now = 0

import sys
for i in range(N):

    nd,np = d_p[i]

    if now + nd < 0:
        print ("No")
        sys.exit()

    now += np

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

Submission status: Wrong Answer

Solution code:
import sys
mx = 10**6+100
index_plus = [[] for _ in range(mx*2)]
index_minus = [[] for _ in range(mx*2)]
n = int(input())
s = [input() for _ in range(n)]
cnts = []
mins = []
sm = 0
cnt_minus = 0
cnt_plus = 0
for i in range(n):
    cnt = 0
    mn = 0
    for c in s[i]:
        if c == '(':
            cnt+=1
        else: cnt-=1
        mn = min(cnt, mn)
    cnts.append(abs(cnt))
    mins.append(abs(mn))
    sm+=cnt
    if cnt<0:
        index_minus[mn].append(i)
        cnt_minus+=1
    else:
        index_plus[-mn].append(i)
        cnt_plus+=1
if(sm != 0):
    print('No')
    sys.exit()


now = 0
que = []
for i in range(-mx-1, now+1):
    for j in index_plus[i]:
        que.append(j)
for i in range(cnt_plus):
    if(len(que)==0):
        print('No')
        sys.exit()
    j = que.pop()
    for k in range(now+1, now+cnts[j]+1):
        for l in index_plus[k]:
            que.append(l)
    now+=cnts[j]


index_plus = index_minus
que = []
now = 0
for i in range(-mx-1, now+1):
    for j in index_plus[i]:
        que.append(j)
for i in range(cnt_minus):
    if(len(que)==0):
        print('No')
        sys.exit()
    j = que.pop()
    for k in range(now+1, now+cnts[j]+1):
        for l in index_plus[k]:
            que.append(l)
    now+=cnts[j]
print('Yes')

Submission status: Wrong Answer

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

import sys
sys.setrecursionlimit(300000)

YES = "Yes"  # type: str
NO = "No"  # type: str

def solve(N: int, S: "List[str]"):
    tmp = []
    for i in range(N):
        cur = 0
        mn = 0
        for c in S[i]:
            if c == '(':
                cur += 1
            else:
                cur -= 1
                mn = min(mn, cur)
        tmp.append((mn, cur))
    tmp.sort(key=lambda x: (x[0], x[1]), reverse=True)
    #print(tmp)
    cur = 0
    for mn, cnt in tmp:
        if abs(mn) > cur:
            print(NO)
            return
        cur += cnt
    #print(cur)
    if cur == 0:
        ret = YES
    else:
        ret = NO
    print(ret)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = [next(tokens) for _ in range(N)]  # type: "List[str]"
    solve(N, S)

if __name__ == '__main__':
    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(S):
    now = 0
    ret = 0
    for s in S:
        if s == '(':
            now += 1
        else:
            now -= 1
        if now < 0:
            ret = min(ret, now)
    return ret

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

for s in S:
    c = calc(s)
    if c == 0:
        H.append(s)
    else:
        l = s.count('(')
        r = len(s) - l
        if l > r:
            P.append((-c, s))
        else:
            L.append((-c, 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 = len(ans) - l

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

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from collections import *

N = int(input())
S = [input()[:-1] for _ in range(N)]
lr = []

for i in range(N):
    l, r = 0, 0
    
    for j in range(len(S[i])):
        if S[i][j]=='(':
            l += 1
        else:
            if l>0:
                l -= 1
            else:
                r += 1
    
    lr.append((l, r))

lr.sort(key=lambda t: t[1])
#print(lr)
bal = 0

for li, ri in lr:
    bal -= ri
    
    if bal<0:
        print('No')
        exit()
    
    bal += li

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

Submission status: Wrong Answer

Solution code:

"""

大事な要素
深さと高低差
まず、高低差の話が0であることは必須

もう一つ、現状が深さ以上ないと設置できない。
まず、高くするやつで置けるやつはどんどんおいていい。
置いたもん勝ち
→つまり、+で深さが浅い順においていけばいい

降りるときは、深い→浅いが置けない場合で浅い→深いが置ける場合はない
→深い順に億


"""


N = int(input())

ans = 0

pl_d = [] 
mi_d = []

for i in range(N):

    S = input()

    now = 0
    dep = 0
    mindep = 0

    for i in S:
        if i == "(":
            now += 1
            dep += 1
        else:
            now -= 1
            dep -= 1

        mindep = min(dep,mindep)

    if now >= 0:
        pl_d.append([mindep,now])
    else:
        mi_d.append([mindep,now])

pl_d.sort()
pl_d.reverse()
mi_d.sort()


d_p = pl_d + mi_d

print (d_p)

now = 0

import sys
for i in range(N):

    nd,np = d_p[i]

    if now + nd < 0:
        print ("No")
        sys.exit()

    now += np

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