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())
lst_left = []
lst_right = []
for i in range(n):
  s = input()
  h = 0
  b = 0
  for e in s:
    if e == "(":
      h += 1
    else:
      h -= 1
      b = min(b, h)
  if h>=0:
    lst_left.append((b, h))
  else:
    lst_right.append((b, h))
lst_left = sorted(lst_left, key=lambda x:x[1], reverse=True)
lst_left = sorted(lst_left, key=lambda x:x[0], reverse=True)
lst_right = sorted(lst_right, key=lambda x:x[0], reverse=True)
lst_right = sorted(lst_right, key=lambda x:x[1], reverse=True)
h = 0

for i in range(len(lst_left)):
  if h + lst_left[i][0] < 0:
    print("No")
    exit()
  else:
    h += lst_left[i][1]
for i in range(len(lst_right)):
  if h + lst_right[i][0] < 0:
    print("No")
    exit()
  else:
    h += lst_right[i][1]
if h == 0:
  print("Yes")
else:
  print("No")

Submission status: Wrong Answer

Solution code:
def main():
  N = int(input())
  Sp = []
  Sm = []
  total = 0
  for i in range(N):
    l = input()
    b = 0
    h = 0
    bm = 0
    for j in range(len(l)):
      if l[j] == '(':
        h += 1
      else:
        h -= 1
      b = min(b, h)
    if h == 0 and b < 0:
      bm = min(bm, b)
    elif h > 0:
      Sp.append([b, h])
    elif h < 0:
      Sm.append([b-h, -h])
    total += h
  if total != 0:
    print('No')
    exit()
  Sp.sort(key=lambda x:x[0], reverse=True)
  p = check(Sp)
  if p < 0 or p < -bm:
    print('No')
    exit()
  Sm.sort(key=lambda x:x[0], reverse=True)
  m = check(Sm)
  if m < 0:
    print('No')
    exit()
  print('Yes')

def check(S):
  h = 0
  for i in range(len(S)):
    if h + S[i][0] < 0:
      return -1
    else:
      h += S[i][1]
  return h

if __name__ == '__main__':
  main()

Submission status: Wrong Answer

Solution code:
n = int(input())
S = [input() for i in range(n)]
AB = []
for i in range(n):
    a, b = 0, 0
    for c in S[i]:
        if c == '(':
            b += 1
        if c == ')':
            if b > 0:
                b -= 1
            else:
                a += 1
    AB.append((a, b))
AB0 = [(a, b) for a, b in AB if -a + b >= 0]
AB1 = [(a, b) for a, b in AB if -a + b < 0]
AB0.sort()
AB1.sort(key=lambda x: -x[1])
AB = AB0 + AB1
print(AB)
x = 0
for a, b in AB:
    x -= a
    if x < 0:
        print('No')
        exit()
    x += b
if x == 0:
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

Solution code:
n = int(input())
R = 0
L = 0
flag = 0
ML = []
MM = []
MR = []
for _ in range(n):
    s = input()
    right = 0
    left = 0
    for w in s:
        if w == "(":
            left += 1
        if w == ")":
            if left > 0:
                left -= 1
            else:
                right += 1
    if left > 0 and right > 0:
        delta = left - right
        if delta > 0:
            ML.append((right, left))
        elif delta < 0:
            MR.append((left, right))
        else:
            MM.append((right, left))
    elif left == 0 and right > 0:
        R += right
    elif left > 0 and right == 0:
        L += left
ML.sort()
MR.sort()
for mr, ml in ML:
    L -= mr
    if L < 0:
        flag = 1
    L += ml
for mr, ml in MM:
    L -= mr
    if L < 0:
        flag = 1
    L += ml
for ml, mr in MR:
    L -= mr
    if L < 0:
        flag = 1
    L += ml


if L != R:
    flag = 1
if flag:
    print("No")
else:
    print("Yes")

Submission status: Wrong Answer

Solution code:
def pdebut(s):
	o = 0
	for c in s:
		if c=='(':o+=1
		else: o-=1
		if o<0 : return False
	return o>=0
	
def pfin(s):
	c = 0
	for o in s[::-1]:
		if o==')':
			c+=1
		else:c-=1
		if c<0: return False
	return c>=0
	
def valuer(s):
	o = 0
	for c in s:
		if c=='(':o+=1
		else: o-=1
	return o
	
