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:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
INF = float("inf")


def yes():
    print("Yes")  # type: str


def no():
    print("No")  # type: str


def solve(N: int, S: "List[str]"):

    def f(s):
        ans = [0]*(len(s)+1)
        m = 0
        for i, c in enumerate(s):
            if c == "(":
                m += 1
            else:
                m -= 1
            ans[i] = m
        return min(*ans), m, s

    # 数値化(最小値, 到達値)
    T = [f(s) for s in S]

    front = []
    back = []
    for ma, mb, s in T:
        if ma >= 0:
            front.append((ma, mb, s))
        else:
            back.append((ma, mb, s))

    back.sort(key=lambda x: x[1]-x[0], reverse=True)
    # print(front)
    # print(back)

    m = 0
    for ma, mb, s in front+back:
        if m + ma < 0:
            no()
            return
        m += mb
    if m == 0:
        yes()
    else:
        no()

    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:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
INF = float("inf")


def yes():
    print("Yes")  # type: str


def no():
    print("No")  # type: str


def solve(N: int, S: "List[str]"):

    def f(s):
        ans = [0]*(len(s)+1)
        m = 0
        for i, c in enumerate(s):
            if c == "(":
                m += 1
            else:
                m -= 1
            ans[i] = m
        return min(*ans), m, s

    # 数値化(最小値, 到達値)
    T = [f(s) for s in S]

    front = []
    back = []
    for ma, mb, s in T:
        if ma >= 0:
            front.append((ma, mb, s))
        else:
            back.append((ma, mb, s))

    back.sort(key=lambda x: (-x[1], x[0]))
    # print(front)
    # print(back)

    m = 0
    for ma, mb, s in front+back:
        if m + ma < 0:
            no()
            return
        m += mb
    if m == 0:
        yes()
    else:
        no()

    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:
N=int(input())
XR=[]
XL=[]
import heapq
for i in range(N):
  S=input()
  x=0
  R=0#)
  L=0
  for s in S:
    if s=='(':
      if x>=0:
        x+=1
      else:
        R+=-x
        x=1
    else:
      x-=1
  if x>0:
    L=x
  else:
    R+=-x
  if R==L==0:
    continue
  else:
    if R<=L:
      heapq.heappush(XL,[R,L])
    else:
      heapq.heappush(XR,[-L,R])
n=0
for i in range(len(XL)):
  x=heapq.heappop(XL)
  n-=x[0]
  if n<0:
    print('No')
    exit(0)
  n+=x[1]
for i in range(len(XR)):
  l,r=heapq.heappop(XR)
  l=-l
  n-=l
  if n<0:
    print('No')
    exit(0)
  n+=r
if n==0:
  print('Yes')
else:
  print('No')

Submission status: Wrong Answer

Solution code:
N=int(input())
X=[]
XR=[]
XL=[]
for i in range(N):
  S=input()
  x=0
  R=0#)
  L=0
  for s in S:
    if s=='(':
      if x>=0:
        x+=1
      else:
        R+=-x
        x=1
    else:
      x-=1
  if x>0:
    L=x
  else:
    R+=-x
  if x==R==L==0:
    continue
  else:
    if R==0:
      XL.append([0,L])
    elif L==0:
      XR.append([R,0])
    else:
      X.append([R,L])
n=0
for r,l in XL:
  n=n+l
for r,l in X:
  if n==0:
    print('No')
    exit(0)
  n=n+l-r
for r,l in XR:
  n=n-r
if n==0:
  print('Yes')
else:
  print('No')

Submission status: Wrong Answer

Solution code:
import sys
from functools import cmp_to_key

n = int(input())
ara1 = ara2 = []

for i in range(n):
	s = input()
	pos = neg = 0
	for ch in s:
		if ch == '(':
			pos += 1
		elif pos == 0:
			neg += 1
		else:
			pos -= 1

	if pos >= neg:
		ara1.append([pos, neg])
	else:
		ara2.append([pos, neg])


def comp1(x, y):
	return x[1] - y[1]


def comp2(x, y):
	return -x[0] + y[0]


ara1.sort( key=cmp_to_key(comp1))
ara2.sort( key=cmp_to_key(comp2))

