Submission #376122

#	Time	Username	Problem	Language	Result	Execution time	Memory
376122		Ozy	Detecting Molecules (IOI16_molecules)	C++17	100 / 100	62 ms	8408 KiB

molecules

#include "molecules.h"
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define rep(i,a,b) for (int i = (a); i <= (b); i++)
#define repa(i,a,b) for (int i = (a); i >= (b); i--)
#define debug(a) cout << #a << " = " << a << endl

#define num first
#define id second

lli ult,sum,cont,n;
lli visitados[200002];
vector<int> res;
vector<pair<lli,lli> > orden;

vector<int> procesa() {

    rep(i,0,n-1) if (visitados[i] > 0) res.push_back(i);
    return res;

}

std::vector<int> find_subset(int l, int u, std::vector<int> w) {

    cont = 0;
    for (auto act : w) {
        orden.push_back({act,cont});
        cont++;
    }
    sort(orden.begin(), orden.end());

    ult = -1;
    cont = 0;
    sum = 0;
    n = w.size();

    for (auto act : orden) {
        sum += act.num;
        if (sum > u) {
            //debug(cont);
            ult = cont-1;
            sum -= act.num;
            //debug(sum);
            break;
        }
        visitados[act.id] = 1;
        cont++;
    }

    if (sum <= u && sum >= l) return procesa();
    else if (ult == -1) return {};

    cont = ult;
    repa(i,n-1,n-cont-1) {

        sum -= orden[ult].num;
        visitados[ orden[ult].id ] = 0;

        sum += orden[i].num;
        visitados[ orden[i].id ] = 1;

        ult--;
        if (sum <= u && sum >= l) return procesa();
    }
    return {};
}

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