有hack是因为s1在弹栈的时候没有考虑弹栈结果是否合理
即：当s2的栈顶元素小于s1的栈顶元素时应该优先让s2弹栈

#include<iostream>
#include<cstring>
#include<stack>
#include<vector>
using namespace std ;

const int N = 1e3 + 10, M = 1e6 + 10 ;

int a[N], f[N], n ; //f[i] = 点i后面的点的最小值  
int color[N] ; // 每个点的颜色
int h[N], e[M], ne[M], idx;
stack<int> sk1, sk2 ;
vector<int> path ;

void add(int a, int b){
    e[idx] = b, ne[idx] = h[a], h[a] = idx++ ;
}

bool dfs(int u, int v){ // u 染色节点  c 染色类型
    color[u] = v ;
    for(int p = h[u]; ~p; p = ne[p]){
        int s = e[p] ;
        if(color[s]){
            if(color[s] == v) return false ;
        } else{
            if(!dfs(s, 3-v)) return false ;
        }
    }
    return true ;
}

void func(){
    if(sk1.top() <= sk2.top()){ // 尝试先让sk1弹栈
        path.push_back('b') ;
        sk1.pop() ;
    } else{ // 否则让sk2弹栈
        path.push_back('d') ;
        sk2.pop() ;
    }
}

int main(){
    memset(h, -1, sizeof(h)) ; 
    int n ;
    cin >> n ;
    for(int i = 0; i < n; i++) scanf("%d", &a[i]) ;
    f[n] = 1e9+10 ;
    for(int i = n - 1; ~i; i--) f[i] = min(a[i], f[i+1]) ;
    for(int i = 0; i < n; i++){
        for(int j = i + 1; j < n; j++){
            if(a[i] < a[j] && a[i] > f[j+1]){
                add(i, j) ;
                add(j, i) ;
            }
        }
    }
    bool flag = true ;
    for(int i = 0; i < n && flag; i++){ // 逐一染色
        if(!color[i]) flag = dfs(i, 1) ; // 优先添加到s1
    }
    if(!flag) puts("0") ; // 染色失败
    else{ // 模拟栈的进出了
        sk1.push(M), sk2.push(M); // 加入哨兵 (加入一个极大值，无法被其他值弹出)
        for(int i = 0; i < n; i++){
            if(color[i] == 1){
                // 考虑是否需要弹栈
                while(a[i] > sk1.top()) func() ;
                path.push_back('a') ;
                sk1.push(a[i]) ;
            } else{
                // 考虑是否需要弹栈
                while(a[i] > sk2.top()) func() ;
                // 考虑s1是否需要继续弹栈
                while(sk1.top() <= sk2.top() && sk1.top() <= f[i+1]){
                    path.push_back('b') ;
                    sk1.pop() ;
                }
                path.push_back('c') ;
                sk2.push(a[i]) ;
            }
        }
        // 将没有弹出栈的元素都弹出
        while(sk1.size() > 1 || sk2.size() > 1) func() ;
        for(auto c : path) printf("%c ", c) ;
    }
}