题解

如果两个数 $p_i < p_j$ 且在它们之间存在更小的数，那么把 $p_i, p_j$ 放进同一个栈会形成经典的「231」坏模式，导致该栈无法被单栈排序。因此只需把所有这种「不能同栈」的点对连边，若图二分则一定存在可行方案；否则输出 0。

建图做二分染色：
对于每个位置 $i$，往后扫描维护区间最小值 cur_min，若 p[i] < p[j] && cur_min < p[i]，在 $i, j$ 之间连边。$n \le 1000$，直接 $\mathcal{O}(n^2)$ 足够。

染色后颜色即栈的归属。按输入顺序处理元素，始终尽可能弹出当前需要的最小值（优先弹出栈 $S_1$，因为操作字典序 b < d），否则按染色结果压入对应的栈（操作 a / c）。二分图保证不会卡死；最终若输出顺序完整得到 $1..n$，记录的操作序列即为所求的字典序最小方案。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if (!(cin >> n)) return 0;
    vector<int> p(n);
    for (int i = 0; i < n; ++i) cin >> p[i];

    vector<vector<int>> adj(n);
    for (int i = 0; i < n; ++i) {
        int cur_min = INT_MAX;
        for (int j = i + 1; j < n; ++j) {
            cur_min = min(cur_min, p[j]);
            if (p[i] < p[j] && cur_min < p[i]) {
                adj[i].push_back(j);
                adj[j].push_back(i);
            }
        }
    }

    vector<int> color(n, -1);
    queue<int> q;
    for (int i = 0; i < n; ++i) {
        if (color[i] != -1) continue;
        color[i] = 0;
        q.push(i);
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (int v : adj[u]) {
                if (color[v] == -1) {
                    color[v] = color[u] ^ 1;
                    q.push(v);
                } else if (color[v] == color[u]) {
                    cout << 0 << '\n';
                    return 0;
                }
            }
        }
    }

    vector<int> s0, s1;
    vector<char> ops;
    int need = 1;
    auto pop_ready = [&]() {
        while (true) {
            if (!s0.empty() && s0.back() == need) {
                ops.push_back('b');
                s0.pop_back();
                ++need;
            } else if (!s1.empty() && s1.back() == need) {
                ops.push_back('d');
                s1.pop_back();
                ++need;
            } else {
                break;
            }
        }
    };

    for (int i = 0; i < n; ++i) {
        pop_ready();
        if (color[i] == 0) {
            ops.push_back('a');
            s0.push_back(p[i]);
        } else {
            ops.push_back('c');
            s1.push_back(p[i]);
        }
        pop_ready();
    }
    pop_ready();
    if (need != n + 1) {
        cout << 0 << '\n';
        return 0;
    }
    for (size_t i = 0; i < ops.size(); ++i) {
        if (i) cout << ' ';
        cout << ops[i];
    }
    cout << '\n';
    return 0;
}