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:
import sys
from operator import itemgetter

def solve():
    input = sys.stdin.readline
    N = int(input())
    Left = []
    lB = None
    rB = None
    for _ in range(N):
        S = input().strip("\n")
        M = len(S)
        aL, aR = 0, 0
        #自身より左にある"("
        r = 0
        for i in range(M):
            if S[i] == ")":
                if r == 0: aL += 1
                else: r -= 1
            else: r += 1
        aR = r
        if lB == None and aL == 0: lB = (aL, aR)
        elif rB == None and aR == 0: rB = (aL, aR)
        else: Left.append((aL, aR))
    Left.sort(key = itemgetter(1), reverse = True)
    Left.sort(key = itemgetter(0))
    
    #print(Left)
    rightOver = 0
    if lB != None: rightOver += lB[1]
    for i in range(len(Left)):
        rightOver -= Left[i][0]
        if rightOver < 0:
            print("No")
            break
        rightOver += Left[i][1]
    else:
        if rB != None:
            rightOver -= rB[0]
            if rightOver != 0: print("No")
            else: print("Yes")
        else:
            if rightOver == 0: print("Yes")
            else: print("No")

    return  0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
def task(n, s):
    deltas = []

    for ss in s:
        localleft = 0
        localright = 0

        for c in ss:
            if c == '(':
                localleft += 1
            elif c == ')':
                if localleft > 0:
                    localleft -= 1
                else:
                    localright += 1

        if localleft > 0 or localright > 0:
            deltas.append([localleft, localright])

    deltas = sorted(deltas, key=lambda x: (x[1], -x[0]))
    total = 0

    for delta in deltas:
        total -= delta[1]

        if total < 0:
            print("No")
            return

        total += delta[0]

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


n = int(input())
s = []
for i in range(0, n):
    s.append(input())
task(n, s)

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

N = I()
S = []
for i in range(N):
    S.append(list(input()))

# ')' - '('
num = [0]*N
for i in range(N):
    val = 0
    temp = [0]*len(S[i])
    for j in range(len(S[i])):
        if S[i][j] == ')':
            temp[j] = temp[j-1]+1
        else:
            temp[j] = temp[j-1]-1

    num[i] = max(temp)

soukei = [0]*N
for i in range(N):
    temp = 0
    for j in range(len(S[i])):
        if S[i][j] == '(':
            temp += 1
        else:
            temp -= 1
    soukei[i] = temp

if sum(soukei) != 0:
    print('No')
    exit()

A = []
for i in range(N):
    A.append((num[i],soukei[i]))


A.sort(key=lambda x:(x[0],-x[1]))

s = 0
for i in range(N):
    if s < A[i][0]:
        print('No')
        exit()
    else:
        s += A[i][1]
    
print('Yes')

Submission status: Wrong Answer

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

s = [0]*N
for i, x in enumerate(S):
    s[i] = len(x) - x.count(')') * 2

if sum(s) == 0:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
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)
    L = 0
    R = 0
    R0 = 0
    t = 0
    if S[0]==")":
        while t<M:
            if S[t]==")":
                R0+=1
                t+=1
            else:
                t+=1
                break
    while t<M:
        if S[t]=="(":
            t+=1
            L+=1
        else:
            t+=1
            R+=1
    if L>R:
        LR[i][0]=L-R
        LR[i][1]=R0
    if L<R:
        LR[i][0]=0
        LR[i][1]=R0+R-L
    if L==R:
        LR[i][0]=0
        LR[i][1]=R0

LP = 0
RP = 0
minLS = float('inf')
minRS = float('inf')
LS = 0
RS = 0
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:
        LS += L
        RS += R
        if LS < minLS:
            minLS = LS
        if RS < minRS:
            minRS = RS

if (minLS<RP)and(minRS<LP):
    print("Yes")
elif (LP==RP)and(LS==0)and(RS==0):
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

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

N0 = 2 ** (n - 1).bit_length()
data = [float('inf')] * (2 * N0)

def update(k, x):
    k += N0 - 1
    data[k] = x
    while k >= 0:
        k = (k - 1) // 2
        data[k] = min(data[2 * k + 1], data[2 * k + 2])
