Submission #840208

#	Time	Username	Problem	Language	Result	Execution time	Memory
840208		sleepntsheep	Detecting Molecules (IOI16_molecules)	C++17	100 / 100	49 ms	4552 KiB

molecules

#include <algorithm>
#include <vector>
#include <utility>
#include <set>
#include <deque>

std::vector<int> find_subset(int l, int u, std::vector<int> w)
{
    int n = w.size(), i;
    std::vector<int> rvcord(n);
    {
        std::vector<std::pair<int, int>> incw(n);
        for (int i = 0; i < n; ++i) incw[i] = {w[i], i};
        std::sort(incw.begin(), incw.end());
        for (int i = 0; i < n; ++i) rvcord[i] = incw[i].second;
        std::sort(w.begin(), w.end());
    }
    long long s = 0;
    std::deque<int> lo; std::vector<int> hi;
    for (i = 0; i < n; ++i)
        if (s + w[i] <= u) s += w[i], lo.push_back(i);
        else break;
    for (int j = i; j < n; ++j) hi.push_back(j);
    while (s < l && lo.size() && hi.size())
    {
        long long d = w[hi.back()] - w[lo.front()];
        if (d <= 0) break;
        s += d;
        lo.push_back(hi.back());
        hi.pop_back(); lo.pop_front(); 
    }
    if (s < l) return std::vector<int>();
    std::vector<int> result(lo.size());
    for (int i = 0; i < lo.size(); ++i) result[i] = rvcord[lo[i]];
    return result;
}

Compilation message (stderr)

molecules.cpp: In function 'std::vector<int> find_subset(int, int, std::vector<int>)':
molecules.cpp:34:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     for (int i = 0; i < lo.size(); ++i) result[i] = rvcord[lo[i]];
      |                     ~~^~~~~~~~~~~

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