题解

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

const int N = 1e4+10;
int n, K = 1, a[N], ka, adr[N];
bool vis[N];
stack<int> S1, S2;
char ans[N << 1];

bool f(int x, int y) {
    for (int i = x; i <= y; i++) {
        if (!vis[i]) return false;
    }
    return true;
}

bool check(int x) {
    if (S2.empty()) return true;
    memset(vis, 0, sizeof(vis));
    for (int i = adr[x]; i <= max(adr[S1.top() - 1], adr[K]); i++) {
        vis[a[i]] = true;
    }
    if (f(S2.top() + 1, n)) return false;
    return true;
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        adr[a[i]] = i;
    }
    for (int i = 1; i <= n; i++) {
        if (S1.empty() || (!S2.empty() && S2.top() < a[i] && S1.top() > a[i])) {
            S1.push(a[i]);
            ans[ka++] = 'a';
        } else if (!S1.empty() && S1.top() < a[i]) {
            if (S2.empty() || S2.top() > a[i]) {
                S2.push(a[i]);
                ans[ka++] = 'c';
            } else {
                cout << "0";
                return 0;
            }
        } else {
            if (a[i] == K) {
                S1.push(a[i]);
                ans[ka++] = 'a';
            } else if (a[i] == S1.top() - 1) {
                S1.push(a[i]);
                ans[ka++] = 'a';
            } else if (!S2.empty() && a[i] == S2.top() - 1) {
                S2.push(a[i]);
                ans[ka++] = 'c';
            } else {
                if (check(a[i])) {
                    S1.push(a[i]);
                    ans[ka++] = 'a';
                } else {
                    S2.push(a[i]);
                    ans[ka++] = 'c';
                }
            }
        }
        while ((!S1.empty() && S1.top() == K) || (!S2.empty() && S2.top() == K)) {
            if (!S1.empty() && S1.top() == K) {
                ans[ka++] = 'b';
                S1.pop();
                K++;
            } else if (!S2.empty() && S2.top() == K) {
                ans[ka++] = 'd';
                S2.pop();
                K++;
            }
        }
    }
    for (int i = 0; i < (n << 1); i++) {
        for (int j = 0; j < (n << 1) - 1; j++) {
            if ((ans[j] == 'd' && ans[j + 1] == 'a') || (ans[j] == 'c' && ans[j + 1] == 'b')) {
                swap(ans[j], ans[j + 1]);
            }
        }
    }
    for (int i = 0; i < (n << 1); i++) {
        cout << ans[i] << " ";
    }
    return 0;
}