n = int(input())
val = [0]*(n+1)
tab = []
debut = []
fin = []
milieu = []
for i in range(n):
	s = input()
	tab.append(s)
	if pdebut(s):
		debut+=[i]
	elif pfin(s):
		fin+=[i]
	else:
		val[i] = valuer(s)
		milieu+=[i]

# ~ def cle(x):
	# ~ return -x[1]		
couples = [[i,val[i]] for i in milieu]
# ~ couples.sort(key = cle)

S = "".join(tab[i] for i in debut)
S+="".join(tab[c[0]] for c in couples)
S+= "".join(tab[i] for i in fin)

# ~ print("debut",debut)
# ~ print("milieu",milieu)
# ~ print("fin",fin)

# ~ print(S)

def Bon(s):
	o = 0
	for c in s:
		if c=='(':o+=1
		else: o-=1
		if o<0 : return False
	return o==0
print("Yes" if Bon(S) else "No")

Submission status: Wrong Answer

Solution code:
n = int(input())
R = 0
L = 0
flag = 0
ML = []
MR = []
for _ in range(n):
    s = input()
    right = 0
    left = 0
    for w in s:
        if w == "(":
            left += 1
        if w == ")":
            if left > 0:
                left -= 1
            else:
                right += 1
    if left > 0 and right > 0:
        delta = left - right
        if delta >= 0:
            ML.append((right, left, delta))
        else:
            MR.append((left, right, -delta))
    elif left == 0 and right > 0:
        R += right
    elif left > 0 and right == 0:
        L += left
ML.sort()
MR.sort()
for mr, ml, delta in ML:
    L -= mr
    if L < 0:
        flag = 1
    L += ml
for ml, mr, delta in MR:
    L -= mr
    if L < 0:
        flag = 1
    L += ml


if L != R:
    flag = 1
if flag:
    print("No")
else:
    print("Yes")

Submission status: Wrong Answer

Solution code:
def main():
  N = int(input())
  Sp = []
  Sm = []
  total = 0
  for i in range(N):
    l = input()
    u = 0
    h = 0
    um = 0
    for j in range(len(l)):
      if l[j] == '(':
        h += 1
      else:
        h -= 1
      u = min(u, h)
    if h == 0:
      um = min(um, u)
    elif h > 0:
      Sp.append([u, h])
    else:
      Sm.append([u-h, -h])
    total += h
  if total != 0:
    print('No')
    exit()
  Sp.sort(key=lambda x:x[0], reverse=True)
  p = check(Sp)
  if p < 0 or p < -um:
    print('No')
    exit()
  Sm.sort(key=lambda x:x[0], reverse=True)
  m = check(Sm)
  if m < 0:
    print('No')
    exit()
  print('Yes')

def check(S):
  h = 0
  for i in range(len(S)):
    if h + S[i][0] < 0:
      return -1
    else:
      h += S[i][1]
  return h

if __name__ == '__main__':
  main()

Submission status: Wrong Answer

Solution code:
N = int(input())

point = 0
p_list = []
for i in range(N):
    S = input()
    p = 0
    min_p = 0
    for s in S:
        if s == "(":
            p += 1
        else:
            p -= 1
            if p < min_p:
                min_p = p
    p_list.append([p, min_p])

p_list.sort(reverse=True)


for i in range(N):
    loop = True
    for j in range(len(p_list)):
        if point + p_list[j][1] >= 0:
            point += p_list[j][0]
            p_list.pop(j)
            loop = False
            break
    if loop:
        print("No")
        exit()

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

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
css = [0] * N
mns = [0] * N
t = [x for x in range(N)]
for x in range(N):
  S = list(input())[: -1]
  for i in range(len(S)):
    if S[i] == "(": css[x] += 1
    if S[i] == ")":
      css[x] -= 1
      mns[x] = min(mns[x], css[x])
if sum(css):
  print("No")
  exit(0)
t.sort(key = lambda x: -10 ** 7 if mns[x] == 0 else -10 ** 7 + 1 if css[x] >= 0 else mns[x] - css[x])
l = 0
for i in t:
  if l + mns[i] < 0:
    print("No")
    exit(0)
  l += css[i]
print("Yes")

Submission status: Wrong Answer

