Submission #289643

#	Time	Username	Problem	Language	Result	Execution time	Memory
289643		peti1234	Detecting Molecules (IOI16_molecules)	C++17	100 / 100	64 ms	8300 KiB

molecules

#include <bits/stdc++.h>

using namespace std;
long long sum, n, kezd=-1, veg;
vector<pair<long long, int> >sz;
vector<int> ans;
void add(int a, int b) {
    sum+=b*sz[a].first;
}
vector<int> find_subset(int a, int b, vector<int> w) {
    n=w.size(), veg=n;
    for (int i=0; i<n; i++) {
        sz.push_back({w[i], i});
    }
    sort(sz.rbegin(), sz.rend());
    while(kezd+1<n && sum<a) {
        kezd++;
        add(kezd, 1);
    }
    if (a<=sum && sum<=b) {
        for (int i=0; i<=kezd; i++) ans.push_back(sz[i].second);
        return ans;
    }
    while(kezd>=0 && sum>b) {
        add(kezd, -1), kezd--;
        veg--, add(veg, 1);
        if (a<=sum && sum<=b) {
            for (int i=0; i<=kezd; i++) ans.push_back(sz[i].second);
            for (int i=veg; i<n; i++) ans.push_back(sz[i].second);
            return ans;
        }
    }
    return ans;
}

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