def query(l, r):
    L = l + N0
    R = r + N0
    s = float('inf')
    while L < R:
        if R & 1:
            R -= 1
            s = min(s, data[R - 1])

        if L & 1:
            s = min(s, data[L - 1])
            L += 1
        L >>= 1
        R >>= 1
    return s

dl = []
for i in range(n):
    dd = 0
    dd_min = 0
    for x in s[i]:
        if x == '(':
            dd += 1
        else:
            dd -= 1
        dd_min = min(dd_min, dd)

    dl.append([dd, dd_min])

d = [_dl[0] for _dl in dl]
if sum(d) != 0:
    print('No')
else:
    dl.sort(key=lambda x:x[1]) # sorted by d_min
    d = [_dl[0] for _dl in dl]
    d_min = [_dl[1] for _dl in dl]

    for i in range(len(d)):
        update(i, -d[i])

    from bisect import bisect_left
    f = True
    carry = 0
    for i in range(n):
        # print(carry, d, d_min)
        if d_min[-1] + carry < 0:
            f = False
            break

        idx = bisect_left(d_min, -carry)
        dd = -query(idx, n)
        if dd == -float('inf'):
            f = False
            break

        carry += dd
        update(idx, float('inf'))

    if f:
        print('Yes')
    else:
        print('No')

Submission status: Wrong Answer

Solution code:
n = int(input())
s = [input() for p in range(n)]
print(s)
ohno = False

def lr(st):
    lopen = 0
    ropen = 0
    for c in st:
        if c == "(":
            lopen += 1
        elif c == ")":
            if lopen > 0:
                lopen += -1
            else:
                ropen += 1
    return(lopen,ropen)

o = [lr(q) for q in s]

print(o)
lvalid = []
rvalid = []
rsum = 0
lsum = 0
for w in o:
    lsum += w[0]
    rsum += w[1]
    if w[0] == 0:
        lvalid.append(w)
    if w[1] == 0:
        rvalid.append(w)

if len(lvalid) == 1 and len(rvalid) == 1:
    if lvalid == rvalid:
        print("No")
        ohno = True

if len(lvalid) > 0 and len(rvalid) > 0:
    if lsum == rsum:
        if ohno != True:
            print("Yes")
    else:
        if ohno != True:
            print("No")

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

def l_in():
    return list(map(int, input().split()))

n=n_in()

base=[]

for _ in range(n):
    s = s_in()

    c = s[0]
    cnt = 1
    ar = []
    for t in range(1,len(s)):
        if s[t-1] == s[t]:
            cnt += 1
        else:
            ar.append((c,cnt))
            c = s[t]
            cnt = 1
    ar.append((c,cnt))

    start = 0
    if ar[0][0] == ")":
        start = 1

    r = 0 # ( の数
    sgn = 1
    for c,cnt in ar[start:]:
        r += sgn*cnt
        sgn *= -1


    res = ()
    if ar[0][0] == ")":
        if r >= 0:
            res = (ar[0][1], r)
        else:
            res = (ar[0][1]-r,0)
    else:
        if r >= 0:
            res = (0, r)
        else:
            res = (r, 0)

    base.append(res)

i_cnt = 0
j_cnt = 0

base2 = []

for i,j in base:
    i_cnt += i
    j_cnt += j

    if j > 0:
        base2.append((i,j))

if i_cnt != j_cnt:
    print("No")
    exit()

base2.sort()

current = 0

for i,j in base2:
    if current < i:
        print("No")
        exit()
    current -= i
    current += j

print("Yes")

Submission status: Wrong Answer

Solution code:
import sys
N = int(input())
brackets = []
def change(S):
    left = 0
    right = 0
    cnt = 0
    for i in S:
        if i == '(':
            left += 1
        else:
            if left > 0:
                left -= 1
                cnt += 1
            right += 1
            
    return (right - cnt, -1 * (len(S) - right - cnt))

for _ in range(N):
    brackets.append(change(input()))

brackets.sort()

cnt = 0
for b in brackets:
    cnt -= b[0]
    if cnt < 0:
        print('No')
        sys.exit()
    cnt -= b[1]
