Submission #1129963

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129963		xnqs	Detecting Molecules (IOI16_molecules)	C++20	100 / 100	40 ms	2632 KiB

molecules

#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <numeric>

#include "molecules.h"

std::vector<int> find_subset(int lo, int hi, std::vector<int> w) {
	std::vector<int> arr(w.size());
	std::iota(arr.begin(),arr.end(),0);
	std::sort(arr.begin(),arr.end(),[&](int a, int b) {
		return w[a] < w[b];
	});

	int64_t sum = 0;
	for (int l = 0, r = 0; r < static_cast<int>(w.size()); r++) {
		sum += w[arr[r]];
		while (l < r && sum > hi) {
			sum -= w[arr[l]];
			++l;
		}

		if (lo <= sum && sum <= hi) {
			std::vector<int> ret;
			ret.reserve(r-l+1);
			for (int i = l; i <= r; i++) {
				ret.emplace_back(arr[i]);
			}
			return ret;
		}
	}

	return std::vector<int>();
}

Compilation message (stderr)

molecules.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
molecules_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

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