Submission #421422

#	Time	Username	Problem	Language	Result	Execution time	Memory
421422		Kevin_Zhang_TW	Detecting Molecules (IOI16_molecules)	C++17	100 / 100	53 ms	3780 KiB

molecules

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif

const int MAX_N = 300010;
#include "molecules.h"

std::vector<int> find_subset(int l, int u, std::vector<int> w) {
	int n = w.size();
	vector<int> id(n); iota(AI(id), 0);

	sort(AI(id), [&](int x, int y) {
		return w[x] < w[y];
	});

	ll sum = 0;

	int r = 0;

	vector<int> take;

	while (r < n) {
		if (sum + w[ id[r] ] > u) break;
		take.pb(id[r]);
		sum += w[id[r++]];
	}

	if (sum >= l) return take;

	if (r == n) return {};

	for (int i = r-1, j = n-1;i >= 0;--i) {

		sum -= w[ take[i] ];
		take[i] = id[j--];
		sum += w[ take[i] ];

		assert(sum <= u);

		if (sum >= l) return take;
	}

	return {};
}

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