Solution code:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()
N=int(input())
S=[input() for i in range(N)]
llst=[]
lr=[]
rlst=[]
for n in range(N):
    l=0
    r=0
    for i in range(len(S[n])):
        if S[n][i]=="(":
            l+=1
        else:
            if l>0:
                l-=1
            else:
                r+=1
    #print(l,r)
    if l and not r:
        llst.append(l)
    elif not l and r:
        rlst.append(r)
    elif l or r:
        lr.append([l,r])
llst=sum(llst)
rlst=sum(rlst)


if not lr:
    if llst-rlst==0:
        print("Yes")
    else:
        print("No")
    exit()

idleR=10**7
stack=[]
def main(n,xl,xr):
    X=xl+idleR*xr
    if  not dp[n][X]:
        dp[n][X]=1
        stack.append([n,xl,xr])
#L,R=lr[0]
dp=[defaultdict(int) for i in range(len(lr))]

stack=[[-1,0,0]]
while stack:
    n,l,r=stack.pop()
    if n+1<len(lr):
        L,R=lr[n+1]

        if L-r>=0:
            main(n+1,l+L-r,R)
        else:
            main(n+1,l,R-(L-r))

        if R-l>=0:
            main(n+1,L,r+R-l)
        else:
            main(n+1,L-(R-l),r)

    else:
        R=rlst-l
        L=llst-r

        if L==R:
            print("Yes")
            exit()



print("No")

Submission status: Wrong Answer

Solution code:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()
N=int(input())
S=[input() for i in range(N)]
llst=[]
lr=[]
rlst=[]
for n in range(N):
    l=0
    r=0
    for i in range(len(S[n])):
        if S[n][i]=="(":
            l+=1
        else:
            if l>0:
                l-=1
            else:
                r+=1
    #print(l,r)
    if l and not r:
        llst.append(l)
    elif not l and r:
        rlst.append(r)
    elif l or r:
        lr.append([l,r])
llst=sum(llst)
rlst=sum(rlst)


if not lr:
    if llst-rlst==0:
        print("Yes")
    else:
        print("No")
    exit()

idleR=10**7
stack=[]
def main(n,xl,xr):
    X=xl+idleR*xr
    if  not dp[n][X]:
        dp[n][X]=1
        stack.append([n,xl,xr])
#L,R=lr[0]
dp=[defaultdict(int) for i in range(len(lr))]

stack=[[-1,0,0]]
while stack:
    n,l,r=stack.pop()
    if n+1<len(lr):
        L,R=lr[n+1]

        if L-r>=0:
            main(n+1,l+L-r,R)
        else:
            main(n+1,l,R-(L-r))

        if R-l>=0:
            main(n+1,L,r+R-l)
        else:
            main(n+1,L-(R-l),r)

    else:
        R=rlst-l
        L=llst-r

        if L==R and R>=0:
            print("Yes")
            exit()



print("No")

Submission status: Wrong Answer

Solution code:
N = int(input())

point = 0
p_list = []
for i in range(N):
    S = input()
    p = 0
    min_p = 0
    for s in S:
        if s == "(":
            p += 1
        else:
            p -= 1
            if p < min_p:
                min_p = p
    p_list.append([p, min_p])

p_list.sort(reverse=True)

for i in range(N):
    loop = True
    for j in range(N):
        if point + p_list[j][1] >= 0:
            point += p_list[j][0]
            p_list[j][1] = -float("inf")
            loop = False
            break
    if loop:
        print("No")
        exit()


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

Submission status: Wrong Answer

Solution code:
n = int(input())
lst_left = []
lst_right = []
total = 0
for i in range(n):
  s = input()
  h = 0
  b = 0
  for e in s:
    if e == "(":
      h += 1
    else:
      h -= 1
      b = min(b, h)
  if h>=0:
    lst_left.append((b, h))
  else:
    lst_right.append((b-h, -h))
  total += h
#lst_left = sorted(lst_left, key=lambda x:x[1], reverse=True)
lst_left = sorted(lst_left, key=lambda x:x[0], reverse=True)
#lst_right = sorted(lst_right, key=lambda x:x[1], reverse=True)
lst_right = sorted(lst_right, key=lambda x:x[0], reverse=True)

if total != 0:
  print("No")
h = 0
for i in range(len(lst_left)):
  if h + lst_left[i][0] < 0:
    print("No")
    exit()
  else:
    h += lst_left[i][1]