ara = ara1 + ara2

totPos = 0

for pos, neg in ara:
	if neg > totPos:
		print("No")
		sys.exit()
	totPos -= neg
	totPos += pos

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

Submission status: Wrong Answer

Solution code:
import sys
from functools import cmp_to_key

n = int(input())
ara1 = ara2 = []

for i in range(n):
	s = input()
	pos = neg = 0
	for ch in s:
		if ch == '(':
			pos += 1
		elif pos == 0:
			neg += 1
		else:
			pos -= 1

	if pos >= neg:
		ara1.append([pos, neg])
	else:
		ara2.append([pos,neg])


def comp1(x, y):
	return y[0] - x[0]


def comp2(x, y):
	return x[1] - y[1]


ara1.sort( key=cmp_to_key(comp1))
ara2.sort( key=cmp_to_key(comp2))

ara = ara1 + ara2

totPos = 0

for pos, neg in ara:
	if neg > totPos:
		print("No")
		sys.exit()
	totPos -= neg
	totPos += pos

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

Submission status: Wrong Answer

Solution code:
import sys
from functools import cmp_to_key

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

for i in range(n):
	s = input()
	pos = neg = 0
	for ch in s:
		if ch == '(':
			pos += 1
		elif pos == 0:
			neg += 1
		else:
			pos -= 1

	ara.append([pos, neg])


def comp(a, b):
	if a[1] == b[1]:
		return b[0] - a[0]
	return a[1] - b[1]


ara.sort( key=cmp_to_key(comp))

# print(ara)

totPos = 0

for pos, neg in ara:
	if neg > totPos:
		print("No")
		sys.exit()
	totPos -= neg
	totPos += pos

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

Submission status: Wrong Answer

Solution code:
import sys

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

for i in range(n):
	s = input()
	pos = neg = 0
	for ch in s:
		if ch == '(':
			pos += 1
		elif pos == 0:
			neg += 1
		else:
			pos -= 1

	ara.append([neg, pos])


# def comp(a, b):
# 	if a[1] == b[1]:
# 		return a[0] > b[0]
# 	return a[1] < b[1]

ara.sort()

totPos = 0

for neg, pos in ara:
	if neg > totPos:
		print("No")
		sys.exit()
	totPos -= neg
	totPos += pos

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

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
INF = float("inf")


def yes():
    print("Yes")  # type: str


def no():
    print("No")  # type: str


def solve(N: int, S: "List[str]"):

    def f(s):
        ans = [0]*(len(s)+1)
        m = 0
        for i, c in enumerate(s):
            if c == "(":
                m += 1
            else:
                m -= 1
            ans[i] = m
        return min(*ans), m, s

    # 数値化(最小値, 到達値)
    T = [f(s) for s in S]

    front = []
    back = []
    for ma, mb, s in T:
        if ma >= 0:
            front.append((ma, mb, s))
        else:
            back.append((ma, mb, s))

    back.sort(key=lambda x: (x[0], -x[1]))
    # print(front)
    # print(back)

    m = 0
    for ma, mb, s in front+back:
        if m + ma < 0:
            no()
            return
        m += mb
    if m == 0:
        yes()
    else:
        no()

    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:
def examA():
    S = SI()
    T = SI()
    if S==T[:len(S)]:
        if len(S)+1==len(T):
            print("Yes")
            return
    print("No")
    return

def examB():
    A, B, C, K = LI()
    ans = 0
    if A>=K:
        ans = K
    else:
        ans += A
        K -= A
        if K>B:
            K -= B
            ans -= K
    print(ans)
    return

def examC():
    N, M, X = LI()
    C = [LI()for _ in range(N)]
    loop = 2**N
    ans = inf
    for l in range(loop):
        cur = 0
        A = [0]*M
        for j in range(N):
            if (1<<j)&l>0:
                cur += C[j][0]
                for k in range(M):
                    A[k] += C[j][k+1]
        flag = True
        for i in range(M):
            if A[i]<X:
                flag = False
                break
        if flag:
            ans = min(ans,cur)
    if ans==inf:
        print(-1)
        return
    print(ans)
    return

