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:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


def I(): return int(input())


def S(): return input()


def MI(): return map(int, input().split())


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


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


yn = {False: 'No', True: 'Yes'}
YN = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**19
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']

show_flg = False
# show_flg = True


def main():
    N = I()
    zeros = []
    incs = []
    decs = []
    s = [None] * N

    for i in range(N):
        s[i] = S()
        cur = 0
        mn = 0
        for c in s[i]:
            if c == '(':
                cur += 1
            else:
                cur -= 1
            mn = min(mn, cur)
        end = cur

        if end == 0:
            zeros.append((mn, end, i))
        elif end > 0:
            incs.append((mn, end, i))
            # heappush(incs, (-mn, end))
        else:
            decs.append((mn, end, i))
            # heappush(decs, (mn, end))

    incs.sort(reverse=True)
    decs.sort()

    ans = []
    for mn, end, idx in incs:
        ans.append(s[idx])

    for mn, end, idx in zeros:
        ans.append(s[idx])

    for mn, end, idx in decs:
        ans.append(s[idx])

    now = 0
    for i in range(len(ans)):
        for c in ans[i]:
            if c == '(':
                now += 1
            else:
                now -= 1
            if now < 0:
                print("No")
                return

    print(yn[now == 0])

    # now = 0
    # for mn, end, idx in incs:
    #     if now + mn < 0:
    #         print('No')
    #         return
    #     now += end

    # for mn, end, idx in zeros:
    #     if now + mn < 0:
    #         print('No')
    #         return
    #     now += end

    # for mn, end, idx in decs:
    #     if now + mn < 0:
    #         print('No')
    #         return
    #     now += end

    # print(yn[now == 0])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

M = 0
left, rev_l, rev_r, right = 0, 0, 0, 0
for S in S_list:
    stack = []
    l, r = 0, 0
    for s in S:
        if s == '(':
            if stack and stack[-1] == ')':
                stack.append('(')
                l = 1
            else:
                stack.append('(')
                l += 1
        else:   # s==')'
            if stack and stack[-1] == '(':
                stack.pop()
                l -= 1
            else:
                stack.append(')')
                r += 1
    if l == 0:
        right += r
    elif r == 0:
        left += l
    else:
        rev_r += r
        rev_l += l
        M = max(M, min(rev_r, rev_l))
    # print('{} l:{} r:{} left:{} rev_l:{} rev_r:{} right:{}'.format(
        # S, l, r, left, rev_l, rev_r, right))

if left+rev_l == rev_r+right and left >= 1 and right >= 1:
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

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


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

    grads_positive = list()
    grads_even = list()
    grads_negative = list()

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

        current_p = 0
        lowest_p = 0

        for s in S:
            if s == '(':
                current_p += 1
            elif s == ')':
                current_p -= 1
                lowest_p = min(lowest_p, current_p)

        if current_p > 0:
            grads_positive.append((lowest_p, current_p))
        elif current_p == 0:
            grads_even.append(lowest_p)
        elif current_p < 0:
            grads_negative.append((lowest_p, current_p))

    grads_positive.sort(reverse=True)
    # grads_negative.sort()

    current_p = 0
    for grad in grads_positive + grads_negative:
        lowest_p = current_p + grad[0]
        if lowest_p < 0:
            return False
        current_p += grad[1]

    if current_p == 0:
        return True
    else:
        return False


def main():
    ok = solve()
    if ok:
        print('Yes')
    else:
        print('No')


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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


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

    grads_positive = list()
    grads_even = list()
    grads_negative = list()

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

        current_p = 0
        lowest_p = 0

        for s in S:
            if s == '(':
                current_p += 1
            elif s == ')':
                current_p -= 1
                lowest_p = min(lowest_p, current_p)

        if current_p > 0:
            grads_positive.append((lowest_p, current_p))
        elif current_p == 0:
            grads_even.append(lowest_p)
        elif current_p < 0:
            grads_negative.append((lowest_p, current_p))

    grads_positive.sort()
    # grads_negative.sort()
    
    current_p = 0
    for grad in grads_positive + grads_negative:
        lowest_p = current_p + grad[0]
        if lowest_p < 0:
            return False
        current_p += grad[1]

    if current_p == 0:
        return True
    else:
        return False


def main():
    ok = solve()
    if ok:
        print('Yes')
    else:
        print('No')


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


def I(): return int(input())


def S(): return input()


def MI(): return map(int, input().split())


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


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


yn = {False: 'No', True: 'Yes'}
YN = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**19
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']