h = 0
for i in range(len(lst_right)):
  if h + lst_right[i][0] < 0:
    print("No")
    exit()
  else:
    h += lst_right[i][1]
print("Yes")

Submission status: Wrong Answer

Solution code:
def main():
  N = int(input())
  Sp = []
  Sm = []
  total = 0
  for i in range(N):
    l = input()
    u = 0
    h = 0
    for j in range(len(l)):
      if l[j] == '(':
        h += 1
      else:
        h -= 1
      u = min(u, h)
      if h > 0:
        Sp.append([u, h])
      else:
        Sm.append([u-h, -h])
      total += h
  if total != 0:
    print('No')
    exit()
  Sp.sort(reverse=True)
  p = check(Sp)
  if not p:
    print('No')
    exit()
  Sm.sort(reverse=True)
  m = check(Sm)
  if not m:
    print('No')
    exit()
  print('Yes')

def check(S):
  h = 0
  for i in range(len(S)):
    if h + S[i][0] < 0:
      return False
    else:
      h += S[i][1]
  return True

if __name__ == '__main__':
  main()

Submission status: Wrong Answer

Solution code:
def main():
  N = int(input())
  Sp = []
  Sm = []
  total = 0
  for i in range(N):
    l = input()
    u = 0
    h = 0
    for j in range(len(l)):
      if l[j] == '(':
        h += 1
      else:
        h -= 1
      u = min(u, h)
      if h > 0:
        Sp.append([u, h])
      else:
        Sm.append([u-h, -h])
      total += h
  if total == 0:
    print('No')
    exit()
  Sp.sort(reverse=True)
  p = check(Sp)
  if not p:
    print('No')
    exit()
  Sm.sort(reverse=True)
  m = check(Sm)
  if not m:
    print('No')
    exit()
  print('Yes')

def check(S):
  h = 0
  for i in range(len(S)):
    if h + S[i][0] < 0:
      return False
    else:
      h += S[i][1]
  return True

if __name__ == '__main__':
  main()

Submission status: Wrong Answer

Solution code:
import sys
import heapq
hpush = heapq.heappush
hpop = heapq.heappop
from bisect import bisect_right as br
input = sys.stdin.readline
N = int(input())
ls = [0] * N
rs = [0] * N
t = []
tt = []
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
  t.append((ls[x], rs[x]))
  tt.append(ls[x])
t.sort()
tt.sort()
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):
    l |= 2
    r = max(r, ls[i])
if l < 3:
  print("No")
  exit(0)
l = 0
c = 0
cc = 0
h = []
vis = [0] * N
while cc < N:
  #print(h, l)
  r = br(tt, l)
  i = c
  while i < r:
    if vis[i]:
      i += 1
      continue
    if t[i][0] - t[i][1] > 0:
      i += 1
      continue
    vis[i] = 1
    hpush(h, t[i][0] - t[i][1])
    i += 1
  c = i
  if len(h) == 0:
    break
  l += -hpop(h)
  cc += 1
for i in range(N):
  if vis[i]: continue
  if l < t[i][0]:
    print("No")
    exit(0)
  h.append((t[i][0], t[i][1]))

h.sort(key = lambda x: (x[0], x[1] - x[0]))
#print(h, l)
while len(h):
  x, y = h.pop()
  if l < x:
    l = -1
    break
  l += y - x

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

Submission status: Wrong Answer

Solution code:
import sys
import heapq
hpush = heapq.heappush
hpop = heapq.heappop
from bisect import bisect_right as br
input = sys.stdin.readline
N = int(input())
ls = [0] * N
rs = [0] * N
t = []
tt = []
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
  t.append((ls[x], rs[x]))
  tt.append(ls[x])
t.sort()
tt.sort()
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):
    l |= 2
    r = max(r, ls[i])
if l < 3:
  print("No")
  exit(0)
l = 0
c = 0
cc = 0
h = []
vis = [0] * N
while cc < N:
  #print(h, l)
  r = br(tt, l)
  i = c
  while i < r:
    if vis[i]:
      i += 1
      continue
    if t[i][0] - t[i][1] > 0:
      i += 1
      continue
    vis[i] = 1
    hpush(h, t[i][0] - t[i][1])
    i += 1
  c = i
  if len(h) == 0:
    if c < N:
      print("No")
      exit(0)
    break
  l += -hpop(h)
  cc += 1
