Submission #491947

#	Time	Username	Problem	Language	Result	Execution time	Memory
491947		Virv	Detecting Molecules (IOI16_molecules)	C++17	69 / 100	2 ms	460 KiB

molecules

#include <algorithm>
#include <cstdint>
#include <numeric>
#include <vector>

#include "molecules.h"

std::vector<int> find_subset(int l, int u, std::vector<int> w) {
	std::vector<uint32_t> p(w.size());
	iota(p.begin(), p.end(), 0);
	sort(p.begin(), p.end(), [&](auto a, auto b) { return w[a] < w[b]; });

	int				 T{};
	std::vector<int> S{};

	size_t i{};
	while (i < p.size() && T + w[p[i]] <= u) {
		T += w[p[i]];
		S.push_back(p[i]);
		++i;
	}

	if (S.size() == 0) return {};

	while (i < p.size() && T < l) {
		T += w[p[i]] - w[S[i % S.size()]];
		S[i % S.size()] = p[i];
		++i;
	}

	return l <= T && T <= u ? S : std::vector<int>{};
}

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