Submission #134652

#	Time	Username	Problem	Language	Result	Execution time	Memory
134652		Muhammetali	Detecting Molecules (IOI16_molecules)	C++11	100 / 100	139 ms	14496 KiB

molecules

#include <algorithm>
#include <vector>
#include <set>
 
#include "molecules.h" //Including grader file
 
using ll = long long; //A little alias to save time.
 
using namespace std;
 
vector<int> find_subset(int l, int u, vector<int> w) {
    int n = w.size();
    vector<pair<int, int> > weight(n);
    for (int i = 0; i < n; i++) {
        weight[i] = { w[i], i }; //Storing initial index for the output.
    }
    sort(weight.begin(), weight.end());
    ll cur_sum = 0;
    int bad_i;
    for (bad_i = 0; bad_i < n; bad_i++) { //Locating first bad length
        cur_sum += weight[bad_i].first;
        if (cur_sum > u)
            break;
    }
    if (bad_i == 0) //no solution
    {
        return vector<int>();
    }
    set<pair<int, int> > picked, remain;
    ll curpicked = 0;
    for (int i = 0; i < bad_i; i++) { 
        picked.insert(weight[i]);
        curpicked += weight[i].first;
    }
    for (int i = bad_i; i < n; i++) {
        remain.insert(weight[i]);
    }
    while (curpicked < l && !remain.empty()) {
        if (picked.begin()->first >= remain.rbegin()->first) //Nothing left to swap
            break;
        //Swap the lowest and the highest elements.
        curpicked += remain.rbegin()->first - picked.begin()->first;
        auto el1 = *picked.begin();
        auto el2 = *remain.rbegin();
        picked.erase(el1);
        picked.insert(el2);
        remain.erase(el2);
    }
    if (curpicked < l){ //no solution 
        return vector<int>();
    }
    vector<int> answer;
    for (auto el : picked)
        answer.push_back(el.second);
    return answer;
}

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