show_flg = False
# show_flg = True


def main():
    N = I()
    zeros = []
    incs = []
    decs = []

    for i in range(N):
        s = S()
        cur = 0
        mn = 0
        for c in s:
            if c == '(':
                cur += 1
            else:
                cur -= 1
            mn = min(mn, cur)
        end = cur

        if end == 0:
            zeros.append((mn, end))
        elif end > 0:
            incs.append((mn, end))
            # heappush(incs, (-mn, end))
        else:
            decs.append((mn, end))
            # heappush(decs, (mn, end))

    incs.sort(reverse=True)
    decs.sort()

    now = 0
    for mn, end in incs:
        if now + mn < 0:
            print('No')
            return
        now += end

    for mn, end in zeros:
        if now + mn < 0:
            print('No')
            return
        now += end

    for mn, end in decs:
        if now + mn < 0:
            print('No')
            return
        now += end

    print(yn[now == 0])
    # print(incs, zeros, decs)
    # now = 0
    # while len(incs) != 0:
    #     mn, end = heappop(incs)
    #     if now + (-mn) < 0:
    #         print('No')
    #         return
    #     now += end

    # # print(now)
    # while len(zeros) != 0:
    #     mn, end = heappop(zeros)
    #     if now + mn < 0:
    #         print('No')
    #         return

    # # print(now)
    # while len(decs) != 0:
    #     mn, end = heappop(decs)
    #     # print(now, end)
    #     if now + mn < 0:
    #         print('No')
    #         return
    #     now += end

    # print(now)
    # print(yn[now == 0])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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


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

    grads_positive = list()
    grads_even = list()
    grads_negative = list()

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

        current_p = 0
        lowest_p = 0

        for s in S:
            if s == '(':
                current_p += 1
            elif s == ')':
                current_p -= 1
                lowest_p = min(lowest_p, current_p)

        if current_p > 0:
            grads_positive.append((lowest_p, current_p))
        elif current_p == 0:
            grads_even.append(lowest_p)
        elif current_p < 0:
            grads_negative.append((lowest_p, current_p))

    grads_positive.sort()

    current_p = 0
    for grad in grads_positive + grads_negative:
        lowest_p = current_p - grad[0]
        if lowest_p < 0:
            return False
        current_p += grad[1]
    
    if current_p == 0:
        return True
    else:
        return False


def main():
    ok = solve()
    if ok:
        print('Yes')
    else:
        print('No')


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
s = [input() for _ in range(n)]

def brace_info(s):
    pp = 0
    nn = 0

    for c in s:
        if c == '(':
            nn += 1
        else:
            if nn > 0:
                nn -= 1
            else:
                pp += 1

    return (nn, pp)

brace_infos = [brace_info(ss) for ss in s]
brace_infos = [b for b in brace_infos if b != (0, 0)]
brace_infos = sorted(brace_infos, key=lambda p: p[1]-p[0])

if len(brace_infos) == 0:
    print('Yes')
else:
    ba = brace_infos[0][0] - brace_infos[0][1]
    solved = False

    for l, r in brace_infos[1:]:
        if r > ba:
            print('No')
            solved = True
            break
        else:
            ba = (l+r-ba)

    if not solved:
        if ba == 0:
            print('Yes')
        else:
            print('No')

Submission status: Wrong Answer

Solution code:
from sys import stdin

def checker(x):
    if not x: return 1
    if x[0] != '(' or x[-1] != ')': return 0

    l = x.count('(', 1, -1)
    r = len(x[1:-1]) - l
    if l != r: return 0

    return 1

def main():
    readline = stdin.readline
    n = int(readline())
    s = tuple(readline().strip() for _ in range(n))

    sorted_s = sorted(s)
    jud = checker(''.join(sorted_s))

    if jud == 1:
        print('Yes')
    else:
        print('No')
    return

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

az = 1
lf = 0
rf = 0
lst = []
rlt = 0
r = 0
l = 0

for s in Ss:
  scr = 0
  rt = 0
  lt = 0
  for i in range(len(s)):
    if s[i] == '(':
      if scr < 0:
        rt -= scr
        scr = 0
      scr += 1
    else:
      scr -= 1
  if scr > 0:
    lt += scr
  elif scr < 0:
    rt -= scr
  rlt += lt - rt
  lst.append((rt,lt))
  
  if lt == 0 and rt > 0:
    rf = 1
    az = 0 
  elif rt == 0 and lt > 0:
    lf = 1
    az = 0
  elif rt > 0 and lt > 0:
    az = 0
    
