Submission #510124

#	Time	Username	Problem	Language	Result	Execution time	Memory
510124		tabr	Detecting Molecules (IOI16_molecules)	C++17	100 / 100	45 ms	4772 KiB

molecules

#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif

vector<int> find_subset(int l, int u, vector<int> w) {
    int n = (int) w.size();
    vector<int> order(n);
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [&](int i, int j) { return w[i] < w[j]; });
    long long lo = 0;
    long long hi = 0;
    for (int i = 1; i <= n; i++) {
        lo += w[order[i - 1]];
        hi += w[order[n - i]];
        if (l <= lo && lo <= u) {
            vector<int> res;
            for (int j = 0; j < i; j++) {
                res.emplace_back(order[j]);
            }
            return res;
        } else if (l <= hi && hi <= u) {
            vector<int> res;
            for (int j = 0; j < i; j++) {
                res.emplace_back(order[n - 1 - j]);
            }
            return res;
        } else if (lo < l && u < hi) {
            vector<int> res;
            for (int j = 0; j < i; j++) {
                res.emplace_back(order[j]);
            }
            long long sum = lo;
            for (int j = i - 1; j >= 0; j--) {
                if (sum - w[order[j]] + w[order[n + j - i]] < l) {
                    res[j] = order[n + j - i];
                    sum -= w[order[j]];
                    sum += w[order[n + j - i]];
                    continue;
                }
                sum -= w[order[j]];
                for (int k = j; k <= n + j - i; k++) {
                    if (sum + w[order[k]] >= l) {
                        res[j] = order[k];
                        break;
                    }
                }
                break;
            }
            return res;
        }
    }
    return vector<int>();
}

#ifdef tabr
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    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;
}
#endif

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