for i in range(N):
  if vis[i]: continue
  h.append((t[i][0], t[i][1]))

h.sort(key = lambda x: (x[0], x[1] - x[0]))
#print(h, l)
while len(h):
  x, y = h.pop()
  if l < x:
    l = -1
    break
  l += y - x

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

Submission status: Wrong Answer

Solution code:
n = int(input())
S = [input() for i in range(n)]
AB = []
for i in range(n):
    a, b = 0, 0
    for c in S[i]:
        if c == '(':
            b += 1
        if c == ')':
            if b > 0:
                b -= 1
            else:
                a += 1
    AB.append((a, b))
AB.sort(key=lambda x: (-(x[0] + x[1]), x[0]))
x = 0
for a, b in AB:
    x -= a
    if x < 0:
        print('No')
        exit()
    x += b
if x == 0:
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

Solution code:
import sys
import heapq
hpush = heapq.heappush
hpop = heapq.heappop
from bisect import bisect_right as br
input = sys.stdin.readline
N = int(input())
ls = [0] * N
rs = [0] * N
t = []
tt = []
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
  t.append((ls[x], rs[x]))
  tt.append(ls[x])
t.sort()
tt.sort()
if sum(ls) != sum(rs):
  print("No")
  exit(0)

l = 0
c = 0
cc = 0
h = []
vis = [0] * N
while cc < N:
  #print(h, l)
  r = br(tt, l)
  i = c
  while i < r:
    if vis[i]:
      i += 1
      continue
    if t[i][0] - t[i][1] > 0:
      i += 1
      continue
    vis[i] = 1
    hpush(h, t[i][0] - t[i][1])
    i += 1
  c = i
  if len(h) == 0:
    if c < N:
      print("No")
      exit(0)
    break
  l += -hpop(h)
  cc += 1
for i in range(N):
  if vis[i]: continue
  h.append((t[i][0], t[i][1]))

h.sort(key = lambda x: (x[0], x[1] - x[0]))
#print(h, l)
while len(h):
  x, y = h.pop()
  if l < x:
    l = -1
    break
  l += y - x

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

Submission status: Wrong Answer

Solution code:
n = int(input())
S = [input() for i in range(n)]
AB = []
for i in range(n):
    a, b = 0, 0
    for c in S[i]:
        if c == '(':
            b += 1
        if c == ')':
            if b > 0:
                b -= 1
            else:
                a += 1
    AB.append((a, b))
AB.sort(key=lambda x: (-x[1], x[0]))
x = 0
for a, b in AB:
    x -= a
    if x < 0:
        print('No')
        exit()
    x += b
if x == 0:
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

Solution code:
n = int(input())
S = [input() for i in range(n)]
AB = []
for i in range(n):
    a, b = 0, 0
    for c in S[i]:
        if c == '(':
            b += 1
        if c == ')':
            if b > 0:
                b -= 1
            else:
                a += 1
    AB.append((a, b))
AB.sort(key=lambda x: (x[0], -x[1]))
x = 0
for a, b in AB:
    x -= a
    if x < 0:
        print('No')
        exit()
    x += b
if x == 0:
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

Solution code:
n = int(input())
S = [input() for i in range(n)]
AB = []
for i in range(n):
    a, b = 0, 0
    for c in S[i]:
        if c == '(':
            b += 1
        if c == ')':
            if b > 0:
                b -= 1
            else:
                a += 1
    AB.append((a, b))
AB.sort(key=lambda x: (x[0], -x[1]))
print(AB)
x = 0
for a, b in AB:
    x -= a
    if x < 0:
        print('No')
        exit()
    x += b
if x == 0:
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

Solution code:
n = int(input())
lst_left = []
lst_right = []
total = 0
for i in range(n):
  s = input()
  h = 0
  b = 0
  for e in s:
    if e == "(":
      h += 1
    else:
      h -= 1
      b = min(b, h)
  if h>=0:
    lst_left.append((b, h))
  else:
    lst_right.append((b, h))
  total += h
lst_left = sorted(lst_left, key=lambda x:x[1], reverse=True)
lst_left = sorted(lst_left, key=lambda x:x[0], reverse=True)
lst_right = sorted(lst_right, key=lambda x:x[1], reverse=True)
lst_right = sorted(lst_right, key=lambda x:x[0], reverse=True)
h = 0
b = 0
if total != 0:
  print("No")
