Atcoder Grand Contest 008 D. K-th K

Atcoder Grand Contest 008 D. K-th K

D: K-th K - AtCoder Grand Contest 008 | AtCoder

解法

位置が確定しているものを左から順に確定させ、その数の左側に置かなければいけない個数を空いている場所に左詰めで書いていく。これができない場合は不可能。

位置が確定しているものをすべて書くことができたら、次にそれらの数の右側に置かなければいけない個数を左詰めで書いていく。これができない場合も不可能。

これらはどこまで書き込んだを示すポインタを一つ持つことで実装できる。$\ O(n^2)\ $。

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

#define all(x) x.begin(), x.end()

int main() {
        int n;
        scanf("%d", &n);
        vector<pair<int, int>> x(n);
        for (int i = 0; i < n; i ++) { 
                scanf(&quot;%d&quot;, &x[i].first);
                x[i].first --;
                x[i].second = i + 1;
        }
        sort(all(x));
        int sp = 0;
        vector<int> ans(n * n, -1);
        for (int i = 0; i < n; i ++) {
                ans[x[i].first] = x[i].second;
                int add = x[i].second - 1;
                while (add --) {
                        if (ans[sp] != -1) add ++;
                        else ans[sp] = x[i].second;
                        sp ++;
                        if (sp > x[i].first) return !puts(&quot;No&quot;);
                }
        }
        for (int i = 0; i < n; i ++) {
                if (ans[sp] == -1 && sp < x[i].first) return !puts(&quot;No&quot;);
                int add = n - x[i].second;
                while (add --) {
                        if (ans[sp] != -1) add ++;
                        else ans[sp] = x[i].second;
                        sp ++;
                }
        }
        puts(&quot;Yes&quot;);
        for (int i = 0; i < n * n; i ++) cout << ans[i] << (i == n * n - 1 ? '\n' : ' ');
        return 0;   
}