こういうのを頭混乱させずにきっちり素早く解ける人が、強い人なんだと思う。強くなりたい！！！！！！
ということで教育的な楽しい問題！！！

問題概要

整合するカッコ列 $S$ があって、 $S$ から以下のように定義される長さ $N$ の順列 $p$ が与えれる:

i 個目の右カッコに対応する左カッコは、左カッコの中で $p_i$ 番目に登場する

この条件を満たすような $S$ を復元せよ。

制約

$1 \le N \le 10^{5}$
$|S| = 2N$

解法 1: そのままの p で真っ向から解く

まずは正面突破する方法から。解法として、

0 個目の右カッコ
1 個目の右カッコ
...

と順々に考えていくのだが、カッコ列を作っていくときに、

i-1 番目の右カッコまでは整合を保ちながらカッコ列を書けたとき、i 番目の右カッコを書くときに、その前に何個左カッコを書くべきかが一意に決まる

ということに着目する。具体的には $p_i$ を 0-indexed として

これまでに書いた左カッコの個数 num が、num $\le p_i$ のとき、左カッコの個数が $p_i + 1$ 個になるまで左カッコを書いて、一番最後に書いた左カッコの直後に、 i 番目の右カッコを書いてマッチさせる
そうでないときは、前回の右カッコのすぐ直後に右カッコを書くしかない。そのときに対応する左カッコが何番目のものなのかは stack などを用いて決定される。それが $p_i$ と一致していたら OK で、一致していなかったらアウト

という感じに解くことができる。

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

int main() {
    int N; cin >> N;
    vector<int> p(N);
    for (int i = 0; i < N; ++i) cin >> p[i], --p[i];
    
    string res = "";
    bool ok = true;
    int num = 0;
    stack<int> st;
    for (int i = 0; i < N; ++i) {
        if (num <= p[i]) {
            while (num <= p[i]) {
                res += "(";
                st.push(num++);
            }
        }
        else if (st.top() != p[i]) { ok = false; break; }
        res += ")";
        st.pop();
    }
    if (ok) cout << res << endl;
    else cout << ":(" << endl;
}

解法 2: p の「左」「右」入れ替えて解く

解法 1 では

各右カッコがどの左カッコに対応するか

について考えていたが、見方を変えて

各左カッコがどの右カッコに対応するか ( $q_i$ とおく)

という見方で解いてみる。素直に stack を用いて解くことができる。

基本的に毎ステップごとに左カッコを追加していき、その直後に

stack のトップにある左カッコが $j$ 番目のものであったとき、その時点で num 個の右カッコが登場済みであったとして $q_j$ == num であったならばそこで右カッコを登場させて、stack から左カッコを消す

という操作を可能なかぎり繰り返すようにすればよい。

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

int main() {
    int N; cin >> N;
    vector<int> p(N) , q(N);
    for (int i = 0; i < N; ++i) cin >> p[i], --p[i], q[p[i]] = i;
    
    string res = "";
    int num = 0;
    stack<int> st;
    for (int i = 0; i < N; ++i) {
        res += "(";
        st.push(i);
        while (!st.empty() && q[st.top()] == num) {
            res += ")";
            ++num;
            st.pop();
        }
    }
    if (st.empty()) cout << res << endl;
    else cout << ":(" << endl;
}