fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define all(x) (x).begin(), (x).end()
  3. #define ll long long
  4. using namespace std;
  5.  
  6. struct DSU {
  7.     vector<int> p;
  8.     void init(int n) { p.assign(n + 1, 0); iota(p.begin(), p.end(), 0); }
  9.     int find(int x) { while (p[x] != x) { p[x] = p[p[x]]; x = p[x]; } return x; }
  10.     void unite(int a, int b) { p[find(a)] = find(b); }
  11. };
  12.  
  13. int main() {
  14.     ios_base::sync_with_stdio(false);
  15.     cin.tie(nullptr);
  16.  
  17.     int t;
  18.     cin >> t;
  19.     while (t--) {
  20.         int n;
  21.         cin >> n;
  22.         vector<int> a(n + 1);
  23.         for (int i = 1; i <= n; ++i) cin >> a[i];
  24.  
  25.         if (n == 1) {
  26.             cout << (a[1] == 1 ? "Yes\n1\n" : "No\n");
  27.             continue;
  28.         }
  29.  
  30.         vector<int> order(n);
  31.         iota(order.begin(), order.end(), 1);
  32.         sort(order.begin(), order.end(), [&](int x, int y){
  33.             if (a[x] != a[y]) return a[x] > a[y];
  34.             return x < y;
  35.         });
  36.  
  37.         set<int> freeIdx;
  38.         for (int i = 1; i <= n; ++i) freeIdx.insert(i);
  39.  
  40.         DSU dsu;
  41.         dsu.init(n);
  42.  
  43.         vector<int> succ(n + 1, 0);
  44.         bool ok = true;
  45.  
  46.         for (int k = 0; k < n; ++k) {
  47.             int v = order[k];
  48.             bool last = (k == n - 1);
  49.  
  50.             auto it = freeIdx.lower_bound(a[v]);
  51.             int chosen = -1;
  52.  
  53.             while (it != freeIdx.end()) {
  54.                 int w = *it;
  55.                 if (last) { chosen = w; break; }
  56.                 if (dsu.find(v) != dsu.find(w)) { chosen = w; break; }
  57.                 ++it;
  58.             }
  59.  
  60.             if (chosen == -1) { ok = false; break; }
  61.             succ[v] = chosen;
  62.             dsu.unite(v, chosen);
  63.             freeIdx.erase(chosen);
  64.         }
  65.  
  66.         if (!ok) { cout << "No\n"; continue; }
  67.  
  68.         vector<int> path;
  69.         path.reserve(n);
  70.         vector<char> vis(n + 1, 0);
  71.         int cur = 1;
  72.         bool cycleOk = true;
  73.         for (int i = 0; i < n; ++i) {
  74.             if (vis[cur]) { cycleOk = false; break; }
  75.             vis[cur] = 1;
  76.             path.push_back(cur);
  77.             cur = succ[cur];
  78.         }
  79.  
  80.         if (!cycleOk || cur != 1) { cout << "No\n"; continue; }
  81.  
  82.         cout << "Yes\n";
  83.         for (int i = 0; i < n; ++i) {
  84.             cout << path[i] << " \n"[i + 1 == n];
  85.         }
  86.     }
  87.  
  88.     return 0;
  89. }
  90.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
5
7
1 3 6 3 2 1 5
9
4 2 9 8 5 8 5 7 9
8
3 4 4 5 6 1 8 2
1
1
5
5 4 2 5 5
stdout
copy 
Yes
1 4 7 5 2 3 6
No
Yes
1 3 7 8 2 4 5 6
Yes
1
No
https://ideone.com/rpzCjK
language:
C++ (gcc 8.3)
created:
12 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!