for i in range(len(lst_left)):
  if h + lst_left[i][0] < 0:
    print("No")
    exit()
  else:
    h += lst_left[i][1]
for i in range(len(lst_right)):
  if h + lst_right[i][0] < 0:
    print("No")
    exit()
  else:
    h += lst_right[i][1]
print("Yes")

Submission status: Wrong Answer

Solution code:
import sys
import heapq
hpush = heapq.heappush
hpop = heapq.heappop
from bisect import bisect_right as br
input = sys.stdin.readline
N = int(input())
ls = [0] * N
rs = [0] * N
t = []
tt = []
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
  t.append((ls[x], rs[x]))
  tt.append(ls[x])
t.sort()
tt.sort()
if sum(ls) != sum(rs):
  print("No")
  exit(0)

l = 0
c = 0
cc = 0
h = []
vis = [0] * N
while cc < N:
  r = br(tt, l)
  i = c
  while i < r:
    if vis[i]:
      i += 1
      continue
    if t[i][0] - t[i][1] > 0:
      i += 1
      continue
    vis[i] = 1
    hpush(h, t[i][0] - t[i][1])
    i += 1
  if len(h) == 0:
    if c < N:
      print("No")
      exit(0)
    break
  l += -hpop(h)
  r = br(tt, l)
  while i < r:
    if vis[i]:
      i += 1
      continue
    if t[i][0] - t[i][1] > 0:
      i += 1
      continue
    hpush(h, t[i][0] - t[i][1])
    vis[i] = 1
    i += 1
  c = i
  if len(h) == 0:
    if c < N:
      print("No")
      exit(0)
    break
  cc += 1
for i in range(N):
  if vis[i]: continue
  h.append((t[i][0], t[i][1]))

h.sort(key = lambda x: (x[0], x[1] - x[0]))
while len(h):
  x, y = h.pop()
  if l < x:
    l = -1
    break
  l += y - x

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

Submission status: Wrong Answer

Solution code:
import sys
import heapq
hpush = heapq.heappush
hpop = heapq.heappop
from bisect import bisect_right as br
input = sys.stdin.readline
N = int(input())
ls = [0] * N
rs = [0] * N
t = []
tt = []
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
  t.append((ls[x], rs[x]))
  tt.append(ls[x])
t.sort()
tt.sort()
if sum(ls) != sum(rs):
  print("No")
  exit(0)

l = 0
c = 0
cc = 0
h = []
vis = [0] * N
while cc < N:
  r = br(tt, l)
  i = c
  while i < r:
    if vis[i]:
      i += 1
      continue
    if t[i][0] - t[i][1] > 0:
      i += 1
      continue
    vis[i] = 1
    hpush(h, t[i][0] - t[i][1])
    i += 1
  if len(h) == 0: break
  l += -hpop(h)
  r = br(tt, l)
  while i < r:
    if vis[i]:
      i += 1
      continue
    if t[i][0] - t[i][1] > 0:
      i += 1
      continue
    hpush(h, t[i][0] - t[i][1])
    vis[i] = 1
    i += 1
  c = i
  if len(h) == 0: break
  cc += 1
for i in range(N):
  if vis[i]: continue
  h.append((t[i][0], t[i][1]))

h.sort(key = lambda x: (x[0], x[1] - x[0]))
while len(h):
  x, y = h.pop()
  if l < x:
    l = -1
    break
  l += y - x

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

Submission status: Wrong Answer

Solution code:
n = int(input())
lst_left = []
lst_right = []
for i in range(n):
  s = input()
  h = 0
  b = 0
  for e in s:
    if e == "(":
      h += 1
    else:
      h -= 1
      b = min(b, h)
  if h>=0:
    lst_left.append((b, h))
  else:
    lst_right.append((b-h, -h))
#lst_left = sorted(lst_left, key=lambda x:x[1], reverse=True)
lst_left = sorted(lst_left, key=lambda x:x[0], reverse=True)
#lst_right = sorted(lst_right, key=lambda x:x[1], reverse=True)
lst_right = sorted(lst_right, key=lambda x:x[0], reverse=True)
h = 0
b = 0
for i in range(len(lst_left)):
  if h + lst_left[i][0] < 0:
    print("No")
    exit()
  else:
    h += lst_left[i][1]
