Submission #419259

#	Time	Username	Problem	Language	Result	Execution time	Memory
419259		Mounir	Detecting Molecules (IOI16_molecules)	C++14	100 / 100	57 ms	5580 KiB

molecules

#include "molecules.h"
#include <bits/stdc++.h>
#define sz(x) (int)x.size()
#define chmax(x, v) x = max(x, v)
#define chmin(x, v) x = min(x, v)
#define all(x) x.begin(), x.end()
#define pb push_back
#define pii pair<int, int>
#define x first
#define y second
using namespace std;

struct Molecule {
	int poids, id;

	bool operator < (const Molecule &autre) const {
		if (poids != autre.poids)
			return poids < autre.poids;
		return id < autre.id;
	}
};

vector<int> find_subset(int l, int u, vector<int> w) {
    int nMolecules = sz(w);

    //cout << nMolecules << endl;

    vector<Molecule> molecules(nMolecules);
    for (int ind = 0; ind < nMolecules; ++ind)
    	molecules[ind] = {w[ind], ind};
    sort(all(molecules));
    int fin = 0; long long sum = 0;
    for (int deb = 0; deb < nMolecules; ++deb){
    	if (deb > 0)
    		sum -= molecules[deb - 1].poids;
    	chmax(fin, deb);
    	while (fin < nMolecules && sum < l)
    		sum += molecules[fin++].poids;
    	//cout << sum << " " << deb << " " << fin << endl;
    	if (l <= sum && sum <= u){
    	//	cout << "OUI " << endl;
    		vector<int> subset;
    		for (int ind = deb; ind < fin; ++ind)
    			subset.pb(molecules[ind].id);
    		return subset;
    	}
    }
    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