Submission #427673

#	Time	Username	Problem	Language	Result	Execution time	Memory
427673		c4ts0up	Detecting Molecules (IOI16_molecules)	C++17	100 / 100	67 ms	8720 KiB

molecules

#include "molecules.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define pb push_back
#define ff first
#define ss second

int n;
vector <pair <ll,ll> > arr;
vector <ll> ps;
pair <ll,ll> res;

vector<int> find_subset(int l, int u, vector<int> w) {
    n = w.size();
    for (int i=0; i<n; i++) arr.pb({(ll)(w[i]), (ll)i});
    sort(arr.begin(), arr.end());

    ps.resize(n);
    ps[0] = arr[0].ff;
    for (int i=1; i<n; i++) ps[i] = ps[i-1] + arr[i].ff;

    bool flag = false;
    ll lb = 0, ub = 0; // [lb, ub]
    while (!flag && lb < n) {
        ub = max(ub, lb);
        while (ub < n && ps[ub] - (lb-1 >= 0 ? ps[lb-1] : 0LL) < l) ub++;

        if (ub < n && l <= ps[ub] - (lb-1 >= 0 ? ps[lb-1] : 0LL) && ps[ub] - (lb-1 >= 0 ? ps[lb-1] : 0LL) <= u) flag = true, res = {lb, ub};
        lb++;
    }

    vector <int> idx;
    if (!flag) return idx;
    else {
        for (int i=res.ff; i<=res.ss; i++) idx.pb(arr[i].ss);
        return idx; 
    }
}

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