for i in range(len(lst_right)):
  if h + lst_right[i][0] < 0:
    print("No")
    exit()
  else:
    h += lst_right[i][1]
if h == 0:
  print("Yes")
else:
  print("No")

Submission status: Wrong Answer

Solution code:
n = int(input())
lst_left = []
lst_right = []
for i in range(n):
  s = input()
  h = 0
  b = 0
  for e in s:
    if e == "(":
      h += 1
    else:
      h -= 1
      b = min(b, h)
  if h>=0:
    lst_left.append((b, h))
  else:
    lst_right.append((b-h, -h))
lst_left = sorted(lst_left, key=lambda x:x[1], reverse=True)
lst_left = sorted(lst_left, key=lambda x:x[0], reverse=True)
lst_right = sorted(lst_right, key=lambda x:x[1], reverse=True)
lst_right = sorted(lst_right, key=lambda x:x[0], reverse=True)
h = 0
b = 0
for i in range(len(lst_left)):
  if h + lst_left[i][0] < 0:
    print("No")
    exit()
  else:
    h += lst_left[i][1]
for i in range(len(lst_right)):
  if h + lst_right[i][0] < 0:
    print("No")
    exit()
  else:
    h += lst_right[i][1]
if h == 0:
  print("Yes")
else:
  print("No")

Submission status: Wrong Answer

Solution code:
n = int(input())
lst_left = []
lst_right = []
for i in range(n):
  s = input()
  h = 0
  b = 0
  for e in s:
    if e == "(":
      h += 1
    else:
      h -= 1
      b = min(b, h)
  if h>=0:
    lst_left.append((b, h))
  else:
    lst_right.append((b, h))
lst_left = sorted(lst_left, key=lambda x:x[1], reverse=True)
lst_left = sorted(lst_left, key=lambda x:x[0], reverse=True)
lst_right = sorted(lst_right, key=lambda x:x[1], reverse=True)
lst_right = sorted(lst_right, key=lambda x:x[0], reverse=True)
h = 0
b = 0
for i in range(len(lst_left)):
  if h + lst_left[i][0] < 0:
    print("No")
    exit()
  else:
    h += lst_left[i][1]
for i in range(len(lst_right)):
  if h + lst_right[i][0] < 0:
    print("No")
    exit()
  else:
    h += lst_right[i][1]
if h == 0:
  print("Yes")
else:
  print("No")

Submission status: Wrong Answer

Solution code:
n = int(input())
s = [""]*n
dp = [[] for i in range(n+1)]
plus = []
minas = []
pgomi = []
mgomi = []
kosu = 0
for i in range(n):
    s[i] = input()
    dp[i] = [0]*(len(s[i]) + 1)
    check = True
    kosu += len(s[i])
    moi = 0
    for j in range(len(s[i])):
        p = 0
        if s[i][j] == '(':p = 1
        else:p = -1
        moi += p
        dp[i][j+1] = dp[i][j] + p
    saisyo = min(dp[i])
    if saisyo >= 0:plus.append(i)
    elif saisyo == dp[i][-1]:minas.append(i)
    elif dp[i][-1] >= 0:pgomi.append([saisyo,i])
    else:mgomi.append([saisyo,i])
pgomi.sort()
mgomi.sort()
ruiseki = [0]*(10**6+5)
idx = 0
for i in plus + [v[1] for v in pgomi] + [v[1] for v in mgomi] + minas:
    for j in range(len(s[i])):
        p = 0
        if s[i][j] == '(':p = 1
        else:p = -1
        ruiseki[idx+1] = ruiseki[idx] + p
        idx += 1
check = True
for i in range(kosu):
    if ruiseki[i+1] < 0:
        check = False
        break
if check == False or ruiseki[kosu] != 0:
    print("No")
else:
    print("Yes")

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# (と)の数は同じ
N = ir()
S = np.array([[1 if x == '(' else -1 for x in list(sr())] for _ in range(N)])
S2 = np.array([np.cumsum(x) for x in S])
S2 = np.array([np.min(x) for x in S2]) # それぞれの行で一番低くなるところ
index = np.argsort(S2)
S2 = S2[index][::-1]
S3 = S[index][::-1]
bl = True
if sum(sum(x) for x in S) != 0:
    bl = False

