Submission #914106

#	Time	Username	Problem	Language	Result	Execution time	Memory
914106		lamter	Detecting Molecules (IOI16_molecules)	C++17	100 / 100	37 ms	6480 KiB

molecules

#include "molecules.h"
#include <bits/stdc++.h>
using i64 = long long int;

std::vector<int> find_subset(int _l, int _r, std::vector<int> _w) {
	std::vector <i64> a(_w.begin(), _w.end());
	i64 l = _l, r = _r;

	int n = (int) a.size();
	std::vector <int> ord(n); std::iota(ord.begin(), ord.end(), 0);
	std::sort(ord.begin(), ord.end(), [&] (int i, int j) -> bool { return a[i] < a[j]; });

	int k = 0;
	int pos_l = 0, pos_r = n - 1;
	i64 sum_l = 0, sum_r = 0;

	for (k = 1; k <= n; k += 1) {
		sum_l += a[ord[pos_l++]];
		sum_r += a[ord[pos_r--]];

		if (sum_l <= r and l <= sum_r)
			break;
	}

	if (k == n + 1)
		return {};

	i64 sum = 0;
	for (int i = 0; i < k; i += 1) {
		sum += a[ord[i]];
	}

	for (int x = 0, y = k; y <= n; x += 1, y += 1) {
		if (l <= sum and sum <= r) {
			return std::vector <int> (ord.begin() + x, ord.begin() + y);
		}

		sum -= a[ord[x]];
		if (y < n)
			sum += a[ord[y]];
	}

	return {};
}

#ifdef ILOVELAMTER
	int main(void) {
		std::vector <int> a = find_subset(10, 20, {15, 17, 16, 18});
		for (int x : a)
			std::cerr << x << ' ';
	}
#endif // ILOVELAMTER

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