if cnt == 0:
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

Solution code:
n = int(input())
a, b = 0, 0
c = 0
cnt = [0, 0]
for _ in range(n):
    s = list(input())
    l = len(s)
    for i in s:
        if i == ")":
            cnt[0] += 1
        else:
            cnt[1] += 1
    if not s[0] == ")":
        m = 0
        x = 0
        for i in range(l):
            if s[i] == "(":
                x += 1
            else:
                x -= 1
            m = max(x, m)
            if x < 0:
                break
        if x > 0:
            a += 1
        if m == l // 2 and x == 0:
            c += 1
    if not s[l - 1] == "(":
        y = 0
        for i in range(l):
            if s[l - i - 1] == ")":
                y += 1
            else:
                y -= 1
            
            if y < 0:
                break
        if y > 0:
            b += 1
print("Yes" if (cnt[0] == cnt[1] and a > 0 and b > 0) or (c == n) else "No")

Submission status: Wrong Answer

Solution code:
n=int(input())
A=[]
for i in range(n):
  x=0
  min=0
  now=input()
  for j in range(len(now)):
    if now[j]=="(":
      x+=1
    else:
      x-=1
      if min>x:
        min-=1
  A.append([x,min])
A=sorted(A, key=lambda func: func[1],reverse=True) 
A=sorted(A, key=lambda func: func[0],reverse=True) 

check=0
OK="Yes"
for i in range(n):
  if check+A[i][1]<0:
    OK="No"
  else:
    check+=A[i][0]
if check!=0:
  OK="No"
print(OK)

Submission status: Wrong Answer

Solution code:
print(-1)

Submission status: Wrong Answer

Solution code:
n = int(input())
sn = [None] * n
for i in range(n):
    sn[i] = input().strip()

def counter(s):
    while '()' in s and s != '':
        s = s.replace('()', '')
    return [s.count(')'), s.count('(')]


check1 = False
check2 = False
results = []
r, l = (0, 0)
for i, s in enumerate(sn):
    pair = counter(s)
    r += pair[0]
    l += pair[1]
    if pair[0] == 0 and pair[1] != 0:
        check1 = True
    if pair[1] == 0 and pair[0] != 0:
        check2 = True

if check1 and check2 and r == l:
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

Solution code:
import sys
n = int(input())
si = []
for _ in range(n):
    s = input()
    l = 0
    r = 0
    count = 0
    for i in range(len(s)):
        if s[i] == "(":
            count += 1
        else:
            count = max(0, count-1)
    l = count
    count = 0
    for i in range(len(s)-1, -1, -1):
        if s[i] == ")":
            count += 1
        else:
            count = max(0, count-1)
    r = count
    si.append((l, r))

if len(si) == 1:
    if si[0] == (0, 0):
        print("Yes")
        sys.exit()

si.sort(key = lambda x: (x[0], -x[1]))
index_l = -1
index_r = -1
maxi_l = 0
maxi_r = 0
for i in range(n):
    a, b = si[i]
    if a == 0:
        if maxi_l < b:
            maxi_l = b
            index_l = i
    if b == 0:
        if maxi_r < a:
            maxi_r = a
            index_r = i

if index_l == -1 or index_r == -1:
    print("No")
    sys.exit()

count = 0
if index_r < index_l:
    count += si.pop(index_l)[1]
    last = si.pop(index_r)
else:
    last = si.pop(index_r)
    count += si.pop(index_l)[1]

for i, j in si:
    count -= i
    if count < 0:
        break
    count += j
count -= last[0]

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

Submission status: Wrong Answer

Solution code:
N = int(input())

S = [input() for i in range(N)]

C = [[0,0] for i in range(N)]

for i in range(N):
    for j in range(len(S[i])):
        if S[i][j] == '(':
            C[i][0] += 1
        else:
            C[i][0] -= 1
        C[i][1] = min(C[i][0],C[i][1])



C.sort(key=lambda x : (-x[1], -x[0]))
#print(C)
now = 0
ans = 'Yes'
for i in range(N):
    if now + C[i][1] < 0:
        ans = 'No'
        break
    now += C[i][0]