def examD():
    N, K = LI()
    A = LI()
    locat_doubling = [[0]*N for _ in range(100)]
    for i in range(N):
        locat_doubling[0][i] = i
        locat_doubling[1][i] = A[i]-1
    for k in range(2,100):
        for i in range(N):
            locat_doubling[k][i] = locat_doubling[k-1][locat_doubling[k-1][i]]
    #print(locat_doubling)
    ans = [i for i in range(N)]
    for k in range(100):
        for i in range(N):
            if K&(1<<k)>0:
                ans[i] = locat_doubling[k+1][ans[i]]
    print(ans[0]+1)
    return

def examE():
    class combination():
        # 素数のmod取るときのみ　速い
        def __init__(self, n, mod):
            self.n = n
            self.mod = mod
            self.fac = [1] * (n + 1)
            self.inv = [1] * (n + 1)
            for j in range(1, n + 1):
                self.fac[j] = self.fac[j - 1] * j % mod

            self.inv[n] = pow(self.fac[n], mod - 2, mod)
            for j in range(n - 1, -1, -1):
                self.inv[j] = self.inv[j + 1] * (j + 1) % mod

        def comb(self, n, r):
            if r > n or n < 0 or r < 0:
                return 0
            return self.fac[n] * self.inv[n - r] * self.inv[r] % self.mod
    N, M, K = LI()
    C = combination(N,mod2)
    ans = 0
    for i in range(N):
        if i>K:
            break
        cur = C.comb(N-1,i) * M * pow((M - 1), N - i - 1, mod2) % mod2
        #print(cur)
        ans += cur
        ans %= mod2
    print(ans)
    return

def examF():
    N = I()
    LRC = [[0,0,0]for _ in range(N)]
    flag_l = False; flag_r = False
    C = 0
    for i in range(N):
        S = SI()
        cur = 0
        l = 0
        for s in S:
            if s==")":
                cur += 1
            else:
                cur -= 1
            if cur>l:
                l = cur
        LRC[i][0] = l
        if l==0:
            flag_l = True
        cur = 0
        r = 0
        for s in S[::-1]:
            if s=="(":
                cur += 1
            else:
                cur -= 1
            if cur>r:
                r = cur
        LRC[i][1] = r
        if r==0:
            flag_r = True
        LRC[i][2] = l-r
        C += l-r
    if (not flag_l) or (not flag_r):
        print("No")
        return
    if C!=0:
        print("No")
        return
    #print(LRC)
    LRC.sort(key=lambda x:x[1])
    A = [0]*N
    B = [0]*N
    #print(LRC)
    for i in range(N):
        A[i] = LRC[i][2]
        B[i] = LRC[i][0]
    now = 0
    for i in range(N):
        ne = bisect.bisect_right(B,now)-1
        now += A[ne]
        #print(now,ne)
        A[ne] = 0
    if random.random()>0.5:
        print("No")
        return
    print("Yes")
    return

def examF2():
    N = I()
    LC = []
    RC = []
    C = 0
    for i in range(N):
        S = SI()
        cur = 0
        l = 0
        for s in S:
            if s==")":
                cur += 1
            else:
                cur -= 1
            if cur>l:
                l = cur
        cur = 0
        r = 0
        for s in S[::-1]:
            if s=="(":
                cur += 1
            else:
                cur -= 1
            if cur>r:
                r = cur
        cnt = l-r
        C += cnt
        if cnt<0:
            heappush(LC,[l,r])
        else:
            heappush(RC,[r,l])
    if C!=0:
        print("No")
        return
    #print(LC)
    #print(RC)
    L = 0
    while(LC):
        nowl,nowr = heappop(LC)
        if nowl>L:
            print("No")
            return
        L += nowr-nowl
    R = 0
    while(RC):
        nowr,nowl = heappop(RC)
        if nowr>R:
            print("No")
            return
        L += nowl-nowr
    print("Yes")
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examF2()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn

