根据 \(P_i\) 是个排列，那将 \(i\) 和 \(P_i\) 进行连边之后不难发现图是由许多环构成的。
则若 \(i\) 为 (，\(P_i\) 则肯定为 )，\(P_j = i\) 的 \(j\) 肯定也为 )，否则就会出现度数为 \(2\) 的情况。
所以发现一个点与相邻两个点的状态是恰好相反的，即确定环上任意一点就可以确定环上整个点的状态，进一步还能发现环只能是偶环，若是奇环则无法构造出合法的方案。
那么对于 \(n = 40\)，偶环最多有 \(20\) 个，直接枚举每个环状态判断即可，最坏时间复杂度 \(O(2^{\frac{n}{2}})\)，\(n=100\) 还是过不了。
发现题目还有个性质没用到，整个括号序列合法，则对于每一位前缀 ( 的个数 \(\ge\) ) 个数。
这则说明了当环点数为 \(2\) 时，( 在前面，) 在后面一定不劣。
于是可以判掉点数为 \(2\) 的环，这样需要枚举的环点数肯定 \(\ge 4\)，最坏时间复杂度 \(O(2^{\frac{n}{4}})\)，能过 \(n=100\) 啦。
// lhzawa(https://www.cnblogs.com/lhzawa/)
// Problem: #6043. 「雅礼集训 2017 Day7」蛐蛐国的修墙方案
// Contest: LibreOJ
// URL: https://loj.ac/p/6043
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
using namespace std;
const int N = 1e2 + 10;
basic_string<int> h[N];
int p[N];
int vis[N];
int kh[N];
int main() {
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &p[i]);
}
int tot = 0;
for (int i = 1; i <= n; i++) {
if (! vis[i]) {
tot++;
for (int s = i; ! vis[s]; vis[s] = 1, h[tot] += s, s = p[s]);
if (h[tot].size() == 2) {
int a = h[tot][0], b = h[tot][1];
kh[min(a, b)] = 1, kh[max(a, b)] = -1;
h[tot].clear(), tot--;
}
}
}
for (int k = 0; k < (1 << tot); k++) {
for (int i = 1; i <= tot; i++) {
int p = (k >> (i - 1)) & 1;
for (int j = 0; j < (int)(h[i].size()); j++) {
kh[h[i][j]] = (p ^ (j & 1)) ? 1 : -1;
}
}
int w = 0, Yes = 1;
for (int i = 1; i <= n; i++) {
w += kh[i];
if (w < 0) {
Yes = 0;
break;
}
}
if (Yes) {
for (int i = 1; i <= n; i++) {
printf("%c", kh[i] == 1 ? '(' : ')');
}
return 0;
}
}
return 0;
}