解题思路
这道题乍一看还以为是个模拟。。怒写一发30分（）。
其实很好hack，如
10
10 2 8 1 7 9 3 4 5 6
按模拟的思路，应该是10入第一个栈，2入第一个栈，8入第二个栈，1入第一个栈，把1、2
弹出，所以此时第一个栈还剩10，第二个栈还剩8。7来了入第一个栈，9就无家可归了，这就出问题了，实际上应该让7入第二个栈。结果正解是二分图？？像我这样的蒟蒻哪能想出来。。
做法是先选出所有如上的数字对，让他们连边，之后二分图染色，入栈时判断颜色。
代码
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1005;
inline int rd(){
int x=0,f=1;char ch=getchar();
while(ch<'0' || ch>'9') {if(ch=='-') f=-1;ch=getchar();}
while(ch>='0' && ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return x*f;
}
struct Edge{
int nxt,to;
}edge[MAXN<<1];
int n,a[MAXN],col[MAXN];
int head[MAXN],cnt;
bool vis[MAXN];
int st1[MAXN],top1,st2[MAXN],top2,num;
inline void add(int bg,int ed){
edge[++cnt].to=ed;
edge[cnt].nxt=head[bg];
head[bg]=cnt;
}
inline bool dfs(int x){
vis[x]=1;
for(register int i=head[x];i;i=edge[i].nxt){
if(vis[edge[i].to]){
if(col[edge[i].to]==col[x]) return false;
}
else{
col[edge[i].to]=col[x]^1;
if(!dfs(edge[i].to)) return false;
}
}
return true;
}
int main(){
n=rd();
for(register int i=1;i<=n;i++) a[i]=rd();
int k=1e9;
for(register int i=n;i;i--){
k=min(k,a[i]);
for(register int j=1;j<i;j++)
if(a[j]<a[i] && a[j]>k) add(j,i),add(i,j);
}
for(register int i=1;i<=n;i++){
if(!vis[i])
if(!dfs(i)){
puts("0");
return 0;
}
}
num=1;
for(register int i=1;i<=n;i++){
if(col[i]==0){
printf("a ");
st1[++top1]=a[i];
}
else{
printf("c ");
st2[++top2]=a[i];
}
while(st1[top1]==num || st2[top2]==num){
if(st1[top1]==num)
printf("b "),top1--;
else
printf("d "),top2--;
num++;
}
}
while(st1[top1]==num || st2[top2]==num){
if(st1[top1]==num)
printf("b "),top1--;
else
printf("d "),top2--;
num++;
}
return 0;
}