fork download
copy 
  1. #include <iostream>
  2. #include <fstream>
  3. #include <vector>
  4. #include <set>
  5. #include <algorithm>
  6. #include <cassert>
  7. #include <ctime>
  8. #include <random>
  9.  
  10. using namespace std;
  11.  
  12. const int INF = 1e9;
  13.  
  14. int a[1000000 + 5];
  15.  
  16. vector < pair < int, int > > ans;
  17.  
  18.  
  19. const int array_size = 1e5 + 5;
  20. int t[array_size * 4], lazy[array_size * 4];
  21.  
  22. void push(int v, int tl, int tr)
  23. {
  24.     t[v] += lazy[v] * (tr - tl + 1);
  25.     if(tl != tr)
  26.     {
  27.         lazy[v << 1] += lazy[v];
  28.         lazy[(v << 1) + 1] += lazy[v];
  29.     }
  30.     lazy[v] = 0;
  31.     return;
  32. }
  33.  
  34. void build(int v, int tl, int tr)
  35. {
  36.     if(tl == tr)
  37.     {
  38.         t[v] = a[tl];
  39.         return;
  40.     }
  41.     int tm = (tl + tr) >> 1;
  42.     build(v << 1, tl, tm);
  43.     build((v << 1) + 1, tm + 1, tr);
  44.     t[v] = t[v << 1] + t[(v << 1) + 1];
  45.     return;
  46. }
  47.  
  48. void update(int v, int tl, int tr, int l, int r, int add)
  49. {
  50.     if(l > r)
  51.         return;
  52.     if(l == tl && r == tr)
  53.     {
  54.         lazy[v] += add;
  55.         push(v, tl, tr);
  56.         return;
  57.     }
  58.     push(v, tl, tr);
  59.     int tm = (tl + tr) >> 1;
  60.     update(v << 1, tl, tm, l, min(r, tm), add);
  61.     update((v << 1) + 1, tm + 1, tr, max(l, tm + 1), r, add);
  62.     t[v] = t[v << 1] + t[(v << 1) + 1];
  63.     return;
  64. }
  65.  
  66. int find_sum(int v, int tl, int tr, int l, int r)
  67. {
  68.     if(l > r)
  69.         return 0;
  70.     push(v, tl, tr);
  71.     if(l == tl && r == tr)
  72.         return t[v];
  73.     int tm = (tl + tr) >> 1;
  74.     return find_sum(v << 1, tl, tm, l, min(r, tm)) + find_sum((v << 1) + 1, tm + 1, tr, max(l, tm + 1), r);
  75. }
  76.  
  77. int intersection(int k1, int b1, int k2, int b2)
  78. {
  79.     int dk = k1 - k2;
  80.     int db = b2 - b1;
  81.     return db / dk + (db / dk > 0 && abs(db) % abs(dk) > 0);
  82. }
  83.  
  84. struct ConvexHullTrick
  85. {
  86.     int sz = 0;
  87.     vector < int > k, b, fr;
  88.     void push(int newk, int newb)
  89.     {
  90.         while(sz)
  91.         {
  92.             if(k.back() == newk && b.back() > newb || k.back() != newk && fr.back() >= intersection(k.back(), b.back(), newk, newb))
  93.             {
  94.                 sz--;
  95.                 k.pop_back();
  96.                 b.pop_back();
  97.                 fr.pop_back();
  98.                 continue;
  99.             }
  100.             break;
  101.         }
  102.         if(sz && k.back() == newk)
  103.             return;
  104.         fr.push_back((sz ? intersection(k.back(), b.back(), newk, newb) : -INF));
  105.         k.push_back(newk);
  106.         b.push_back(newb);
  107.         sz++;
  108.     }
  109.     int convex(int x)
  110.     {
  111.         if(!sz)
  112.             return INF;
  113.         int j = upper_bound(fr.begin(), fr.end(), x) - fr.begin() - 1;
  114.         return k[j] * x + b[j];
  115.     }
  116. };
  117.  
  118. int main()
  119. {
  120.     ios_base::sync_with_stdio(0);
  121.     cin.tie(0);
  122.     int t;
  123.     cin >> t;
  124.     while (t--)
  125.     {
  126.         int n;
  127.         cin >> n;
  128.         for (int i = 0; i < n; i++)
  129.             cin >> a[i];
  130.         ans.clear();
  131.         for (int i = 0; i < n; i++)
  132.         {
  133.             int pos = (n - 1 + i) % n;
  134.             int j = (pos - 4 + n) % n;
  135.             int cnt = 0;
  136.             while (a[pos] > 0)
  137.             {
  138.                 cnt++;
  139.                 if (cnt == n * 2) break;
  140.                 if (a[j] > 0 && pos != j)
  141.                 {
  142.                     ans.push_back({pos + 1, j + 1});
  143.                     a[pos]--;
  144.                     a[j]--;
  145.                 }
  146.                 j--;
  147.                 j += n;
  148.                 j %= n;
  149.             }
  150.         }
  151.         cout << ans.size() << '\n';
  152.         for (auto i : ans)
  153.             cout << i.first << " " << i.second << '\n';
  154.     }
  155. }
  156.  
Success #stdin #stdout 0.01s 5508KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
0
https://ideone.com/yPMiNS
language:
C++ (gcc 8.3)
created:
3 years 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!