Submission #1045707

#	Time	Username	Problem	Language	Result	Execution time	Memory
1045707		Gromp15	Detecting Molecules (IOI16_molecules)	C++17	100 / 100	39 ms	4952 KiB

molecules

#include "molecules.h"
#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()

using namespace std;

std::vector<int> find_subset(int l, int u, std::vector<int> w) {
	int n = sz(w);
	vector<int> idx(n);
	iota(all(idx), 0);
	sort(all(idx), [&](int x, int y) { return w[x] < w[y]; });
	vector<bool> use(n);
	long long sum = 0;
	int to = -1;
	for (int i = 0; i < n; i++) {
		if (sum + w[idx[i]] > u) break;
		use[i] = 1;
		sum += w[idx[i]], to = i;
	}
	if (to == -1) return {};
	int L = 0;
	while (sum < l && to+1 < n) {
		sum += w[idx[to+1]] - w[idx[L]];
		use[L] = 0, use[to+1] = 1;
		L++, to++;
	}
	if (sum < l) return {};
	vector<int> ans;
	for (int i = 0; i < n; i++) if (use[i]) ans.emplace_back(idx[i]);
	return ans;
}

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