if sum(C[i][0] for i in range(N)) != 0:
    ans = 'No'

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from collections import Counter
def main():
    N = int( input())
    Ss = [ input() for _ in range(N)]
    left = 0
    right = 0
    Up = []
    Down = []
    Sig = []
    for S in Ss:
        C = Counter(S)
        left += C["("]
        right += C[")"]
        now = 0
        p = [0]
        for s in S:
            if s == "(":
                now += 1
            else:
                now -= 1
            p.append(now)
        m = -min(p)
        s = p[0]+m
        g = p[-1]+m
        if s == g:
            Sig.append((s, s, g))
        elif s < g:
            Up.append((s ,s, g))
        else:
            Down.append((g,s,g))
    if left != right:
        print("No")
        return
    Sig.sort()
    Up.sort()
    Down.sort()
    now = 0
    for m,s,g in Up:
        if now < m:
            print("No")
            return
        now += g-s
    for m,s,g in Sig:
        if now < m:
            print("No")
            return
    for m,s,g in Down[::-1]:
        if now < m:
            print("No")
            return
        now += g-s
    print("Yes")
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N=int(input())

cand=[]
right=[]
left=[]
for _ in range(N):
    moji=input()
    if moji.count(")")-moji.count("(")>=0:
        right.append(moji)
    else:
        left.append(moji)
mx_r=[]
for item in right:
    mx=-10**9
    temp=0
    for moji in item:
        if moji=="(":
            temp+=1
        else:
            temp-=1
        mx=max(temp,mx)
    mx_r.append([mx,item])

mx_l=[]
for item in left:
    mi=10**9
    temp=0
    for moji in item:
        if moji=="(":
            temp+=1
        else:
            temp-=1
        mi=min(temp,mi)
    mx_l.append([mi,item])

mx_l.sort(key=lambda x:x[0],reverse=True)
mx_r.sort(key=lambda x:x[0],reverse=True)
#print(mx_r,mx_l)    

ans=""
for item in mx_l:
    ans+=item[1]
for item in mx_r:
    ans+=item[1]
#print(ans)

temp=0
for item in ans:
    if item=="(":
        temp+=1
    else:
        temp-=1
    if temp<0:
        print("No")
        exit()
if temp==0:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    tp = 0 
    tm = []
    left = 0
    right = 0
    for i in range(N):
        S = input()
        w = 0
        wl = 0
        l = 0
        r = 0
        for j in S:
            if j == '(':
                l += 1
                wl += 1
            else:
                r += 1
                w -= 1
                w += wl
                wl = 0
        left += l
        right += r
        if w >= 0:
            tp += (l - r)
        else:
            tm.append((l - r, -w))
    if left != right:
        return False
    tm.sort(reverse=True)
    while tm:
        tmp = []
        for i in tm:
            if tp + i[0] < 0:
                return False
            if i[1] <= tp:
                tp += i[0]
            else:
                tmp.append(i)
        if len(tmp) == len(tm):
            return False
        tm = tmp
    return True
if main():
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

Solution code:
n = int(input())

a = []

total_balance = 0

for i in range(n):
	s = input()
	a.append(s)
	total_balance += s.count('(') - s.count(')')

if total_balance != 0:
	print('No')
	exit()

else: 
	minb = []
	maxb = []
	tb = []
	for s in a:
		balance = 0
		min_balance = 0
		max_balance = 0
		for c in s:
			if c == '(':
				balance += 1
			else:
				balance -= 1

			max_balance = max(max_balance, balance)
			min_balance = min(min_balance, balance)

		tb.append(-balance)
		minb.append(-min_balance)
		maxb.append(max_balance)

	b = sorted(zip(minb, tb))

	balance = 0

	#print(b)

	for mb, tb in b:
		mb = -mb
		tb = -tb

		#print(mb, tb)
		if balance + mb < 0:
			print('No')
			exit()

		else:
			balance += tb

		if balance < 0:
			print('No')
			exit()

	print('Yes')

Submission status: Wrong Answer

Solution code:
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

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

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def rangeI(it, l, r):
    for i, e in enumerate(it):
        if l <= i < r:
            yield e
        elif l >= r:
            break

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

