fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MAX_N = 1e6+5;
  5.  
  6. typedef long long ll;
  7. typedef pair<ll, int> PLI;
  8.  
  9. int n;
  10. ll k;
  11.  
  12. vector<PLI> ans[MAX_N];
  13.  
  14. int main() {
  15.     ios_base::sync_with_stdio(0);
  16.     cin.tie(0);
  17.  
  18.     set<PLI> secik;
  19.     ll suma = 0LL;
  20.  
  21.     cin >> n >> k;
  22.     for (int i = 0; i < n; i++) {
  23.         ll a;
  24.         cin >> a;
  25.         suma += a;
  26.         secik.insert(make_pair(a, i + 1));
  27.     }
  28.  
  29. 	if (suma > k*n) {
  30.         cout << "NIE\n";
  31.         return 0;
  32. 	}
  33.  
  34. 	int nr_pojemnika = 1;
  35.  
  36. 	while (!secik.empty()) {
  37.         PLI mini = *secik.begin();
  38.  
  39.         if (mini.first > k) {
  40.             break;
  41.         }
  42.  
  43.         PLI maxi = *prev(secik.end());
  44.  
  45.         if (maxi.first <= k) {
  46.             break;
  47.         }
  48.  
  49.         secik.erase(secik.begin());
  50.         secik.erase(prev(secik.end()));
  51.  
  52.         ll free_space = k - mini.first;
  53.         ll maxi_to_be_used = maxi.first - free_space;
  54.         secik.insert(make_pair(maxi_to_be_used, maxi.second));
  55.  
  56.         ans[nr_pojemnika].push_back(mini);
  57.         ans[nr_pojemnika].push_back(make_pair(free_space, maxi.second));
  58.  
  59.         nr_pojemnika++;
  60. 	}
  61.  
  62. 	while (!secik.empty()) {
  63.         PLI mini = *secik.begin();
  64.         ans[nr_pojemnika].push_back(mini);
  65.         secik.erase(secik.begin());
  66.         nr_pojemnika++;
  67. 	}
  68.  
  69. 	cout << "TAK\n";
  70. 	for (int i = 1; i <= n; i++) {
  71.         cout << ans[i].size() << ' ';
  72.  
  73.         for (auto p: ans[i]) {
  74.             cout << p.second << ' ' << p.first << ' ';
  75.         }
  76.         cout << '\n';
  77. 	}
  78.  
  79. 	return 0;
  80. }
  81.  
Success #stdin #stdout 0.01s 27036KB
comments (?)
stdin
copy 
5 6
1
11
3
4
2
stdout
copy 
TAK
2 1 1 2 5 
1 5 2 
1 3 3 
1 4 4 
1 2 6
https://ideone.com/0kRzUF
language:
C++14 (gcc 8.3)
created:
9 days 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!