Submission #1024882

#	Time	Username	Problem	Language	Result	Execution time	Memory
1024882		slivajan	Detecting Molecules (IOI16_molecules)	C++17	0 / 100	0 ms	344 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)){
        ls += w[ptr];
        rs += w[w.size() - ptr - 1];

        ptr++;
    }

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

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

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

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

    return ret;
}

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