Submission #600517

#	Time	Username	Problem	Language	Result	Execution time	Memory
600517		8e7	Detecting Molecules (IOI16_molecules)	C++17	100 / 100	51 ms	5292 KiB

molecules

//Challenge: Accepted
#include <bits/stdc++.h>
#include "molecules.h"
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r){
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 100005
#define pii pair<int, int>
#define ff first
#define ss second

vector<int> find_subset(int L, int U, vector<int> w) {
	vector<int> ret;	
	int n = w.size();
	vector<pii> a(n);
	vector<ll> pref(n, 0);
	for (int i = 0;i < n;i++) a[i] = {w[i], i};
	sort(a.begin(), a.end());
	for (int i = 0;i < n;i++) pref[i] = a[i].ff + (i ? pref[i-1] : 0);	
	auto sum = [&] (int l, int r){
		return pref[r] - (l ? pref[l-1] : 0LL);
	};
	for (int i = 1;i <= n;i++) {
		ll low = sum(0, i-1), up = sum(n-i, n-1);
		if (min(up, (ll)U) >= max((ll)L, low)) {
			for (int j = 0;j <= n - i;j++) {
				if (L <= sum(j, j+i-1) && sum(j, j+i-1) <= U){
					for (int x = j;x < j + i;x++) ret.push_back(a[x].ss);
					sort(ret.begin(), ret.end());
					return ret;
				}
			}
		}
	}
	return ret;
}

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