Submission #134591

#	Time	Username	Problem	Language	Result	Execution time	Memory
134591		MAMBA	Detecting Molecules (IOI16_molecules)	C++17	100 / 100	69 ms	6392 KiB

molecules

#include "molecules.h"
#include <bits/stdc++.h>

using namespace std;

#define rep(i , j ,k) for (int i = j; i < (int)k; i++)
#define pb push_back
#define all(x) x.begin(),x.end()

typedef vector<int> vi;
typedef long long ll;



vi find_subset(int l, int u, vi w) {
	int n = w.size();

	vi ind(n);
	iota(all(ind) , 0);
	sort(all(ind) ,[&](int a, int b) { return w[a] < w[b]; });


	vector<ll> ps(n);
	rep(i, 0 , n) ps[i] = w[ind[i]];
	partial_sum(all(ps) , ps.begin());

	ll now = 0;


	for (int i = n; i; i--) {
		int id = lower_bound(all(ps) , l - now) - ps.begin();
		if (now >= l) {
			if (now > u) return vi(0);
			vi res(ind.begin() + i, ind.end());
			sort(all(res));
			return res;
		}
		if (id < i && ps[id] + now <= u) {
			vi res;
			rep(j , 0 , id + 1)
				res.pb(ind[j]);
			rep(j , i , n)
				res.pb(ind[j]);
			sort(all(res));
			return res;
		}
		now += w[ind[i - 1]];
	}
	return vi(0);
}

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