Submission #1382860

---

Source Code Expand

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <cassert>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>

using namespace std;

#define f first
#define s second
#define pb push_back
#define pp pop_back
#define mp make_pair
#define ll long long
#define ld double
#define ull unsigned long long
#define PI pair < int, int > 

const int N = 512 * 512;
const int M = 123;
const ld Pi = acos(-1);
const ll Inf = 1e18;
const int inf = 1e9;
const int mod = 1e9 + 7;
const int Sz = 501;
const int MOD = 1e9 + 7;

void add(int &a, int b) {
  a += b;
  if (a >= mod) a -= mod;
}
int mult(int a, int b) {
  return 1ll * a * b % mod;
}
int sum(int a, int b) {
  add(a, b);
  return a;
}

int n, a[N], x[N], cnt[N], id[N], num[N], C[N];
pair < int, int > arr[N];

void solve() { 
  cin >> n;
  for (int i = 1;i <= n;i++) {
    cin >> x[i];
    if (cnt[x[i]]) {
      cout << "No\n";
      return;
    }
    num[i] = n;
    cnt[x[i]] = i;
  }
  for (int i = 1, used = 0;i <= n * n;i++) {
    if (cnt[i]) {
      if (i - used < cnt[i]) {
        cout << "No\n";
        return;
      }
      used += cnt[i];
    }
  }
  queue < int > q;
  for (int i = 1;i <= n * n;i++) {
    if (cnt[i]) {
      int x = cnt[i];
      a[i] = x;
      num[x]--;
      for (int it = 1;it < x;it++) {
        a[q.front()] = x;
        q.pop();
        num[x]--;
      }
    } else {
      q.push(i);
    }
  }
  for (int i = 1;i <= n;i++) arr[i] = {x[i], i};
  sort(arr + 1, arr + n + 1);
  reverse(arr + 1, arr + n + 1);
  int ptr = 1;
  for (int i = n * n;i;i--) {
    if (!a[i]) {
      while(num[arr[ptr].s] == 0) ptr++;
      a[i] = arr[ptr].s;
      num[arr[ptr].s]--;
    }
  }
  for (int i = 1;i <= n * n;i++) {
    C[a[i]]++;
    if (cnt[i] > 0) {
      int x = cnt[i];
      if (C[x] != x) {
        cout << "No\n";
        return;
      }
    }
  }
  cout << "Yes\n";
  for (int i = 1, ptr = 0;i <= n * n;i++) {
    cout << a[i] << " ";
  }
  cout << endl;
}
  
int main() {
  #ifdef wws
   freopen("in", "r", stdin);
   // freopen("in", "w", stdout);
  #endif 
  ios_base::sync_with_stdio(0);
  int tt = 1; 
  while(tt--) solve();
  return 0;
}

Submission Info

Judge Result