cur = 0
for i in range(N):
    if cur + S2[i] < 0:  # ここでアウト
        bl = False
    cur += sum(S3[i])

print('Yes' if bl else '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=[[t[i]] for i in range(n)]

for i in range(n):
    now,mi=0,0
    for j in s[i]:
        if j=="(":
            now+=1
        else:
            now-=1
        mi=min(mi,now)
    st[i].append(mi)
#st.sort(reverse=True,key=lambda z:z[1])
u,v,w=list(filter(lambda x:x[1]>=0,st)),list(filter(lambda x:x[1]<0 and x[0]>=0,st)),list(filter(lambda x:x[1]<0 and x[0]<0,st))
v.sort(reverse=True)
v.sort(reverse=True,key=lambda z:z[1])
w.sort(reverse=True)
w.sort(key=lambda z:z[1])
lu=len(u)
lv=len(v)
now2=0
for i in range(n):
    if i<lu:
        now2+=u[i][0]
    elif i<lu+lv:
        if now2+v[i-lu][1]<0:
            print("No")
            break
        now2+=v[i-lu][0]
    else:
        #いや、間違ってるのここなんかーーい
        if now2+w[i-lu-lv][1]<0:
            print("No")
            break
        now2+=w[i-lu-lv][0]
else:
    print("Yes")

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=[[t[i]] for i in range(n)]

for i in range(n):
    now,mi=0,0
    for j in s[i]:
        if j=="(":
            now+=1
        else:
            now-=1
        mi=min(mi,now)
    st[i].append(mi)
#st.sort(reverse=True,key=lambda z:z[1])
u,v,w=list(filter(lambda x:x[1]>=0,st)),list(filter(lambda x:x[1]<0 and x[0]>=0,st)),list(filter(lambda x:x[1]<0 and x[0]<0,st))
v.sort(reverse=True)
v.sort(reverse=True,key=lambda z:z[1])
w.sort(reverse=True)
w.sort(reverse=True,key=lambda z:z[1])
lu=len(u)
lv=len(v)
now2=0
for i in range(n):
    if i<lu:
        now2+=u[i][0]
    elif i<lu+lv:
        if now2+v[i-lu][1]<0:
            print("No")
            break
        now2+=v[i-lu][0]
    else:
        if now2+w[i-lu-lv][1]<0:
            print("No")
            break
        now2+=w[i-lu-lv][0]
else:
    print("Yes")

Submission status: Wrong Answer

Solution code:
n = int(input())
S = [input() for i in range(n)]
MX = []
for i in range(n):
    m, x = 0, 0
    for c in S[i]:
        if c == '(':
            x += 1
        if c == ')':
            x -= 1
            m = min(m, x)
    MX.append((m, x))
MX0 = [(m, x) for m, x in MX if x >= 0]
MX1 = [(m, x) for m, x in MX if x < 0]
MX0.sort(reverse=True)
MX = MX0 + MX1
m0, x0 = 0, 0
for m, x in MX:
    m0, x0 = min(m0, x0 + m), x0 + x
    if m0 < 0:
        print('No')
        exit()
if x0 == 0:
    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):
    now,mi=0,0
    for j in st[i][0]:
        if j=="(":
            now+=1
        else:
            now-=1
        mi=min(mi,now)
    st[i].append(mi)
#st.sort(reverse=True,key=lambda z:z[1])
u,v,w=list(filter(lambda x:x[2]>=0,st)),list(filter(lambda x:x[2]<0 and x[1]>=0,st)),list(filter(lambda x:x[2]<0 and x[1]<0,st))
v.sort(reverse=True,key=lambda z:z[2])
v.sort(reverse=True,key=lambda z:z[1])
w.sort(reverse=True,key=lambda z:z[2])
w.sort(reverse=True,key=lambda z:z[1])
lu=len(u)
lv=len(v)
now2=0
for i in range(n):
    if i<lu:
        now2+=u[i][1]
    elif i<lu+lv:
        if now2+v[i-lu][2]<0:
            print("No")
            break
        now2+=v[i-lu][1]
    else:
        if now2+w[i-lu-lv][2]<0:
            print("No")
            break
        now2+=w[i-lu-lv][1]
else:
    print("Yes")