Submission #491958

#	Time	Username	Problem	Language	Result	Execution time	Memory
491958		Virv	Detecting Molecules (IOI16_molecules)	C++17	100 / 100	53 ms	2644 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]; });

	long long T{};
	size_t	  i{}, j{};

	for (;;) {
		if (l <= T && T <= u) return std::vector<int>(p.begin() + i, p.begin() + j);

		if (T < l && j < p.size()) {
			T += w[p[j++]];
		} else if (T > u && i < j) {
			T -= w[p[i++]];
		} else {
			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