【精進7】AGC008-D

貪欲に決めていく

問題

D - K-th K
長さ$N$列の数列$x$が与えられる。$1\le i \le N$を満たす各$i$をちょうど$N$回ずつ含む長さ$N^2$の数列であって、任意の$1\le i\le N$について$i$が$i$番目に現れるインデックスが$x_i$となるようなものが存在するならば$1$つ出力せよ。

解法

答えとなる配列を用意しておき、配列の値がまだ決まっていないインデックスをsetで持っておく。$x_i$の昇順に見ていく。$x_i$までに未定のインデックスが$i-1$個なければ構築は不可能である。存在する場合、先頭の$i-1$個のインデックスの値を$i$に決定してしまってよい。また$インデックスx_i$の値は$i$に決定する。これを一通り行う。これで$x_i$以前に$i$を$i$個配置できたので次に$x_i$より後ろに$i$を$N-i$個配置していく。これも同様に$x_i$の昇順に決めていけば良い。未定の最小のインデックスが$x_i$以下になった場合構築は不可能である。

#include "template.hpp"
void solve() {
    LL(n);
    vl x(n);
    rep(i, n) {
        input(x[i]);
        --x[i];
    }
    vl ord(n);
    iota(all(ord), 0);
    sort(all(ord), [&x](ll i, ll j) { return x[i] < x[j]; });
    vl ans(n * n, -1);
    set<ll> unused;
    rep(i, n * n) unused.insert(i);
    vl sf;
    for(auto &i : ord) {
        rep(_, i) {
            auto itr = unused.begin();
            ans[*itr] = i;
            unused.erase(unused.begin());
        }
        if(unused.count(x[i]) == 0) {
            print("No");
            return;
        }
        ans[x[i]] = i;
        unused.erase(x[i]);
        rep(_, n - i - 1) sf.push_back(i);
    }
    for(auto &i : sf) {
        auto itr = unused.begin();
        if(*itr < x[i]) {
            print("No");
            return;
        }
        ans[*itr] = i;
        unused.erase(itr);
    }
    assert(unused.empty());
    print("Yes");
    for(auto &i : ans)
        cout << i + 1 << " ";
    print();
}

int main() {
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    cout << std::setprecision(16);
    int t = 1;
    rep(_, t) {
        solve();
    }
}