Submission #1042556

---

Source Code Expand

// Template {{{
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
using namespace std;
typedef long long LL;

#ifdef LOCAL
#include "contest.h"
#else
#define dump(x) 
#endif

const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
inline bool valid(int x, int w) { return 0 <= x && x < w; }

void iostream_init() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.setf(ios::fixed);
    cout.precision(12);
}
//}}}

int N;
vector<int> solve() {
    vector<int> X(N);
    REP(i, N) cin >> X[i];
    REP(i, N) X[i]--;

    map<int, int> event;
    REP(i, N) event[ X[i] ] = i;

    REP(i, N) if (event[ X[i] ] != i) {
        return vector<int>(); // NG
    }

    typedef pair<int, int> P;
    priority_queue<P, vector<P>, greater<P>> before;
    REP(i, N) {
        if(i != 0) {
            before.push(P(X[i], i));
        }
    }

    queue<int> after;
    vector<int> count(N);

    vector<int> answer;
    auto insert = [&](int x) {
        //cout << "insert " << x+1 << endl;
        answer.push_back(x+1);
        count[x]++;
    };

    REP(i, N * N) {
        //cout << i << endl;
        if(event.count(i)) {
            //cout << "event" << event[i] << endl;
            const int x = event[i];
            if(count[x] != x) {
                //cout << "count " << x << " " << count[x] << " is not " << x << endl;
                return vector<int>(); // NG
            }
            insert(x);
            REP(_, N - count[x]) {
                after.push(x);
            }
        } else {
            if(before.empty()) {
                if(after.empty()) {
                    //cout << "before and after" << endl;
                    return vector<int>(); // NG
                } else {
                    int x = after.front(); after.pop();
                    insert(x);
                }
            } else {
                auto p = before.top();
                int x = p.second;
                insert(x);
                if(count[x] < x) {
                    // remain
                } else {
                    before.pop();
                }
            }
        }
    }

    return answer;
}

int main(){
    iostream_init();
    while(cin >> N) {
        auto res = solve();
        if(res.size() != 0) {
            cout << "Yes" << endl;
            REP(i, res.size()) {
                cout << res[i];
                if(i+1 != res.size()) cout << " ";
                else cout << endl;
            }
        } else {
            cout << "No" << endl;
        }
    }
    return 0;
}

Submission Info

Judge Result