Submission #65963

#	Time	Username	Problem	Language	Result	Execution time	Memory
65963		gs13068	Detecting Molecules (IOI16_molecules)	C++17	100 / 100	94 ms	9736 KiB

molecules

#include "molecules.h"
#include <algorithm>
 
using namespace std;
 
pair<int, int> a[200002];
 
std::vector<int> find_subset(int l, int u, std::vector<int> w) {
    vector<int> r;
    long long L, U;
    int i, j, k, n;
    n = w.size();
    for (i = 0; i < n; i++) {
        a[i].first = w[i];
        a[i].second = i;
    }
    sort(a, a + n);
    L = U = 0;
    for (i = 0; i < n; i++) {
        L += a[i].first;
        U += a[n - i - 1].first;
        if (L <= u && l <= U) break;
    }
    if (i == n) return r;
    for (j = 0; L < l; j++) {
        L -= a[j].first;
        L += a[j + i + 1].first;
    }
    for (k = 0; k <= i; k++) r.push_back(a[j + k].second);
    return r;
}

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