Submission #1024900

#	Time	Username	Problem	Language	Result	Execution time	Memory
1024900		slivajan	Detecting Molecules (IOI16_molecules)	C++17	100 / 100	35 ms	8784 KiB

molecules

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

typedef long long un;
typedef vector<un> vuc;


#define REP(i, a, b) for(un i = a; i < b; i++)
#define FEAC(i, a) for (auto&& i : a)
#define vec vector
#define ALL(x) (x).begin(), (x).end()

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

    vec<pair<un, un>> toSort((un)w.size());

    REP(i, 0, (un)w.size()) toSort[i] = {w[i], i};

    sort(ALL(toSort));

    vuc tab(w.size());

    REP(i, 0,(un) w.size()){
        w[i] = toSort[i].first;
        tab[i] = toSort[i].second;
    }

    un ls = 0;
    un rs = 0;

    un ptr = 0;

    while(((ls < l) and (rs < l)) and (ptr < (un)w.size())){
        ls += w[ptr];
        rs += w[w.size() - ptr - 1];

        ptr++;
    }

    if (ls > u){
        return {};
    }

    if (rs < l) return {};

    vec<int> ret(ptr);
    iota(ALL(ret), 0);

    un newptr = ((un)ret.size()) - 1;
    while(ls < l){
        ret[newptr] = ((un)w.size()) - ((un)ret.size()) + newptr;
        ls += (w[ret[newptr]] - w[newptr]);
        newptr--;
    }

    REP(i, 0, (un)ret.size()){
        ret[i] = tab[ret[i]];
    }

    return ret;
}

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