Submission #292478

#	Time	Username	Problem	Language	Result	Execution time	Memory
292478		Aldas25	Detecting Molecules (IOI16_molecules)	C++14	100 / 100	64 ms	8932 KiB

molecules

#include "molecules.h"
#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define REP(n) FOR(O, 1, (n))
#define f first
#define s second
#define pb push_back
typedef vector<int> vi;
typedef long long ll;

std::vector<int> find_subset(int l, int u, std::vector<int> w) {
    int n = (int)w.size();
    vi ret;
    vector<pair<ll, int>> srt;
    FOR(i, 0, n-1) srt.pb({w[i], i});
    sort(srt.begin(), srt.end());
    ll sum = 0ll;
    int le = 0;
    FOR(i, 0, n-1) {
        ll wi = srt[i].f;
        int id = srt[i].s;
        if (sum + wi <= u) {
            sum += wi;
            ret.pb(id);
        } else if (sum < l) {
            sum += wi;
            sum -= srt[le].f;
            le++;
            ret.pb(id);
        }

        //cout << " i = " << i << " id = "<< id << " w = " << wi << "  sum = " << sum << endl;

        if (l <= sum && sum <= u) {
            vi ans;
            FOR(j, le, (int)ret.size()-1)
                ans.pb(ret[j]);
            return ans;
        }

    }

    return {};
}

• Subtask 1: 9 / 9
• Subtask 2: 10 / 10
• Subtask 3: 12 / 12
• Subtask 4: 15 / 15
• Subtask 5: 23 / 23
• Subtask 6: 31 / 31