lst.sort()

if not rlt == 0:
  print('No')
else:
  for t in lst:
    r += t[0]
    l += t[1]
    if r > l:
      print('No')
      break
  print('Yes')

Submission status: Wrong Answer

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

M = 0
left, rev_l, rev_r, right = 0, 0, 0, 0
for S in S_list:
    stack = []
    l, r = 0, 0
    for s in S:
        if s == '(':
            if stack and stack[-1] == ')':
                stack.append('(')
                l = 1
            else:
                stack.append('(')
                l += 1
        else:   # s==')'
            if stack and stack[-1] == '(':
                stack.pop()
                l -= 1
            else:
                stack.append(')')
                r += 1
    if l == 0:
        right += r
    elif r == 0:
        left += l
    else:
        rev_r += r
        rev_l += l
        M = max(M, min(rev_r, rev_l))
    # print('{} l:{} r:{} left:{} rev_l:{} rev_r:{} right:{}'.format(
        # S, l, r, left, rev_l, rev_r, right))

if left+rev_l == rev_r+right and M <= sum((left, rev_l, rev_r, right))//2:
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

Solution code:

import sys

pos, neg = [], []
n = int(input())
for i in range(n):
    s = input()
    bal = 0
    min_bal = 0
    for c in s:
        bal += 1 if c == '(' else -1
        min_bal = min(bal, min_bal)

    if bal >= 0:
        pos.append((-min_bal, bal))
    else:
        neg.append((max(-min_bal, -bal), bal))

pos.sort(reverse=True) 
neg.sort(reverse=True, key = lambda p: p[0]+p[1])

cur = 0
for m, e in pos:
    if cur < m:
        print("No")
        sys.exit()

    cur += e

for m, e in neg:
    if cur < m:
        print("No")
        sys.exit()

    cur += e

print("Yes" if cur == 0 else "No")

Submission status: Wrong Answer

Solution code:
from functools import cmp_to_key
n = int(input())
s = [input() for _ in range(n)]

def brace_info(s):
    pp = 0
    nn = 0

    for c in s:
        if c == '(':
            nn += 1
        else:
            if nn > 0:
                nn -= 1
            else:
                pp += 1

    return (nn, pp)

brace_infos = [brace_info(ss) for ss in s]
brace_infos = [b for b in brace_infos if b != (0, 0)]
brace_infos = sorted(brace_infos, key=lambda p: p[1]-p[0])

if len(brace_infos) == 0:
    print('Yes')
else:
    ba = 0
    solved = False

    for l, r in brace_infos:
        if r > ba:
            print('No')
            solved = True
            break
        else:
            ba = (l+r-ba)

    if not solved:
        if ba == 0:
            print('Yes')
        else:
            print('No')

Submission status: Wrong Answer

Solution code:
import sys

pos, neg = [], []
n = int(input())
for i in range(n):
    s = input()
    bal = 0
    min_bal = 0
    for c in s:
        bal += 1 if c == '(' else -1
        min_bal = min(bal, min_bal)

    if bal >= 0:
        pos.append((min_bal, bal))
    else:
        neg.append((min(min_bal, bal), bal))

pos.sort(reverse=True) 
neg.sort(reverse=True, key = lambda p: p[0]+p[1])

cur = 0
for m, e in pos:
    if cur + m < 0:
        print("No")
        sys.exit()

    cur += e

for m, e in neg:
    if cur + m < 0:
        print("No")
        sys.exit()

    cur += e

print("Yes" if cur == 0 else "No")

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


def I(): return int(input())


def S(): return input()


def MI(): return map(int, input().split())


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


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


yn = {False: 'No', True: 'Yes'}
YN = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**19
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']

show_flg = False
# show_flg = True


def main():
    N = I()
    zeros = []
    incs = []
    decs = []

    for i in range(N):
        s = S()
        cur = 0
        mn = 0
        for c in s:
            if c == '(':
                cur += 1
            else:
                cur -= 1
            mn = min(mn, cur)
        end = cur

        if end == 0:
            zeros.append((mn, end))
        elif end > 0:
            heappush(incs, (-mn, end))
        else:
            heappush(decs, (mn, end))

    # print(incs, zeros, decs)
    now = 0
    while len(incs) != 0:
        mn, end = heappop(incs)
        if now + (-mn) < 0:
            print('No')
            return
        now += end

    # print(now)
    while len(zeros) != 0:
        mn, end = heappop(zeros)
        if now + mn < 0:
            print('No')
            return

    # print(now)
    while len(decs) != 0:
        mn, end = heappop(decs)
        # print(now, end)
        if now + mn < 0:
            print('No')
            return
        now += end

    # print(now)
    print(yn[now == 0])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

