2021牛客暑期多校训练营10 F、Train Wreck

题目大意

给你一个长度为的出栈入栈序列，你现在有辆列车，第辆列车颜色为，你要让每次停留在栈中颜色排列是唯一的。问是否可行，如果可行输出进栈颜色方案。

Solution

考点：堆

我们可以把出栈入栈转换成一棵树来考虑，初始栈为空的时候假设我们有一个节点的树并且这个结点编号为，接下来入栈就是当前节点新开辟一个儿子，出栈就是回到父亲，一直这样操作一个合理的出栈入栈顺序就会生成个节点。我们要做的就是给生成的个节点打上颜色，让每个点到的路径上构成的颜色序列唯一。

那么就很明显，我们每次让任意一个节点它的儿子节点们颜色互不相同就可以了。

我们用的方式填颜色，把同层次的颜色先选上不一样种颜色，并且每种颜色减一后插回原来的序列中。

我们使用堆可以很好的维护上面的数据结构。

#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define pai pair<int, int>
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
#define debug(x) cout << #x << ":" << x << '\n'
typedef tuple<int, int> tup;
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op)    putchar(op); return; }    char F[40]; ll tmp = x > 0 ? x : -x;    if (x < 0)putchar('-');    int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';        tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]);    if (op)    putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;    while (b) { if (b & 1)    ans *= a;        b >>= 1;        a *= a; }    return ans; }    ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INF64 = 0x3f3f3f3f3f3f3f3f;

const int N = 2e6 + 7;
ll n, m;
int p[N];
char s[N];

// (()()()()()())


multiset<pai, greater<pai>> st;
vector<int> len[N];

int a[N];

int solve() {
    n = read();
    scanf("%s", s + 1);
    unordered_map<int, int> cnt;
    for (int i = 1; i <= n; ++i)    p[i] = read(), ++cnt[p[i]];

    for (int i = 1; i <= n; ++i) {
        if (cnt.count(i)) {
            st.insert({ cnt[i],i });
        }
    }

    int now = 0;
    for (int i = 1; i <= 2 * n; ++i) {
        if (s[i] == '(') {
            ++now;
            len[now].push_back(i);
        }
        else --now;
    }

    for (int i = 1; i <= n; ++i) {
        int sz = len[i].size();
        if (sz) {
            multiset<pai, greater<pai>> tmp;
            for (int j = 1; j <= sz; ++j) {
                if (st.empty()) {
                    puts("NO");
                    exit(0);
                }
                auto it = *st.begin();
                if (it.first == 0) {
                    puts("NO");
                    exit(0);
                }
                st.erase(st.find(it));
                tmp.insert(it);
            }
            for (auto& pos : len[i]) {
                auto it = *tmp.begin();
                a[pos] = it.second;
                tmp.erase(tmp.find(it));
                st.insert({ it.first - 1, it.second });
            }
        }
    }


    return 1;
}

signed main() {
    //int T = read(); for (int i = 1; i <= T; ++i)
    {
        //solve();
        cout << (solve() ? "YES" : "NO") << endl;
        stack<int> stk;
        for (int i = 1; i <= 2 * n; ++i) {
            if (s[i] == '(')    print(a[i], 32);
        }
        puts("");
    }
    return 0;
}