LOJ

分析

我们把 $i$ 向 $p_i$ 连边，这样子会有很多环。可以发现，如果有奇环则无解，所以我们只考虑偶环。

显然一个偶环上只会是一个 (、一个 )、……，但是如果直接搜的话复杂度最大会达到 $\mathcal{O}(2^{\frac{n}{2}})$，无法接受。

考虑一个大小为 $2$ 的偶环，显然小的那个填 (、大的那个填 ) 更优，因此我们只需要搜大小 $\geq 4$ 的环即可。时间复杂度降为 $\mathcal{O}(2^\frac{n}{4})$，然后就可以过了。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100+10;

int n,tot=0;
int p[N],vis[N],ans[N];
vector<int> vec,cir[N>>2];

inline void find(int x) {
    vec.clear();
    for (re int i=x;!vis[i];i=p[i])
        vis[i]=1,vec.push_back(i);
    if (vec.size()==2) {
        if (vec[0]<vec[1]) ans[vec[0]]=1,ans[vec[1]]=-1;
        else ans[vec[0]]=-1,ans[vec[1]]=1;
    }
    else cir[++tot]=vec;
}

inline int check() { int s=0;
    for (re int i=1;i<=n;++i) {
        s+=ans[i];
        if (s<0) return 0;
    }
    return s==0;
}

inline void dfs(int p) { int t;
    if (p>tot) {
        if (!check()) return;
        for (re int i=1;i<=n;++i) putchar(ans[i]==1?'(':')');
        puts(""); exit(0);
    }
    t=1; for (re int i:cir[p]) ans[i]=t,t=-t; dfs(p+1);
    t=-1; for (re int i:cir[p]) ans[i]=t,t=-t; dfs(p+1);
}

int main() {
    n=read();
    for (re int i=1;i<=n;++i) p[i]=read();
    for (re int i=1;i<=n;++i) if (!vis[i]) find(i);
    dfs(1);
    return 0;
}