pos, neg = [], []
n = int(input())
for i in range(n):
    s = input()
    bal = 0
    min_bal = 0
    for c in s:
        bal += 1 if c == '(' else -1
        min_bal = min(bal, min_bal)

    if bal >= 0:
        pos.append((min_bal, bal))
    else:
        neg.append((min(min_bal, -bal), bal))

pos.sort(reverse=True) 
neg.sort(reverse=True, key = lambda p: p[0]+p[1])

cur = 0
for m, e in pos:
    if cur + m < 0:
        print("No")
        sys.exit()

    cur += e

for m, e in neg:
    if cur + m < 0:
        print("No")
        sys.exit()

    cur += e

print("Yes" if cur == 0 else "No")

Submission status: Wrong Answer

Solution code:
import sys

pos, neg = [], []
n = int(input())
for i in range(n):
    s = input()
    bal = 0
    min_bal = 0
    for c in s:
        bal += 1 if c == '(' else -1
        min_bal = min(bal, min_bal)

    if bal >= 0:
        pos.append((min_bal, bal))
    else:
        neg.append((min_bal, bal))

pos.sort(reverse=True) 
neg.sort(reverse=True, key = lambda p: p[0]+p[1])

cur = 0
for m, e in pos:
    if cur + m < 0:
        print("No")
        sys.exit()

    cur += e

for m, e in neg:
    if cur + m < 0:
        print("No")
        sys.exit()

    cur += e

print("Yes" if cur == 0 else "No")

Submission status: Wrong Answer

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

left, rev_l, rev_r, right = 0, 0, 0, 0
for S in S_list:
    stack = []
    l, r = 0, 0
    for s in S:
        if s == '(':
            if stack and stack[-1] == ')':
                stack.append('(')
                l = 1
            else:
                stack.append('(')
                l += 1
        else:   # s==')'
            if stack and stack[-1] == '(':
                stack.pop()
                l -= 1
            else:
                stack.append(')')
                r += 1
    if l == 0:
        right += r
    elif r == 0:
        left += l
    else:
        rev_r += r
        rev_l += l
    # print(S, l, r, left, rev_l, rev_r, right)

if left >= rev_r and rev_l <= right and left+rev_l == rev_r+right:
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

Solution code:
import sys

pos, neg = [], []
n = int(input())
for i in range(n):
    s = input()
    bal = 0
    min_bal = 0
    for c in s:
        bal += 1 if c == '(' else -1
        min_bal = min(bal, min_bal)

    if bal >= 0:
        pos.append((min_bal, bal))
    else:
        neg.append((max(min_bal, -bal), bal))

pos.sort(reverse=True) 
neg.sort(reverse=True, key = lambda p: p[0]+p[1])

cur = 0
for m, e in pos:
    if cur + m < 0:
        print("No")
        sys.exit()

    cur += e

for m, e in neg:
    if cur + m < 0:
        print("No")
        sys.exit()

    cur += e

print("Yes" if cur == 0 else "No")

Submission status: Wrong Answer

Solution code:
from functools import cmp_to_key
from collections import Counter
n = int(input())
s = [input() for _ in range(n)]

def brace_info(s):
    cnt = Counter(s)
    return cnt['('], cnt[')']
    # pp = 0
    # nn = 0

    # for c in s:
    #     if c == '(':
    #         nn += 1
    #     else:
    #         if nn > 0:
    #             nn -= 1
    #         else:
    #             pp += 1

    # return (nn, pp)

brace_infos = [brace_info(ss) for ss in s]
brace_infos = [b for b in brace_infos if b != (0, 0)]
brace_infos = sorted(brace_infos, key=lambda p: p[1]-p[0])
ba = 0

solved = False

for l, r in brace_infos:
    if r > ba:
        print('No')
        solved = True
        break
    else:
        ba = (l+r-ba)

if not solved:
    if ba == 0:
        print('Yes')
    else:
        print('No')

Submission status: Wrong Answer

Solution code:
N = int(input())
s = []
for i in range(N):
    s.append(input())
inc = []
dec = []
for i in s:
    cn = 0
    mn = 0
    for j in i:
        if j=="(":
            cn+=1
        else:
            cn-=1
        mn = min(cn,mn)
    if cn>=0:
        inc.append([mn,cn])
    else:
        dec.append([mn-cn,-cn])