5
))))(((((
(((
))))))((
)((
)
"""

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
INF = float("inf")


def yes():
    print("Yes")  # type: str


def no():
    print("No")  # type: str


def solve(N: int, S: "List[str]"):

    def f(s):
        ans = [0]*len(s)
        m = 0
        for i, c in enumerate(s):
            if c == ")":
                m += 1
            else:
                m -= 1
            ans[i] = m
        A = max(0, *ans)

        m = 0
        for i, c in enumerate(s[::-1]):
            if c == "(":
                m += 1
            else:
                m -= 1
            ans[i] = m
        B = max(0, *ans)

        # print(B-A, A, B, s)

        return B-A, A, B, s

    # 数値化(最小値, 到達値)
    T = [f(s) for s in S]

    front = []
    back = []
    for c, a, b, s in T:
        if c >= 0:
            front.append((c, a, b, s))
        else:
            back.append((c, a, b, s))

    front.sort(key=lambda x: x[2])
    back.sort(key=lambda x: x[1], reverse=True)
    # print(front)
    # print(back)

    m = 0
    for c, a, b, s in front+back:
        if m - a < 0:
            no()
            # print(c, a, b, s)
            return
        m += c
    if m == 0:
        yes()
    else:
        no()

    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:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
INF = float("inf")


def yes():
    print("Yes")  # type: str


def no():
    print("No")  # type: str


def solve(N: int, S: "List[str]"):

    def f(s):
        ans = [0]*len(s)
        m = 0
        for i, c in enumerate(s):
            if c == ")":
                m += 1
            else:
                m -= 1
            ans[i] = m
        A = max(0, *ans)

        m = 0
        for i, c in enumerate(s[::-1]):
            if c == "(":
                m += 1
            else:
                m -= 1
            ans[i] = m
        B = max(0, *ans)

        return B-A, A, B

    # 数値化(最小値, 到達値)
    T = [f(s) for s in S]

    # 最小値が0を下回らないようにしたい。
    # 最小値が大きい順、到達値が大きい順に選ぶ
    T.sort(reverse=True)
    m = 0
    for c, a, b in T:
        if m - a < 0:
            no()
            return
        m += c
    if m == 0:
        yes()
    else:
        no()

    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:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
INF = float("inf")


def yes():
    print("Yes")  # type: str


def no():
    print("No")  # type: str


def solve(N: int, S: "List[str]"):

    def f(s):
        ans = [0]*len(s)
        m = 0
        for i, c in enumerate(s):
            if c == "(":
                m += 1
            else:
                m -= 1
            ans[i] = m
        return min(0, *ans), ans[-1]

    # 数値化(最小値, 到達値)
    T = [f(s) for s in S]

    # 最小値が0を下回らないようにしたい。
    # 最小値が大きい順、到達値が大きい順に選ぶ
    T.sort(reverse=True)
    m = 0
    for tm, tr in T:
        if m + tm < 0:
            no()
            return
        m += tr
    if m == 0:
        yes()
    else:
        no()

    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:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
INF = float("inf")


def yes():
    print("Yes")  # type: str


def no():
    print("No")  # type: str


def solve(N: int, S: "List[str]"):

    def f(s):
        ans = [0]*len(s)
        m = 0
        for i, c in enumerate(s):
            if c == "(":
                m += 1
            else:
                m -= 1
            ans[i] = m
        return min(0, *ans), ans[-1]

    # 数値化(最小値, 到達値)
    T = [f(s) for s in S]

    # 最小値が0を下回らないようにしたい。
    # 最小値が大きい順、到達値が大きい順に選ぶ
    T.sort(reverse=True)
    print(T)
    m = 0
    for tm, tr in T:
        if m + tm < 0:
            no()
            return
        m += tr
    if m == 0:
        yes()
    else:
        no()

    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:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
INF = float("inf")


def yes():
    print("Yes")  # type: str


def no():
    print("No")  # type: str


def solve(N: int, S: "List[str]"):

    def f(s):
        ans = [0]*len(s)
        m = 0
        for i, c in enumerate(s):
            if c == "(":
                m += 1
            else:
                m -= 1
            ans[i] = m
        return min(INF, *ans), ans[-1]

    # 数値化(最小値, 到達値)
    T = [f(s) for s in S]

    # 最小値が0を下回らないようにしたい。
    # 最小値が大きい順、到達値が大きい順に選ぶ
    T.sort(reverse=True)
    m = 0
    for tm, tr in T:
        if m + tm < 0:
            no()
            return
        m += tr
    if m == 0:
        yes()
    else:
        no()

    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:
n=int(input())
s=[input() for i in range(n)]
li=[]
res=0
for i in range(n):
    lr=0
    min_=0
    for c in s[i]:
        if c=='(':
            lr+=1
        else:
            lr-=1
        min_=min(min_,lr)
    li.append([s[i],lr,min_])
    res+=lr
if res!=0:
    print('No')
    exit()
li.sort(key=lambda x:(x[1],x[2]),reverse=True)
cum=0
for i in range(n):
    if cum+li[i][2]<0:
        print('No')
        exit()
    cum+=li[i][1]
    if cum<0:
        print('No')
        exit()
if cum!=0:
    print('No')
else:
    print('Yes')

Submission status: Wrong Answer

Solution code:
N = int(input())

tleft = 0
tright = 0
a = []
b=  []
for _ in range(N):
  s = input()
  left = 0
  lmin = 0
  for c in s:
    if c == "(":
      left += 1
    else: # ")"
      left -= 1
      lmin = min(lmin,left)
  #
  if left >= 0:
    if lmin == 0:
      tleft += left
    else:
      a.append([left,lmin])
  else:
    if left < lmin:
      tright += left
    else:
      b.append([left,lmin])
#
a.sort(key=lambda x:-x[1])
b.sort(key=lambda x:-min(x[0],x[1]))

for left, lmin in a:
  if tleft + lmin < 0:
    print("No")
    exit(0)
  else:
    tleft += left
#
for left, lmin in b:
  if tleft + lmin < 0:
    print("No")
    exit(0)
  else:
    tleft += left
#
if tleft + tright == 0:
  print("Yes")
else:
  print("No")
#

Submission status: Wrong Answer

Solution code:
N = int(input())

tleft = 0
tright = 0
a = []
b=  []
for _ in range(N):
  s = input()
  left = 0
  lmin = 0
  for c in s:
    if c == "(":
      left += 1
    else: # ")"
      left -= 1
      lmin = min(lmin,left)
  #
  if left >= 0:
    if lmin == 0:
      tleft += left
    else:
      a.append([left,lmin])
  else:
    if left < lmin:
      tright += left
    else:
      b.append([left,lmin])
#
a.sort(key=lambda x:-x[1])
b.sort(key=lambda x:x[0]-x[1])
#print(tleft)
#print(a)
#print(tright)

for left, lmin in a:
  if tleft + lmin < 0:
    print("No")
    exit(0)
  else:
    tleft += left
#
for left, lmin in b:
  if tleft + lmin < 0:
    print("No")
    exit(0)
  else:
    tleft += left
#
if tleft + tright == 0:
  print("Yes")
else:
  print("No")
#

Submission status: Wrong Answer

Solution code:
N = int(input())

tleft = 0
tright = 0
a = []
b=  []
for _ in range(N):
  s = input()
  left = 0
  lmin = 0
  for c in s:
    if c == "(":
      left += 1
    else: # ")"
      left -= 1
      lmin = min(lmin,left)
  #
  if left >= 0:
    if lmin == 0:
      tleft += left
    else:
      a.append([left,lmin])
  else:
    if left < lmin:
      tright += left
    else:
      b.append([left,lmin])
#
a.sort(key=lambda x:-x[1])
b.sort(key=lambda x:-x[1])
#print(tleft)
#print(a)
#print(tright)

for left, lmin in a:
  if tleft + lmin < 0:
    print("No")
    exit(0)
  else:
    tleft += left
#
for left, lmin in b:
  if tleft + lmin < 0:
    print("No")
    exit(0)
  else:
    tleft += left
#
if tleft + tright == 0:
  print("Yes")
else:
  print("No")
#

Submission status: Wrong Answer

Solution code:
N = int(input())

tleft = 0
tright = 0
a = []

for _ in range(N):
  s = input()
  left = 0
  lmin = 0
  for c in s:
    if c == "(":
      left += 1
    else: # ")"
      left -= 1
      lmin = min(lmin,left)
  #
  if left >= 0 and lmin == 0:
    tleft += left
  elif left < 0 :
    tright += left
  else:
    a.append([left,lmin])
#
a.sort(key=lambda x:x[1])
#print(tleft)
#print(a)
#print(tright)

for left, lmin in a:
  if tleft + lmin < 0:
    print("No")
    break
  else:
    tleft += left
else:
  if tleft + tright == 0:
    print("Yes")
  else:
    print("No")
#

#

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    Ss = [input() for _ in range(n)]
    U = [[0, 0] for _ in range(n)]
    for i in range(n):
        for c in Ss[i]:
            if c == "(":
                U[i][1] += 1
            else:
                if U[i][1] == 0:
                    U[i][0] += 1
                else:
                    U[i][1] -= 1
    L, R = 0, 0
    P = []
    for i in range(n):
        if U[i][0] == 0 and U[i][1] > 0:
            L += U[i][1]
        elif U[i][0] > 0 and U[i][1] == 0:
            R += U[i][0]
        elif U[i][0] > 0 and U[i][1] > 0:
            P.append([U[i][0], U[i][1]])
    P.sort(key=lambda x: (x[0], -x[1]))
    if L == 0 and R == 0 and len(P) == 0:
        print("Yes")
    elif (L == 0 or R == 0) and len(P) > 0:
        print("No")
    else:
        f = True
        for i in range(len(P)):
            L -= P[i][0]
            if L < 0:
                f = False
                break
            L += P[i][1]
        if L == R and f:
            print("Yes")
        else:
            print("No")

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    Ss = [input() for _ in range(n)]
    U = [[0, 0] for _ in range(n)]
    for i in range(n):
        for c in Ss[i]:
            if c == "(":
                U[i][1] += 1
            else:
                if U[i][1] == 0:
                    U[i][0] += 1
                else:
                    U[i][1] -= 1
    L, R = 0, 0
    P = []
    for i in range(n):
        if U[i][0] == 0 and U[i][1] > 0:
            L += U[i][1]
        elif U[i][0] > 0 and U[i][1] == 0:
            R += U[i][0]
        elif U[i][0] > 0 and U[i][1] > 0:
            P.append(U[i][1] - U[i][0])
    P.sort(reverse=True)
    if L == 0 and R == 0 and len(P) == 0:
        print("Yes")
    elif (L == 0 or R == 0) and len(P) > 0:
        print("No")
    else:
        f = True
        for i in range(len(P)):
            L += P[i]
            if L < 0:
                f = False
                break
        if L == R and f:
            print("Yes")
        else:
            print("No")

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    Ss = [input() for _ in range(n)]
    U = [[0, 0] for _ in range(n)]
    for i in range(n):
        for c in Ss[i]:
            if c == "(":
                U[i][1] += 1
            else:
                if U[i][1] == 0:
                    U[i][0] += 1
                else:
                    U[i][1] -= 1
    L, R = 0, 0
    P = []
    for i in range(n):
        if U[i][0] == 0 and U[i][1] > 0:
            L += U[i][1]
        elif U[i][0] > 0 and U[i][1] == 0:
            R += U[i][0]
        elif U[i][0] > 0 and U[i][1] > 0:
            P.append(U[i][1] - U[i][0])
    P.sort(reverse=True)
    if L == 0 and R == 0 and len(P) == 0:
        print("Yes")
    elif (L == 0 or R == 0) and len(P) > 0:
        print("No")
    else:
        f = True
        for i in range(len(P)):
            L += P[i]
            if L < 0:
                f = False
                break
        if L == R:
            print("Yes")
        else:
            print("No")

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def determine_string_code(bracket_string):
  brackets_left = 0 # )
  brackets_right = 0 # (
  for char in bracket_string:
    if char == "(":
      brackets_right += 1
    else:
      if brackets_right > 0:
        brackets_right -= 1
      else:
        brackets_left += 1
  return (brackets_left, brackets_right)

def build_res(in_list, half_ind):
  in_list.sort(key=lambda x: x[half_ind])
  final_res = (0, 0)
  for res in in_list:
    if res[0]>final_res[1]:
      final_res = (final_res[0]+res[0]-final_res[1], res[1])
    elif res[0]<final_res[1]:
      final_res = (final_res[0], res[1]+final_res[1]-res[0])
    else:
      final_res = (final_res[0], res[1])
  return final_res

n = int(input())
residues = list()
for _ in range(n):
  new_string = input()
  residues.append(determine_string_code(new_string))
first_half = list()
second_half = list()
for res in residues:
  if res[1] > res[0]:
    first_half.append(res)
  else:
    second_half.append(res)
first_res = build_res(first_half, 0)
second_res = build_res(second_half, 1)
if first_res[0] == 0 and second_res[1] == 0 and first_res[1] == second_res[0]:
  print("Yes")
else:
  print("No")

Submission status: Wrong Answer

Solution code:
def determine_string_code(bracket_string):
  brackets_right = 0 # (
  brackets_left = 0 # )
  for char in bracket_string:
    if char == "(":
      brackets_right += 1
    else:
      if brackets_right > 0:
        brackets_right -= 1
      else:
        brackets_left += 1
  return (brackets_left, brackets_right)

def build_res(in_list):
  in_list.sort(key=lambda x: x[0])
  final_res = (0, 0)
  for res in in_list:
    if res[0]>final_res[1]:
      final_res = (final_res[0]+res[0]-final_res[1], res[1])
    elif res[0]<final_res[1]:
      final_res = (final_res[0], res[1]+final_res[1]-res[0])
    else:
      final_res = (final_res[0], res[1])
  return final_res

def check_possible():
  first_half = list()
  second_half = list()
  for res in residues:
    if res[1] > res[0]:
      first_half.append(res)
    elif res[0] >= res[1]:
      second_half.append(res)
  first_res = build_res(first_half)
  second_res = build_res(second_half)
  if first_res[0] == 0 and second_res[1] == 0 and first_res[1] == second_res[0]:
    return "Yes"
  return "No"

n = int(input())
residues = list()
for _ in range(n):
  new_string = input()
  residues.append(determine_string_code(new_string))
print(check_possible())

Submission status: Wrong Answer

Solution code:
def determine_string_code(bracket_string):
  brackets_right = 0 # (
  brackets_left = 0 # )
  for char in bracket_string:
    if char == "(":
      brackets_right += 1
    else:
      if brackets_right > 0:
        brackets_right -= 1
      else:
        brackets_left += 1
  return (brackets_left, brackets_right)

def build_res(in_list):
  in_list.sort(key=lambda x: x[0])
  final_res = (0, 0)
  for res in in_list:
    if res[0]>final_res[1]:
      final_res = (final_res[0]+res[0]-final_res[1], res[1])
    elif res[0]<final_res[1]:
      final_res = (final_res[0], res[1]+final_res[1]-res[0])
    else:
      final_res = (final_res[0], res[1])
  return final_res

def check_possible():
  first_half = list()
  second_half = list()
  for res in residues:
    if res[1] > res[0]:
      first_half.append(res)
    elif res[0] > res[1]:
      second_half.append(res)
  first_res = build_res(first_half)
  second_res = build_res(second_half)
  if first_res[0] == 0 and second_res[1] == 0 and first_res[1] == second_res[0]:
    return "Yes"
  return "No"

n = int(input())
residues = list()
for _ in range(n):
  new_string = input()
  residues.append(determine_string_code(new_string))
print(check_possible())

Submission status: Wrong Answer

Solution code:
def determine_string_code(bracket_string):
  brackets_right = 0 # )
  brackets_left = 0 # (
  for char in bracket_string:
    if char == "(":
      brackets_right += 1
    else:
      if brackets_right > 0:
        brackets_right -= 1
      else:
        brackets_left += 1
  return (brackets_left, brackets_right)

def check_possible():
  if len(residues) == 1:
    if residues[0][0] == residues[0][1] == 0:
      return "Yes"
    else:
      return "No"
  check_left = False
  check_right = False
  for res in residues:
    if res[1] == 0:
      check_right = True
    elif res[0] == 0:
      check_left = True
  if (not check_left) or (not check_right):
    return "No"
  right_facing = sum(res[0] for res in residues)
  left_facing = sum(res[1] for res in residues)
  if right_facing == left_facing:
    return "Yes"
  return "No"

n = int(input())
residues = list()
for _ in range(n):
  new_string = input()
  residues.append(determine_string_code(new_string))
print(check_possible())