Submission #500422

#	Time	Username	Problem	Language	Result	Execution time	Memory
500422		CatalinT	Detecting Molecules (IOI16_molecules)	C++17	0 / 100	0 ms	204 KiB

molecules

#include <vector>
#include <iostream>
#include <cassert>
#include <algorithm>
#include <numeric>
#include <iostream>

using namespace std;

using int64 = long long;
auto impossible = vector<int> {};

vector<int> find_subset(int l, int u, vector<int> w) {
    vector<int> sol;
    int64 res = 0;

    int N = w.size();
    vector<int> order(N);

    iota(order.begin(), order.end(), 0);

    sort(order.begin(), order.end(), [&](int a, int b){
        return w[a] < w[b];
    });

    for (auto i : order) {
        res += w[i];
        sol.push_back(i);
        if (res >= l)
            break;
    }

    if (res <= u)
        return sol;
    else if (res < l)
        return impossible;

    // cerr << "here: " << res << "\n";

    int at = 0;
    while(at < sol.size()) {
        res -= w[sol[at]];
        at++;
        if (res >= l && res <= u) {
            return vector<int>(sol.begin() + at, sol.end());
        } else if (res < l) {
            return impossible;
        }
    }

    return impossible;
}

// void debug(vector<int> v) {
//     for (auto x : v) cerr << x << " "; cerr << "\n";
// }

// int main() {
//     debug(find_subset(15, 17, {6, 8, 8, 7}));
//     debug(find_subset(14, 15, {5, 5, 6, 6}));
//     debug(find_subset(10, 20, {15, 17, 16, 18}));
//     return 0;
// }

Compilation message (stderr)

molecules.cpp: In function 'std::vector<int> find_subset(int, int, std::vector<int>)':
molecules.cpp:41:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     while(at < sol.size()) {
      |           ~~~^~~~~~~~~~~~

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