Submission #1100476

#	Time	Username	Problem	Language	Result	Execution time	Memory
1100476		Zero_OP	Detecting Molecules (IOI16_molecules)	C++14	100 / 100	48 ms	7868 KiB

molecules

#include <bits/stdc++.h>

using namespace std;

vector<int> find_subset(int l, int u, vector<int> w){
    vector<pair<int, int>> ids;
    for(int i = 0; i < (int)w.size(); ++i){
        ids.push_back({w[i], i});
    }

    sort(ids.begin(), ids.end());
    int n = (int)w.size();
    vector<long long> pref(n);

    pref[0] = ids[0].first;
    for(int i = 1; i < n; ++i){
        pref[i] = pref[i - 1] + ids[i].first;
    }

    auto sum = [&](int i, int j) -> long long{
        return pref[j] - (i > 0 ? pref[i - 1] : 0);
    };

    for(int i = 0, j = 0; i < n; ++i){
        while(j < n && sum(i, j) < l) ++j;

        if(j == n) return {};
        if(sum(i, j) <= u){
            vector<int> res;
            for(int k = i; k <= j; ++k){
                res.push_back(ids[k].second);
            }
            return res;
        }
    }

    return {};
}

#ifdef LOCAL
int main(){
    vector<int> A = {6, 8, 8, 7};
    vector<int> a = find_subset(15, 17, A);
    for(int x : a) cout << x << ' '; cout << '\n';

    vector<int> b = find_subset(14, 15, {5, 5, 6, 6});
    for(int x : b) cout << x << ' '; cout << '\n';

    vector<int> c = find_subset(10, 20, {15, 17, 16, 18});
    for(int x : c) cout << x << ' '; cout << '\n';
}
#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