传送门
毒瘤细节题。
首先考虑不合法的情况。
先把相同的值配对，这样就构成了一些区间。
那么如果这些区间有相交的话，就不合法了。
如何判断？DZYO安利了一波st表，我觉得很不错。
接着考虑两个相同的值，它们中间一定只有奇数个数。
然后剩下不合法的情况可以在接下来处理时判断。
接下来还原序列的问题是可以拆分成子问题的。
考虑这两个相同的值夹住的区间。
显然这个区间里是没有值相同的。
对于区间里两个相邻且不全为0的数。
如果是形如0xy0xy0xy的话，我们把0改成y可以变成一个可行解yxyyxyyxy。
而如果是形如xy0xy0xy0的话，我们把0改成x可以变成一个可行解xyxxyxxyx。
如果连续三个都不同那一定是凉了。
这样的话，对于头两种情况，我们用一个并查集维护一种操作。
如果是第一种情况，我们可以直接丢掉0x0x0x只保留y在序列中同时把答案数组中0对应的值赋为y。
第二种同理。
这样操作完整个序列之后序列会严重缩水变成：
X0...0A10...0A20...0A30...0XX0...0A_10...0A_20...0A_30...0XX0...0A10...0A20...0A30...0X
然后继续操作。
如果两端都为0或者都为相同的数直接递归子问题。
如果了两端有一个不为0的，把为0的变成跟它相同的就行了。
最后有点细节。
如果这一次处理的区间为[L,R][L,R][L,R]，我们再用一个并查集把它们并在一起，下一次直接当成一个点就行了。
p.s.由于本蒟蒻很菜，代码是照着DZYO学长写的。
代码：
#include<bits/stdc++.h>
#define N 1000005
using namespace std;
inline int read(){
int ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
int n,m,in[N],pred[N],last[N],cnt[N],len,st[N][21],L[N],R[N];
vector<int>del;
inline int min(int a,int b){return a<b?a:b;}
inline int find(int*fa,int x){return x==fa[x]?x:fa[x]=find(fa,fa[x]);}
inline bool solve(int l,int r){
vector<int>pos;
int Ri=-1;
for(int i=find(R,l);i<=r;i=find(R,i+1)){
pos.push_back(i),++Ri;
while(pos.size()>=3){
if(((!in[pos[Ri-2]]&&in[i])||(in[pos[Ri-2]]&&!in[i])||(in[pos[Ri-2]]&&(in[pos[Ri-2]]==in[i])))&&in[pos[Ri-1]]){
if(in[pos[Ri-2]]!=in[pos[Ri]])in[pos[Ri-2]]=in[i]=in[pos[Ri-2]]+in[i];
pos.pop_back(),pos.pop_back(),Ri-=2;
}
else break;
}
}
for(int i=1;i<pos.size();++i)if(in[pos[i]]&&in[pos[i-1]]){puts("no");return 0;}
deque<int>q;
int Le=pos[0];
for(int i=1;i<pos.size()-1;++i)q.push_back(pos[i]);
while(!q.empty()){
int x=q.front(),y=q.back();
if(q.size()==1){
if(!in[x]){
if(del.empty()){puts("no");return 0;}
in[x]=del.back(),del.pop_back();
}
break;
}
else{
if(!in[x]&&!in[y]){
if(del.empty()){puts("no");return 0;}
in[x]=in[y]=del.back(),del.pop_back(),Le=in[x],q.pop_front(),q.pop_back();
}
else if(in[x])in[q[1]]=Le,q.pop_front(),q.pop_front();
else in[q[q.size()-2]]=Le,q.pop_back(),q.pop_back();
}
}
for(int i=find(R,l);i<=r;i=find(R,i+1))if(i!=l)R[i]=r+1;
L[r]=l;
return 1;
}
int main(){
n=read();
for(int i=1;i<n*2;++i)in[i]=read(),++cnt[in[i]];
for(int i=1;i<=n;++i)if(!cnt[i])del.push_back(i);
if(in[1]&&in[n*2-1]&&in[1]!=in[n*2-1]){puts("no");return 0;}
else if(!in[1]&&!in[n*2-1]){
if(del.empty()){puts("no");return 0;}
in[1]=in[n*2-1]=del.back(),del.pop_back();
}
else if(in[1]!=in[n*2-1])in[1]=in[n*2-1]=in[1]+in[n*2-1];
for(int i=1;i<n*2;++i){
if(!in[i])continue;
pred[i]=last[in[i]]?last[in[i]]:i,last[in[i]]=i;
}
for(int i=1;i<n*2;++i){
st[i][0]=pred[i]?pred[i]:i;
if(in[i]&&((pred[i]&1)!=(i&1))){puts("no");return 0;}
for(int j=1;j<=20&&(1<<j)<=i;++j)st[i][j]=min(st[i][j-1],st[i-(1<<(j-1))][j-1]);
if(in[i]&&pred[i]<i){
int mn=i,pre=i-1;
for(int j=20;~j;--j)if(pre-(1<<j)+1>pred[i])mn=min(mn,st[pre][j]),pre-=(1<<j);
if(mn<=pred[i]){puts("no");return 0;}
}
}
for(int i=1;i<=n*2;++i)L[i]=R[i]=i;
for(int i=2;i<n*2;++i){
if(!in[i]||find(L,pred[i])>=i)continue;
if(!solve(find(L,pred[i]),i))return 0;
}
puts("yes");
for(int i=1;i<n*2;++i)printf("%d ",in[i]);
return 0;
}