Submission #840190

#	Time	Username	Problem	Language	Result	Execution time	Memory
840190		sleepntsheep	Detecting Molecules (IOI16_molecules)	C++17	0 / 100	1 ms	212 KiB

molecules

#include <algorithm>
#include <set>
#include <deque>

std::vector<int> find_subset(int l, int u, std::vector<int> w)
{
    std::sort(w.begin(), w.end());
    int s = 0, i;
    std::multiset<int> sub;
    std::deque<int> lo, hi;
    for (i = 0; i < (int)w.size(); ++i)
        if (s + w[i] < l) s += w[i], lo.push_back(i), sub.insert(i);
        else break;
    for (int j = i; j < (int)w.size(); ++j) hi.push_front(j);
    while (s < l && lo.size() && hi.size())
    {
        int d = w[hi.front()] - w[lo.front()];
        if (d <= 0) break;
        s += d;
        sub.erase(sub.find(lo.front())); sub.insert(hi.front());
        lo.push_back(hi.front());
        hi.pop_front(); lo.pop_front(); 
    }
    if (s < l) return std::vector<int>();
    return std::vector(lo.begin(), lo.end());
}

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