Submission #546244

#	Time	Username	Problem	Language	Result	Execution time	Memory
546244		Sergio_2357	Detecting Molecules (IOI16_molecules)	C++17	69 / 100	50 ms	6572 KiB

molecules

#include "molecules.h"
#include <bits/stdc++.h>

using namespace std;

#define ll int

std::vector<int> find_subset(int l, int u, vector<int> w)
{
    ll sum = 0;
    vector<ll> a = w;
    int n = a.size();
    vector<int> us(n, 0);
    vector<pair<int, int>> ri(n);
    for (int i = 0; i < n; i++)
        ri[i] = { w[i], i };
    sort(a.begin(), a.end());
    sort(ri.begin(), ri.end());
    int s = 0;
    int e = n - 1;
    while (sum < l && e >= 0) {
        us[e] = 1;
        sum += a[e];
        e--;
        //cout << sum << endl;
    }
    e = n - 1;
    while (sum > u && s < e) {
        if (!us[e] || us[s])
            break;
        us[e] = 0;
        us[s] = 1;
        sum -= a[e];
        sum += a[s];
        e--;
        s++;
        //cout << sum << endl;
    }
    if (sum >= l && sum <= u) {
        vector<int> res;
        for (int i = 0; i < n; i++) {
            if (us[i])
                res.push_back(ri[i].second);
        }
        sort(res.begin(), res.end());
        return res;
    } else {
        return vector<int>(0);
    }
}

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