Submission #230991

#	Time	Username	Problem	Language	Result	Execution time	Memory
230991		peijar	Detecting Molecules (IOI16_molecules)	C++17	100 / 100	69 ms	8704 KiB

molecules

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

#define SZ(v) ((int)(v).size())
using ll = long long; 

vector<int> find_subset(int l, int r, vector<int> weights)
{
	int nb_poids = SZ(weights);
	vector<ll> prefix_sum(nb_poids+1);
	vector<pair<ll, int> > poids(nb_poids);
	for (int i(0); i < nb_poids; ++i)
		poids[i] = make_pair(weights[i], i);
	sort(poids.begin(), poids.end());
	for (int i(0); i < nb_poids; ++i)
		prefix_sum[i+1] = prefix_sum[i] + poids[i].first;

	for (int taille(1); taille <= nb_poids; ++taille)
		if (prefix_sum[taille] <= r and prefix_sum[nb_poids] - prefix_sum[nb_poids-taille] >= l)
		{
			for (int i_start(0); i_start + taille <= nb_poids; ++i_start)
			{
				ll sum = prefix_sum[i_start + taille] - prefix_sum[i_start];
				if (sum >= l and sum <= r)
				{
					vector<int> ans;
					for (int i(0); i < taille; ++i)
						ans.push_back(poids[i+i_start].second);
					return ans;
				}
			}
		}
	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