Advertisement
erek1e

IOI '16 P1 - Detecting Molecules (Standard I/O)

Jun 16th, 2022
739
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.03 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <cassert>
  5.  
  6. using namespace std;
  7.  
  8. int main() {
  9.     int n, l, u;
  10.     cin >> n >> l >> u;
  11.     vector<pair<int, int>> w(n);
  12.     for (int i = 0; i < n; ++i) cin >> w[i].first, w[i].second = i;
  13.     sort(w.begin(), w.end());
  14.  
  15.     // possible with k molecules iff sum of biggest k >= l
  16.     // and sum of smallest k <= u
  17.     int k = 0;
  18.     long long sumBig = 0, sumSmall = 0;
  19.     while (k < n && sumBig < l) {
  20.         sumSmall += w[k].first;
  21.         sumBig += w[n-++k].first;
  22.     }
  23.    
  24.     if (sumBig < l || sumSmall > u) {
  25.         cout << 0 << endl;
  26.         return 0;
  27.     }
  28.  
  29.     long long sum = sumSmall;
  30.     int changed = 0;
  31.     while (sum < l) {
  32.         assert(n-1-changed >= k);
  33.         sum += w[n-1-changed].first - w[changed].first;
  34.         ++changed;
  35.     }
  36.  
  37.     cout << k << endl;
  38.     for (int i = changed; i < k; ++i) cout << w[i].second << ' ';
  39.     for (int i = n-changed; i < n; ++i) cout << w[i].second << ' ';
  40.     cout << endl;
  41.     return 0;
  42. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement