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

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>

using namespace std;

int main() {
    int n, l, u;
    cin >> n >> l >> u;
    vector<pair<int, int>> w(n);
    for (int i = 0; i < n; ++i) cin >> w[i].first, w[i].second = i;
    sort(w.begin(), w.end());

    // possible with k molecules iff sum of biggest k >= l
    // and sum of smallest k <= u
    int k = 0;
    long long sumBig = 0, sumSmall = 0;
    while (k < n && sumBig < l) {
        sumSmall += w[k].first;
        sumBig += w[n-++k].first;
    }

    if (sumBig < l || sumSmall > u) {
        cout << 0 << endl;
        return 0;
    }

    long long sum = sumSmall;
    int changed = 0;
    while (sum < l) {
        assert(n-1-changed >= k);
        sum += w[n-1-changed].first - w[changed].first;
        ++changed;
    }

    cout << k << endl;
    for (int i = changed; i < k; ++i) cout << w[i].second << ' ';
    for (int i = n-changed; i < n; ++i) cout << w[i].second << ' ';
    cout << endl;
    return 0;
}