print(inc,dec)

Submission status: Wrong Answer

Solution code:
import sys
from operator import itemgetter

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N = INT()
A = []
cur = 0
for i in range(N):
    S = input()
    tmp = []
    for s in S:
        if s == '(':
            tmp.append(s)
        else:
            if tmp and tmp[-1] == '(':
                tmp.pop()
            else:
                tmp.append(s)
    l = tmp.count('(')
    r = len(tmp) - l
    A.append((l, r))
A.sort(key=itemgetter(1))

for l, r in A:
    cur += r
    if cur > 0:
        No()
        exit()
    cur -= l
if cur == 0:
    Yes()
else:
    No()

Submission status: Wrong Answer

Solution code:
from functools import cmp_to_key
n = int(input())
s = [input() for _ in range(n)]

def brace_info(s):
    pp = 0
    nn = 0

    for c in s:
        if c == '(':
            nn += 1
        else:
            if nn > 0:
                nn -= 1
            else:
                pp += 1

    return (nn, pp)

brace_infos = [brace_info(ss) for ss in s]
brace_infos = [b for b in brace_infos if b != (0, 0)]
brace_infos = sorted(brace_infos, key=lambda p: p[1]-p[0])
ba = 0

solved = False

for l, r in brace_infos:
    if r > ba:
        print('No')
        solved = True
        break
    else:
        ba = (l+r-ba)

if not solved:
    if ba == 0:
        print('Yes')
    else:
        print('No')

Submission status: Wrong Answer

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

r = 0
l = 0
rf = 0
lf = 0
az = 1

for s in Ss:
  scr = 0
  rt = 0
  lt = 0
  for i in range(len(s)):
    if s[i] == '(':
      if scr < 0:
        rt -= scr
        scr = 0
      scr += 1
    else:
      scr -= 1
  if scr > 0:
    lt += scr
  elif scr < 0:
    rt -= scr
  if lt == 0 and rt > 0:
    rf = 1
    az = 0
    r += rt 
  elif rt == 0 and lt > 0:
    lf = 1
    az = 0
    l += lt
  elif rt > 0 and lt > 0:
    az = 0
    r += rt
    l += lt
    
if (l == r and rf == 1 and lf == 1) or az == 1:
  print('Yes')
else:
  print('No')

Submission status: Wrong Answer

Solution code:
import sys
from operator import itemgetter

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N = INT()
A = []
cur = 0
for i in range(N):
    S = input()
    tmp = []
    for s in S:
        if s == '(':
            tmp.append(s)
        else:
            if tmp and tmp[-1] == '(':
                tmp.pop()
            else:
                tmp.append(s)
    l = tmp.count('(')
    r = len(tmp) - l
    if r == 0:
        cur -= l
    else:
        A.append((r-l, l, r))
A.sort(key=itemgetter(0))

for _, l, r in A:
    cur += r
    if cur > 0:
        No()
        exit()
    cur -= l
if cur == 0:
    Yes()
else:
    No()

Submission status: Wrong Answer

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

r = 0
l = 0
rf = 0
lf = 0
az = 1

for s in Ss:
  scr = 0
  rt = 0
  lt = 0
  for i in range(len(s)):
    if s[i] == '(':
      if scr < 0:
        rt -= scr
        scr = 0
      scr += 1
    else:
      scr -= 1
  if scr > 0:
    lt += scr
  elif scr < 0:
    rt -= scr
  if lt == 0 and rt > 0:
    rf = 1
    az = 0
  elif rt == 0 and lt > 0:
    lf = 1
    az = 0
  elif rt > 0 and lt > 0:
    az = 0
if (l == r and rf == 1 and lf == 1) or az == 1:
  print('Yes')
else:
  print('No')

Submission status: Wrong Answer

Solution code:
import sys
from operator import itemgetter

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N = INT()
A = []
for i in range(N):
    S = input()
    tmp = []
    for s in S:
        if s == '(':
            tmp.append(s)
        else:
            if tmp and tmp[-1] == '(':
                tmp.pop()
            else:
                tmp.append(s)
    l = tmp.count('(')
    r = len(tmp) - l
    A.append((r-l, l, r))
A.sort(key=itemgetter(0))

cur = 0
for _, l, r in A:
    cur += r
    if cur > 0:
        No()
        exit()
    cur -= l
if cur == 0:
    Yes()
else:
    No()

Submission status: Wrong Answer

