Submission #426370

#	Time	Username	Problem	Language	Result	Execution time	Memory
426370		timmyfeng	Detecting Molecules (IOI16_molecules)	C++17	100 / 100	66 ms	6340 KiB

molecules

#include <bits/stdc++.h>
using namespace std;

vector<int> find_subset(int l, int r, vector<int> w) {
    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];
    });

    vector<long long> prefix(n + 1);
    for (int i = 0; i < n; ++i) {
        prefix[i + 1] = prefix[i] + w[order[i]];
    }

    for (int i = 1; i <= n; ++i) {
        if (prefix[i] <= r && l <= prefix[n] - prefix[n - i]) {
            for (int j = 0; j + i <= n; ++j) {
                if (l <= prefix[j + i] - prefix[j] && prefix[j + i] - prefix[j] <= r) {
                    return vector<int>(order.begin() + j, order.begin() + j + i);
                }
            }
        }
    }

    return vector<int>();
}

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