INF = 999999999999999999999999
MOD = 10**9+7

n = int(input())
S = [ input() for _ in range(n)]

left = 0
right = 0

l_ok = [False] * n
r_ok = [False] * n
lmr  = [0] * n
min_lmr = [INF] * n

for i,s in enumerate(S):
    l = 0
    r = 0
    lok = True
    for j,c in enumerate(s):
        if c == "(":
            l += 1
        else:
            r += 1
            if r > l:
                lok = False
        min_lmr[i] = min(min_lmr[i], l-r)
    l = 0
    r = 0
    rok = True
    for j in range(len(s)-1, -1, -1):
        if s[j] == "(":
            l += 1
            if l > r:
                rok = False
                break
        else:
            r += 1

    left += s.count("(")
    right += s.count(")")
    lmr[i] = left - right

    l_ok[i] = lok
    r_ok[i] = rok

# log(l_ok)
# log(r_ok)

if left != right:
    print("No")
    exit()

strs = []

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

# # LeftもRightもだめなやつをminL-Rが多い順に並べる
# ngs = []
# for i in range(n):
#     if not l_ok[i] and not r_ok[i]:
#         ngs.append((min_lmr[i], i))

# ngs.sort(key=lambda ng: ng[0], reverse=True)

# # log(ngs)

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

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


# min L-R順に全てを並べる
aaa = []
for i in range(n):
    aaa.append((min_lmr[i], i))
aaa.sort(key=lambda aa: aa[0], reverse=True)
for i in range(n):
    strs.append(S[aaa[i][1]])

# log(min_lmr)
# log("".join(strs))

l = 0
r = 0
for s in strs:
    for j,c in enumerate(s):
        if c == "(":
            l += 1
        else:
            r += 1
            if r > l:
                print("No")
                exit()
print("Yes")

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

def main():  
    N = int(input())
    flag1 = False
    flag2 = False
    left = 0
    right = 0
    for _ in range(N):
        s = input()
        stack = ['-']
        for t in s:
            if t == '(':
                stack.append(t)
            else:
                if stack[-1] == '(':
                    stack.pop()
                else:
                    stack.append(')')
        if len(stack) == 1:
            continue
        elif stack[1] == '(':
            flag1 = True
            left += len(stack) - 1
        elif len(stack) >= 3  and stack[1] == ')' and stack[-1] == '(':
            for i in range(len(stack)):
                if stack[i] == '(':
                    s = i
                    break
            left += len(stack) - s
            right += s - 1
        else:
            flag2 = True
            right += len(stack) - 1
    if right == left == 0 or flag1 and flag2 and right == left:
        print('Yes')
    else:
        print('No') 
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    inf=10**9
    n=II()
    ss=[SI() for _ in range(n)]
    ms=[]
    for s in ss:
        mn=0
        now=0
        for c in s:
            if c=="(":now+=1
            else:now-=1
            if now<mn:mn=now
        ms.append((mn,now))
    ms.sort(key=lambda x:-x[0]-x[1])
    #print(ms)
    cnt=0
    for mn,s in ms:
        if cnt+mn<0:
            print("No")
            exit()
        cnt+=s
    if cnt==0:print("Yes")
    else:print("No")

main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# vim: set fileencoding=utf-8

# pylint: disable=unused-import, invalid-name, missing-docstring, bad-continuation


"""Module docstring
"""

import functools
import heapq
import itertools
import logging
import math
import random
import string
import sys
from argparse import ArgumentParser
from collections import defaultdict, deque
from copy import deepcopy
from typing import Dict, List, Optional, Set, Tuple


def solve(values: List[str]) -> bool:
    counts = defaultdict(int)
    total_closing = 0
    total_opening = 0
    for v in values:
        opening = 0
        closing = 0
        for c in v:
            if c == ")":
                if opening == 0:
                    closing += 1
                else:
                    opening -= 1
            if c == "(":
                opening += 1
        if closing + opening != 0:
            counts[(closing, opening)] += 1
            total_opening += opening
            total_closing += closing
    LOG.debug((counts))
    LOG.debug((total_opening, total_closing))
    if not counts:
        return True
    for opening, closing in counts:
        if opening == total_closing - closing and closing == total_opening - opening:
            return True
    return False