Solution code:
n=int(input())
A=[]
B=[]
c=0
for i in range(n):
  S=input()
  a=0
  b=0
  for j in range(len(S)):
    if S[j]=="(":
      a=a+1
    else:
      a=a-1
      if a<b:
        b=a
  b=b*-1
  if b==0:
    c=c+a
  elif a>=0:
    B.append([b,-1*a])
  else:
    A.append([-1*b,-1*a])
A.sort()
B.sort()
f=0
for i in range(len(B)):
  if c-B[i][0]<0:
    f=1
  c=c-B[i][1]
for i in range(len(A)):
  if c+A[i][0]<0:
    f=1
  c=c-A[i][1]
if c!=0:
  f=1
if f==0:
  print("Yes")
else:
  print("No")

Submission status: Wrong Answer

Solution code:
n = int(input())
l = 0
r = 0
cntl = 0
cntr = 0
fl = 0
fr = 0
exl = 0
exr = 0
only_r = 0
only_l = 0
maxl = 0
maxr = 0
exlr = []
for i in range(n):
    s = input()
    templ = 0
    tempr = 0
    temp_exl = 0
    temp_exr = 0
    fl = 0
    fr = 0
    for i in s:
        if i == "(":
            tempr += 1
        elif i == ")":
            tempr -= 1
            if tempr < 0:
                tempr = 0
                templ += 1
                fl = 1
    temp_exl += templ
    if tempr > 0:
        temp_exr += tempr
        fr = 1
    if fl == 1 and fr == 0:
        only_l += temp_exl
    elif fr == 1 and fl == 0:
        only_r += temp_exr
    elif temp_exl + temp_exr > 0:
        exl += temp_exl
        exr += temp_exr
        exlr.append([temp_exl-temp_exr, temp_exl,temp_exr])
    # maxl = max(maxl,temp_exl)
    # maxr = max(maxr,temp_exr)
# print (exr,exl,only_r,only_l)
a = only_r
b = only_l
# print(exlr)
exlr.sort()
exlr.sort(key=lambda x: x[1])

# print(exlr)
# for i in range(len(exlr)):
#     if exlr[i][1] <= a and exlr[i][0] <= 0:
#         a -= exlr[i][0]
#         exlr[i] = [0,0,0]
# print(exlr)
for i in exlr:
    a -= i[1]
    if a<0:
        print("No")
        exit()
    a += i[2]
if a-b == 0:
    print("Yes")
else:
    print("No")
# if exl+only_l == exr+only_r and exl-exr == only_r-only_l and only_l > 0 and only_r > 0:
#     print("Yes")
# elif exr+exl+only_l+only_r == 0:
#     print("Yes")
# else:
#     print("No")

Submission status: Wrong Answer

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

LP = 0
RP = 0
X = []
for i in range(N):
    L = LR[i][0]
    R = LR[i][1]
    if (L==0)and(R==0):
        continue
    elif L==0:
        RP += R
    elif R==0:
        LP += L
    else:
        X.append([L,R,L-R])

X.sort(key=lambda x:x[2],reverse=True)

Life = LP
if Life==0:
    if (RP==0)and(len(X)==0):
        print("Yes")
    else:
        print("No")
else:
    flag = 1
    for i in range(len(X)):
        Life += -1*X[i][1]
        if (Life<0)and(X[i][0]-X[i][1]<=0):
            flag=0
        Life += X[i][0]
    if flag==0:
        print("No")
    elif Life==RP:
        print("Yes")
    else:
        print("No")

Submission status: Wrong Answer

Solution code:
N = int(input())
from collections import deque
L = deque([])
R = deque([])

for i in range(N):
  S = input()
  l = [0]*len(S)
  if S[0]=='(':
    l[0]=1
  else:
    l[0]=-1
  for j in range(1,len(S)):
    if S[j]=='(':
      l[j] = l[j-1] + 1
    else:
      l[j] = l[j-1] - 1
  if l[-1] < 0:
    R.append([min(l)-l[-1], -l[-1], min(0,min(l)), l[-1]])
  else:
    L.append([min(0,min(l)),l[-1]])
    
R = sorted(R, key = lambda x:x[0], reverse = True)
L = sorted(L, key = lambda x:x[0])
now = 0
judge = True
    
for l in L:
  if now + l[0]<0:
    judge = False
    break
  else:
    now += l[1]
    
for r in R:
  if now+r[2]<0:
    judge = False
    break
  else:
    now += r[3]
    
if now!=0:
  judge = False
  
if judge:
  print('Yes')
else:
  print('No')