fork download
copy 
  1. #include <bits/stdc++.h>
  2. #pragma GCC optimize ("O3")
  3. #define lesgooo ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
  4. #define lop(i, n) for(ll i = 0; i < (ll)n; i++)
  5. #define alop(i,v) for(auto &i: v)
  6. #define ll long long
  7. #define ld long double
  8. //#define endl '\n'
  9. #define all(v) v.begin(),v.end()
  10. #define mem(dp, x) memset(dp, x, sizeof(dp))
  11. #define sq(x) ((x) * (x))
  12. #define pb push_back
  13. using namespace std;
  14. const ll mod = 1e9 + 7;
  15. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  16.  
  17. ll random(ll l, ll r) {
  18.     return uniform_int_distribution<ll>(l, r)(rng);
  19. }
  20.  
  21. typedef unsigned long long ull;
  22.  
  23. ull modmul(ull a, ull b, ull M) {
  24.     ull ret = a * b - M * ull(1.L / M * a * b);
  25.     return ret + M * (ret < 0) - M * (ret >= (ll)M);
  26. }
  27. ull modpow(ull b, ull e, ull mod) {
  28.     ull ans = 1;
  29.     for (;e; b = modmul(b, b, mod), e /= 2) {
  30.         if (e & 1) ans = modmul(ans, b, mod);
  31.     }
  32.     return ans;
  33.  
  34. }
  35. void dfs(int node, vector<pair<int,int>>&edges,  vector<vector<int>>&adj ) {
  36.     for (auto x:adj[node]) {
  37.         edges.push_back({node,x});
  38.         dfs(x,edges,adj);
  39.     }
  40. }
  41. int main() {
  42.     ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  43.  
  44.     ll t; cin >> t;
  45.     while (t--) {
  46.         ll n; cin >> n;
  47.         vector<int>m(n);
  48.         priority_queue<pair<int,int>> pq;
  49.         for (int i = 0;i<n;i++) {
  50.             cin>>m[i];
  51.             if (m[i] > 0) pq.push({m[i],i});
  52.         }
  53.         vector<vector<int>>adj(n);
  54.         vector<int>par(n);
  55.         int rt = -1;
  56.         int prev = -1;
  57.         while (!pq.empty()) {
  58.             pair<int,int> pr = pq.top();
  59.             pq.pop();
  60.             if (rt == -1) {rt =pr.second; prev = rt; par[rt] = -1;}
  61.             else {
  62.                 int nd = pr.second;
  63.                 par[nd] = prev;
  64.                 adj[prev].push_back(nd);
  65.                 prev = nd;
  66.             }
  67.         }
  68.         vector<bool>vis(n,0);
  69.         int st = 0;
  70.         int node = prev;
  71.         while (node != -1) {
  72.             for (int i = st; i<m[node];i++) {
  73.                 if (i == node) {vis[i] = 1; continue;}
  74.                 if (!vis[i]) {
  75.                     adj[node].push_back(i);
  76.                     par[i] = node;
  77.                     vis[i] = 1;
  78.                 }
  79.             }
  80.             st = m[node];
  81.             node = par[node];
  82.         }
  83.         cout<<rt<<'\n';
  84.         vector<pair<int,int>>edges;
  85.         dfs(rt,edges,adj);
  86.         for (auto x:edges) cout<<x.first<<" "<<x.second<<'\n';
  87.     }
  88. }
  89.  
  90.  
Success #stdin #stdout 0.01s 5268KB
comments (?)
stdin
copy 
1
2
2 0
stdout
copy 
0
0 1
https://ideone.com/ZxTUX9
language:
C++ (gcc 8.3)
created:
16 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!