def do_job():
    "Do the work"
    LOG.debug("Start working")
    # first line is number of test cases
    N = int(input())
    values = []
    for _ in range(N):
        values.append(input().strip())
    result = solve(values)
    print("Yes" if result else "No")


def print_output(testcase: int, result) -> None:
    "Formats and print result"
    if result is None:
        result = "IMPOSSIBLE"
    print("Case #{}: {}".format(testcase + 1, result))
    # 6 digits float precision {:.6f} (6 is the default value)
    # print("Case #{}: {:f}".format(testcase + 1, result))


def configure_log() -> None:
    "Configure the log output"
    log_formatter = logging.Formatter("%(lineno)d - " "%(message)s")
    handler = logging.StreamHandler(sys.stdout)
    handler.setFormatter(log_formatter)
    LOG.addHandler(handler)


LOG = None
# for interactive call: do not add multiple times the handler
if not LOG:
    LOG = logging.getLogger("template")
    configure_log()


def main(argv=None):
    "Program wrapper."
    if argv is None:
        argv = sys.argv[1:]
    parser = ArgumentParser()
    parser.add_argument(
        "-v",
        "--verbose",
        dest="verbose",
        action="store_true",
        default=False,
        help="run as verbose mode",
    )
    args = parser.parse_args(argv)
    if args.verbose:
        LOG.setLevel(logging.DEBUG)
    do_job()
    return 0


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    sys.exit(main())


class memoized:
    """Decorator that caches a function's return value each time it is called.
    If called later with the same arguments, the cached value is returned, and
    not re-evaluated.
    """

    def __init__(self, func):
        self.func = func
        self.cache = {}

    def __call__(self, *args):
        try:
            return self.cache[args]
        except KeyError:
            value = self.func(*args)
            self.cache[args] = value
            return value
        except TypeError:
            # uncachable -- for instance, passing a list as an argument.
            # Better to not cache than to blow up entirely.
            return self.func(*args)

    def __repr__(self):
        """Return the function's docstring."""
        return self.func.__doc__

    def __get__(self, obj, objtype):
        """Support instance methods."""
        return functools.partial(self.__call__, obj)

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    S = [input() for _ in range(N)]
    L = []
    for i in range(N):
        t = 0
        mint = 1
        for s in S[i]:
            if s == "(":
                t += 1
            else:
                t -= 1
            mint = min(mint, t)
        L.append((t, mint))
    L.sort(key=lambda x: x[0], reverse=True)
    L.sort(key=lambda x: x[1], reverse=True)
    t = 0
    for l, m in L:
        if t + m < 0:
            return False
        t += l
        if t < 0:
            return False
    if t == 0:
        return True
    return False


if main():
    print("YES")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
import sys
n = int(input())
s = [input() for _ in range(n)]
cnts = []
mins = []
plus = []
minus = []
sm = 0
for i in range(n):
    cnt = 0
    mn = 0
    mx = 0
    for c in s[i]:
        if c == '(':
            cnt+=1
        else: cnt-=1
        mn = min(cnt, mn)
        mx = max(cnt, mx)
    cnts.append(abs(cnt))
    if cnt>0:
        plus.append(i)
        mins.append(mn)
    else:
        minus.append(i)
        mins.append(mx)
    sm+=cnt
if(sm != 0):
    print('No')
    sys.exit()
plus.sort(key = lambda x:mins[x])
minus.sort(key = lambda x:mins[x])
now = 0
que = []
r = 0
while r<len(plus) and mins[plus[r]]<=now:
    que.append(plus[r])
    r+=1
for i in range(len(plus)):
    if(len(que)==0):
        print('No')
        sys.exit()
    j = que.pop()
    now+=cnts[j]
    while r<len(plus) and mins[plus[r]]<=now:
        que.append(plus[r])
        r+=1

plus = minus
now = 0
que = []
r = 0
while r<len(plus) and mins[plus[r]]<=now:
    que.append(plus[r])
    r+=1
