Submission #611074

#	Time	Username	Problem	Language	Result	Execution time	Memory
611074		Temmie	Detecting Molecules (IOI16_molecules)	C++17	100 / 100	43 ms	5584 KiB

molecules

#include <bits/stdc++.h>

std::vector <int> find_subset(int f, int u, std::vector <int> w) {
	int n = w.size();
	std::vector <std::pair <int, int>> a(n);
	for (int i = 0; i < n; i++) {
		a[i] = { w[i], i };
	}
	std::sort(a.begin(), a.end());
	long long sum = 0;
	for (int l = 0, r = 0; r < n; r++) {
		sum += a[r].first;
		while (l <= r && sum > u) {
			sum -= a[l++].first;
		}
		if (l > r) {
			break;
		}
		if (sum >= f && sum <= u) {
			std::vector <int> ans;
			for (int j = l; j <= r; j++) {
				ans.push_back(a[j].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