Submission #546243

#	Time	Username	Problem	Language	Result	Execution time	Memory
546243		Sergio_2357	Detecting Molecules (IOI16_molecules)	C++17	0 / 100	1 ms	340 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;
    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: 0 / 9
• Subtask 2: 0 / 10
• Subtask 3: 0 / 12
• Subtask 4: 0 / 15
• Subtask 5: 0 / 23
• Subtask 6: 0 / 31