【正经题解】双栈排序

当每个元素进哪个栈确定时，不确定的只有某个元素进一个栈，和另一个栈弹出元素的顺序。

这种情况，因为要求字典序最小，而
a 栈的所有操作的字典序都小于 b 栈，我们每次有元素进 b 栈前先尽可能把 a 栈能弹出的先弹出。
这样，我们知道，只要确定每个数进入哪个栈，问题就解决了！
怎么确定呢？？
也就是确定哪些元素无论是否同时在栈内，都不能进入同一个栈。即，找到所有
i 元素选择进入 a 栈，那么 j 元素只能进入 b 栈的情况。

如果有一个顺序靠前的元素，和一个顺序靠后的元素，前者大于后者，前者和后者可以进入同一个栈，即前面的元素进入没有弹出时，后面的元素进入。

如果有一个顺序靠前的元素 i，和一个顺序靠后的元素 j，前者大小小于后者

#include<bits/stdc++.h>
using namespace std;

int n, N, x, k, tot, sum = 1, p1 = 1001, p2 = 1001;
int a[1001], f[1005], c[1001], t[2005], head[1005];
char s[5] = {'0', 'a', 'b', 'c', 'd'};
vector<int> p[1001];  // p[i]统计i的边
queue<int> q;  // 广搜染色队列
stack<int> s1, s2;

struct edge {
    int next, to;
} e[2000005];

inline void add(int x, int y) {  // 链式前向星存边
    ++tot;
    e[tot].next = head[x];
    e[tot].to = y;
    head[x] = tot;
}

inline int read() {
    int x = 0;
    bool f = 1;
    char ch = getchar();
    while (ch > '9' || ch < '0') {
        if (ch == '-') f = 0;
        ch = getchar();
    }
    while (ch <= '9' && ch >= '0') {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return f ? x : -x;
}

int main() {
    n = read(), f[n + 1] = n + 1, N = 2 * n;

    for (int i = 1; i <= n; ++i) a[i] = read();
    for (int i = n; i >= 1; --i) f[i] = min(f[i + 1], a[i]);  // 寻找i为起点的最小值，注意从n开始 

    for (int i = 1; i <= n; ++i)
        for (int j = i + 1; j <= n; ++j)
            if (a[i] < a[j] && a[i] > f[j + 1])  // 如果i,j不能处于同一个栈，建立以i,j为顶点的无向边 
                add(i, j), add(j, i);

    for (int i = 1; i <= n; ++i) {
        if (!c[i]) {  // 如果i点未被染色，加入队列 
            q.push(i);
            c[i] = 1;  // 1表示进入栈1，因为要求最小字典序 
            while (!q.empty()) {
                x = q.front();  // 取出队首元素 
                q.pop();
                for (int j = head[x]; j; j = e[j].next) {
                    int y = e[j].to;
                    if (c[y]) {
                        if (c[y] ^ c[x])  // 如果已被染色且不冲突就跳过这条边 
                            continue;
                        puts("0");  // 如果发生冲突（即出现两端点颜色相同）直接结束
                        return 0;
                    }
                    c[y] = c[x] * (-1);  // 将未被染色的点染成与队首元素相反的颜色 
                    q.push(y);  // 放入队列，继续扩展 
                }
            }
        }
    }

    int i = 1;
    while (k < N) {  
        if (!s1.empty()) p1 = s1.top();
        if (!s2.empty()) p2 = s2.top();
        if (c[i] == 1 && (a[i] < p1 || s1.empty())) s1.push(a[i]), t[++k] = 1, ++i;  // 注意考虑栈为空的情况 
        else if (p1 == sum) ++sum, t[++k] = 2, s1.pop();
        else if (c[i] == -1 && (a[i] < p2 || s2.empty())) s2.push(a[i]), t[++k] = 3, ++i;
        else if (p2 == sum) ++sum, t[++k] = 4, s2.pop();
    }

    for (int i = 1; i <= N; ++i)
        printf("%c ", s[t[i]]);

    return 0;
}