Advertisement
Mirbek

Untitled

Mar 11th, 2023
746
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.08 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int main() {
  6.     int tt;
  7.     cin >> tt;
  8.     while (tt--) {
  9.         int n;
  10.         cin >> n;
  11.        
  12.         vector <int> deg(n + 1);
  13.         set <pair <int, int>> st;
  14.         for (int i = 1; i <= n; i++) {
  15.             cin >> deg[i];
  16.             if (deg[i] > 0)
  17.                 st.insert({deg[i], i});
  18.         }
  19.        
  20.         vector < pair <int, int> > edges;
  21.         while (!st.empty()) {
  22.             auto last = --st.end();
  23.             auto prev = --(--st.end());
  24.             edges.emplace_back(last->second, prev->second);
  25.             pair <int, int> p1 = *last, p2 = *prev;
  26.             st.erase(last);
  27.             st.erase(prev);
  28.             p1.first--;
  29.             p2.first--;
  30.             if (p1.first > 0)
  31.                 st.insert(p1);
  32.             if (p2.first > 0)
  33.                 st.insert(p2);
  34.            
  35.         }
  36.        
  37.         cout << edges.size() << endl;
  38.         for (int i = 0; i < edges.size(); i++) {
  39.             cout << edges[i].first << " " << edges[i].second << endl;
  40.         }
  41.     }
  42. }
  43.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement