Submission #362128

#	Time	Username	Problem	Language	Result	Execution time	Memory
362128		Eyed	Detecting Molecules (IOI16_molecules)	C++14	100 / 100	63 ms	10452 KiB

molecules

#include <iostream>
#include <algorithm>
#include <vector>
#define ll long long
#define pii pair<ll, int>
using namespace std;

vector<int> find_subset(int l, int u, vector<int> w) {
	ll prefix[200005];
	ll suffix[200005];
	ll n = w.size();
	vector<pii> nW;
	vector<int> ans;
	bool less = false;
	for (ll i = 0; i < n; ++i) {
		if (w[i] >= l && w[i] <= u) {
			ans.push_back(i);
			return ans;
		}
		if (w[i] < l) less = true;
		nW.push_back(make_pair(w[i], i ));
	}
	if (!less) {
		return ans;
	}
	sort(nW.begin(), nW.end());
	//for (ll i = 0; i < n; ++i) cout << w[i] << " ";
	//cout << endl;
	prefix[0] = nW[0].first;
	suffix[n - 1] = nW[n - 1].first;
	for (ll i = 1; i < n; ++i) prefix[i] = prefix[i - 1] + nW[i].first;
	for (ll i = n - 2; i >= 0; --i) suffix[i] = suffix[i + 1] + nW[i].first;
	if (prefix[n - 1] < l) {
		return ans;
	}
	for (ll i = 0; i < n; ++i) {
		if (prefix[i] >= l && prefix[i] <= u) {
			for (ll j = 0; j <= i; ++j) ans.push_back(nW[j].second);
			return ans;
		}
		if (suffix[n - i - 1] >= l && suffix[n - i - 1] <= u) {
			for (ll j = n - 1; j >= n - i - 1; --j) ans.push_back(nW[j].second);
			return ans;
		}
		if (!(prefix[i] < l && suffix[n - i - 1] > u)) continue;
		ll curSum = prefix[i];
		for (ll j = 0; j <= min(i, n - i - 1); ++j) {
			curSum += (nW[n - j - 1].first - nW[j].first);
			if (curSum >= l && curSum <= u) {
				for (ll k = 0; k <= j; ++k) ans.push_back(nW[n - k - 1].second);
				for (ll k = j + 1; k <= i; ++k) ans.push_back(nW[k].second);
				return ans;
			}
		}
		return ans;
	}
	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