考虑假设已知括号序列 \(s\)，如何求出 \(p,q\)。
对于求 \(p\)，考虑从 \(s_1\) 到 \(s_n\) 逐个往里放，如果能放就直接放，肯定不劣，否则就从后面抽最近的左括号放过来，然后继续放。不难证明不存在更优方案，对于 \(q\) 同理。
接下来我们发现，如果 \(p\) 中存在 \(p_i < p_{i-1}\)，\(s_{p_{i-1}}\) 必然为左括号，\(s_{p_i}\) 必然为右括号，对于 \(q\) 也有类似的结论。实际如果 \(p,q\) 合法，已经足以求出括号序列 \(s\) 了。
证明考虑画出括号序列的折线图，那么 \(p\) 求出的就是低于水平线的所有部分（对于水平线下的部分，设右括号分别位于 \(r_1,r_2 \dots r_k\)，左括号位于 \(l_1,l_2 \dots l_k\)，那么 \(\forall i,r_i < l_i\)，所以每个左括号都会被抽到前面）。同理由于 \(q\) 是对中心对称后的折线图进行这一过程，其求出的自然是高于水平线的所有部分，拼起来自然就是整体。
当然，由于我们只利用了一部分信息求出便求出了答案，所以其余一部分信息可能与答案冲突。对求出的答案重新贪心一遍，判断贪心出的序列是否和 \(p,q\) 相同即可。
精细实现可以做到 \(O(n)\)。
代码实现
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef double db;
inline ll read() {
ll x=0,f=1;char ch=getchar();
while(!isdigit(ch)) {if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
const int N=4e5+5;
int n,p[N],q[N];
char s[N];
bool ck_sit() {
int nwp=0,nwq=0;
for(int i=1;i<=n;i++) {
if(s[p[i]]=='(') nwp++;
else nwp--;
if(s[q[i]]=='(') nwq++;
else nwq--;
if(nwp<0||nwq<0) return 0;
}
if(nwp||nwq) return 0;
return 1;
}
int np[N],nq[N];
bool ck_mnmx() {
int cntp=0,cntq=0,nw=0;
set <int> sl;
for(int i=1;i<=n;i++) if(s[i]=='(') sl.insert(i);
for(int i=1;i<=n;i++) {
if(s[i]=='('&&sl.find(i)==sl.end()) continue;
if(s[i]=='(') sl.erase(i),nw++,np[++cntp]=i;
else if(nw) nw--,np[++cntp]=i;
else np[++cntp]=(*sl.begin()),sl.erase(*sl.begin()),np[++cntp]=i;
}
for(int i=1;i<=n;i++) if(np[i]!=p[i]) return 0;
nw=0;sl.clear();
for(int i=n;i>=1;i--) if(s[i]=='(') sl.insert(-i);
for(int i=n;i>=1;i--) {
if(s[i]=='('&&sl.find(-i)==sl.end()) continue;
if(s[i]=='(') sl.erase(-i),nw++,nq[++cntq]=i;
else if(nw) nw--,nq[++cntq]=i;
else nq[++cntq]=-(*sl.begin()),sl.erase(*sl.begin()),nq[++cntq]=i;
}
for(int i=1;i<=n;i++) if(nq[i]!=q[i]) return 0;
return 1;
}
int main() {
n=read()*2;
for(int i=1;i<=n;i++) p[i]=read();for(int i=1;i<=n;i++) q[i]=read();
for(int i=2;i<=n;i++) if(p[i]<p[i-1]) s[p[i]]=')',s[p[i-1]]='(';
for(int i=2;i<=n;i++) if(q[i]>q[i-1]) s[q[i]]=')',s[q[i-1]]='(';
for(int i=1;i<=n;i++) if(s[i]!='('&&s[i]!=')') return puts("-1"),0;
if(!ck_sit()||!ck_mnmx()) return puts("-1"),0;
for(int i=1;i<=n;i++) cout<<s[i];
cout<<'\n';
return 0;
}