fork download
copy 
  1. /* AUTHOR: TUAN ANH - BUI */
  2. // ~~ icebear ~~
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5.  
  6. typedef long long ll;
  7. typedef pair<ll, int> ii;
  8. typedef pair<int, ii> iii;
  9.  
  10. template<class X, class Y>
  11.     bool minimize(X &x, const Y &y) {
  12.         if (x > y) return x = y, true;
  13.         return false;
  14.     }
  15.  
  16. template<class X, class Y>
  17.     bool maximize(X &x, const Y &y) {
  18.         if (x < y) return x = y, true;
  19.         return false;
  20.     }
  21.  
  22. #define FOR(i,a,b) for(int i=(a); i<=(b); ++i)
  23. #define FORR(i,a,b) for(int i=(a); i>=(b); --i)
  24. #define REP(i, n) for(int i=0; i<(n); ++i)
  25. #define RED(i, n) for(int i=(n)-1; i>=0; --i)
  26. #define MASK(i) (1LL << (i))
  27. #define BIT(S, i) (((S) >> (i)) & 1)
  28. #define mp make_pair
  29. #define pb push_back
  30. #define fi first
  31. #define se second
  32. #define all(x) x.begin(), x.end()
  33. #define task "lock"
  34. /*  END OF TEMPLATE. ICEBEAR IS REALLY CUTE  */
  35.  
  36. const int MOD = 1e9 + 7;
  37. const int inf = (int)1e9 + 27092008;
  38. const ll INF  = (ll)1e18 + 27092008;
  39. const int N = 5e5 + 5;
  40. int n, k, a[N];
  41. ll sum;
  42. vector<vector<ll>> ans;
  43.  
  44. void init(void) {
  45.     cin >> n >> k;
  46.     FOR(i, 1, n) cin >> a[i], sum += a[i];
  47. }
  48.  
  49. void process(void) {
  50.     ll T = sum / k;
  51.     if (T < *max_element(a + 1, a + n + 1)) return void(cout << "-1");
  52.     multiset<ii> s;
  53.     FOR(i, 1, n) s.insert(mp(a[i], i));
  54.     while(!s.empty()) {
  55.         vector<ii> vec;
  56.         REP(i, k) {
  57.             vec.pb(*--s.end());
  58.             s.erase(--s.end());
  59.         }
  60.  
  61.         ll x = min(vec.back().first, T - (s.empty() ? 0ll : s.rbegin()->first));
  62.         T -= x;
  63.         vector<ll> cur(1, x);
  64.         for(auto [v, j] : vec) {
  65.             cur.push_back(j);
  66.             v -= x;
  67.             if (v > 0) s.insert(mp(v, j));
  68.         }
  69.         ans.push_back(cur);
  70.     }
  71.     cout << ans.size() << '\n';
  72.     for(auto S : ans) {
  73.         for(ll x : S) cout << x << ' ';
  74.         cout << '\n';
  75.     }
  76. }
  77.  
  78. int32_t main() {
  79.     ios_base::sync_with_stdio(0);
  80.     cin.tie(0); cout.tie(0);
  81.     if (fopen(task".inp", "r")) {
  82.         freopen(task".inp", "r", stdin);
  83.         freopen(task".out", "w", stdout);
  84.     }
  85.     int tc = 1;
  86. //    cin >> tc;
  87.     while(tc--) {
  88.         init();
  89.         process();
  90.     }
  91.     return 0;
  92. }
  93.  
  94.  
Success #stdin #stdout 0s 5312KB
comments (?)
stdin
copy 
5
1 2 1 3 1
stdout
copy 
5
3 3 
2 1 
1 4 
1 2 
0 5
https://ideone.com/cN5a97
language:
C++ (gcc 8.3)
created:
6 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!