for i in range(len(plus)):
    if(len(que)==0):
        print('No')
        sys.exit()
    j = que.pop()
    now+=cnts[j]
    while r<len(plus) and mins[plus[r]]<=now:
        que.append(plus[r])
        r+=1
print('Yes')

Submission status: Wrong Answer

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

N = int(input())
S = [input().rstrip() for _ in range(N)]

def calc(S):
    now = 0
    ret = 0
    for s in S:
        if s == '(':
            now += 1
        else:
            now -= 1
        ret = min(ret, now)
    return ret

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

for s in S:
    less = -calc(s)
    if less == 0:
        H.append(s)
    else:
        l = s.count('(')
        r = len(s) - l
        if l >= r:
            P.append((less, s))
        else:
            L.append((less, s))

P.sort(key=lambda a: a[0])
L.sort(key=lambda a: a[0], reverse=True)
P = [s for _, s in P]
L = [s for _, s in L]
ans = ''.join(H + P + L)

l = ans.count('(')
r = ans.count(')')

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

Submission status: Wrong Answer

Solution code:
N, = map(int, input().split())
X = []
for _ in range(N):
    s = input().strip()
    a, b = 0, 0
    for c in s:
        if c == "(":
            a += 1
        else:
            if a > 0:
                a -= 1
            else:
                b += 1
    X.append((a, b))
X.sort(key=lambda x:x[0]-x[1])
s = 0
stack = []
while X:
    a, b = X.pop()
    if b > s:
        stack.append((a, b))
        continue
    s += a-b
    while stack:
        a, b = stack[-1]
        if b <= s:
            s += a-b
            stack.pop()
            continue
        break
if stack or s != 0:
    print("No")
else:
    print("Yes")

Submission status: Wrong Answer

Solution code:
import heapq

N = int(input())

data = [0]*N
for i in range(N):
    S = list(str(input()))
    s = 0
    m = 0
    for j in range(len(S)):
        if S[j] == "(":
            s += 1
        else:
            s -= 1
            m = min(m,s)
    data[i] = [-m,-s]


heapq.heapify(data)
x = 0
valid = []
heapq.heapify(valid)

det = 0

###
#print("data",data)
#print("valid",valid)
#print(x)
###

while data:
    ###
    #print("data",data)
    #print("valid",valid)
    ###
    while data and x - data[0][0] >= 0:
        y = heapq.heappop(data)
        heapq.heappush(valid,[y[1],y[0]])
    
    ###
    #print("valid",valid)
    ###

    ###
    #print("data",data)
    #print("valid",valid)
    #print(x)
    ###
    while valid and x >= 0:
        z = heapq.heappop(valid)
        x -= z[0]
    
    if data and x - data[0][0] < 0:
        det = -1
        break

if det == 0 and x == 0:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
N = int(input())
A = ""
sum = 0
M = 0
for i in range(N):
    S = input()
    m = 0
    t = 0
    for s in S:
        if s == "(":
            t += 1
        else:
            t -= 1
        if m >= t:
            m = t
    if m == 0:
        M += t
    else:
        M = min(M,sum+m)
    sum += t
if sum != 0 or M < 0:
    print("No")
else:
    print("Yes")

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
def count(s):
    m=0
    e=0
    for t in s:
        if t=='(':
            e+=1
        else:
            e-=1
        m=min(m,e)
    return (e,m)

def solve(P,N):
    s=0
    for _,e in P:
        s+=e
    for _,e in N:
        s+=e
    if s!=0:
        return 'No'
    s=0
    for m,e in P:
        if s+m<0:
            return 'No'
        s+=e
        if s<0:
            return 'No'
    for m,e in N:
        if s+m<0:
            return 'No'
        s+=e
        if s<0:
            return 'No'
    return 'Yes'

def main():
    n=int(input())
    S=[input().strip() for _ in range(n)]
    P,N=[],[]
    for s in S:
        e,m=count(s)
        #print(s,e,m)
        if e>0:
            P.append((m,e))
        else:
            N.append((m,e))
    P.sort(reverse=True)
    N.sort(reverse=True)
    #print(P,N)
    print(solve(P,N))
    
if __name__=='__main__':
    main()