Problem:

B: 括弧を語る数 / Parentheses Number

問題

以下のように 正しい括弧列 を定めます。

 空文字列は正しい括弧列である

 正しい括弧列 S に対して ( S )  は正しい括弧列である

 正しい括弧列 S, T に対して ST は正しい括弧列である

ここで、正しい括弧列に対して以下のような規則で順列を対応付けます。

i 番目の閉じ括弧が j 番目の開き括弧に対応しているとき、 数列の i 番目の値は j である。

長さ n の順列 P = ( p_1, p_2, $\ldots$, p_n ) が与えられるので、 それに対応する括弧列を復元してください。

ただし、順列に対応する括弧列が存在しない場合は :( を出力してください。

入力形式

n
p_1 p_2 $\ldots$ p_n

1 行目に順列の項数 n が与えられる。

2 行目に順列 p_1, p_2, $\ldots$, p_i, $\ldots$, p_n が空白区切りで与えられる。

制約

 1 \leq n \leq 10^5

 1 \leq p_i \leq n

 入力は全て整数である。

P = ( p_1, p_2, $\ldots$, p_n ) は順列である。

出力形式

順列に対応する括弧列を出力してください。

そのような括弧列が存在しない場合は :( を出力してください。

入力例1

2
2 1

出力例1

(())

入力例2

10
1 2 3 4 5 6 7 8 9 10

出力例2

()()()()()()()()()()

入力例3

3
3 1 2

出力例3

:(



Sample input:
2
2 1


Sample output:
(())

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
cnt = 0
ans = ''
st = list()
for x in a:
    while cnt < x:
        ans += '('
        cnt += 1
        st.append(cnt)
    if st[-1] == x:
        st.pop()
        ans += ')'
    else:
        ans = ':('
        break
print(ans)

Submission status: Accepted

Solution code:
import itertools as ite
from decimal import *
import math

INF = 10 ** 18

n = input()
p = map(int, raw_input().split())
S = ""
prev = [-1] * (n + 1)
nex = [0] + [-1] * (n + 1)
num_p = 0
for num in p:
    if num > num_p:
        num_next = num_p
        while num_next <= num:
            if nex[num_next] != -1:
                id = num_next
                while nex[num_next] != -1:
                    num_next = nex[num_next] + 1
                nex[id] = num_next - 1
            S += "("
            num_next += 1
        S += ")"
        nex[num] = num
        prev[num] = num
    else:
        num_prev = num_p - 1
        while prev[num_prev] != -1:
            num_prev = prev[num_prev] - 1
        if num_prev != num:
            print ":("
            exit()
        prev[num_p] = num_prev
        nex[num] = num
        prev[num] = num
        S += ")"
    num_p = num
print S

Submission status: Accepted

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

N = int(input())
P = list(map(int,input().split()))

Q = [-1]*N
for i,p in enumerate(P):
    Q[p-1] = i

S = ''
a = 1
def rec(l,r):
    global S,a
    if l==r:
        return
    while l < r:
        ai = Q[a-1]
        if ai >= r:
            print(':(')
            exit()
        a += 1
        S += '('
        rec(l,ai)
        S += ')'
        l = ai + 1
rec(0,N)

print(S)