Submission #725785

#	Time	Username	Problem	Language	Result	Execution time	Memory
725785		hoainiem	Detecting Molecules (IOI16_molecules)	C++14	100 / 100	125 ms	12864 KiB

molecules

#include "molecules.h"
#include<bits/stdc++.h>
using namespace std;
multiset<int>u;
multiset<int>::iterator it;
long long sum = 0;
priority_queue<int, vector<int>, greater<int> >v;
std::vector<int> find_subset(int l, int r, std::vector<int> w) {
    for (int tmp : w)
        v.push(tmp);
    while (!v.empty() && sum < l){
        int tmp = v.top();
        v.pop();
        if (sum + tmp <= r){
            sum += tmp;
            u.insert(tmp);
            continue;
        }
        it = u.lower_bound(tmp);
        if (it != u.begin()){
            it--;
            sum += tmp - *it;
            v.push(*it);
            u.erase(it);
            u.insert(tmp);
        }
    }
    if (sum < l)
        return std::vector<int>();
    vector<int>res;
    for (int i = 0; i < (int)w.size(); i++)
        if (u.find(w[i]) != u.end()){
            res.push_back(i);
            u.erase(u.find(w[i]));
        }
    return res;
}

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