Miku

规律：假如只有一个栈，那么如果原序列存在三个数x<y<Z&&$V_y>V_x>V_z$

那么就不可能排序成功，但是这里有两个栈，那么就应该把原序列分成两部分

两部分？二分图。

把不能在一起的点连边，进行二分图染色。

如果成功，就意味着存在&&两个栈的成员搞定了

反之不存在

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<stack>
using namespace std;
int n;
int fi[1001];
struct e{
    int to;
    int ne;
} edge[10000001];
int color[1001];
int rm[1001];
stack <int>s1,s2;
int p;
int s=1;
int ord=1;
int head[1001];
void add(int f,int t){
    p++;
    edge[p].ne=head[f];
    edge[p].to=t;
    head[f]=p;
    return ;
} 
int v;
void dfs(int now,int c){
    color[now]=c;
    for(int i=head[now];i;i=edge[i].ne){
        v=edge[i].to;
        if(color[v]==c){
            s=0;
            return ;
        }
        if(color[v]==-1){
            dfs(v,c^1);
        }
    }
}
void find(){
    for(int i=1;i<n;++i)
        for(int j=i+1;j<n;++j){
            if(fi[j]>fi[i]&&rm[j+1]<fi[i]){
            add(i,j);
            add(j,i);
            }
        }
    for(int i=1;i<=n;++i){
        if(color[i]==-1)
        {
            dfs(i,1);
        }
    }
}
void print(){
    for(int i=1;i<=n;++i){
        if(color[i]==1){
            s1.push(i);
            cout<<"a"<<" ";
        }else{
        s2.push(i);
        cout<<"c"<<" ";
        }
        while((!s1.empty()&&fi[s1.top()]==ord)||(!s2.empty()&&fi[s2.top()]==ord)){
            while(!s1.empty()&&fi[s1.top()]==ord){
                ord++;
                s1.pop();
                cout<<"b ";
            }
            while(!s2.empty()&&fi[s2.top()]==ord){
                ord++;
                s2.pop();
                cout<<"d ";
            }
        }
    }
}
int main(){
    scanf("%d",&n);
    memset(color,-1,sizeof(color));
    for(int i=1;i<=n;++i){
        scanf("%d",&fi[i]);
        rm[i]=fi[i];
    }
    rm[n+1]=0x7f7f7f7f;
    for(int i=n;i;--i){
        if(rm[i+1]<fi[i])
        rm[i]=rm[i+1];
    }
    find();
    if(s==0){
        cout<<0;
        return 0;
    }else{
        print();
    }
    return 0;
}