Submission #393726

#	Time	Username	Problem	Language	Result	Execution time	Memory
393726		JimmyZJX	Detecting Molecules (IOI16_molecules)	C++14	69 / 100	52 ms	6440 KiB

molecules

#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstring>
#include <climits>
#include <cassert>
#include <tuple>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <numeric>

using namespace std;

typedef long long LL;
typedef vector<int> Vi;
typedef vector<LL> VL;
typedef vector<bool> Vb;
typedef vector<vector<int>> Vii;
typedef vector<vector<vector<int>>> Viii;
typedef vector<vector<pair<int, int>>> Vip;

#define forR(i, n) for (int i = 0; i < (n); i++)

template <typename T>
vector<size_t> sort_indexes(vector<T> v) {
	vector<size_t> idx(v.size());
	iota(idx.begin(), idx.end(), 0);

	stable_sort(idx.begin(), idx.end(),
		[&v](size_t i1, size_t i2) {return v[i1] < v[i2]; });

	return idx;
}

bool overlap(int x1, int x2, int y1, int y2) {
	if (y2 >= x1 && x2 >= y1) return true;
	return false;
}

Vi find_subset(int l, int u, Vi w) {
	auto idx = sort_indexes(w);

	int n = w.size();

	int curSz = 0;
	LL lower = 0, upper = 0;
	while (true) {
		curSz++;
		if (curSz > n) {
			return Vi();
		}
		lower += w[idx[curSz - 1]];
		upper += w[idx[n - curSz]];
		if (overlap(lower, upper, l, u)) break;
	}

	LL sum = lower; // [0 .. sz-1]
	int adjust = 0;
	while (true) {
		if (sum >= l) break;
		if (adjust > curSz) break;
		sum -= w[idx[curSz - 1 - adjust]];
		sum += w[idx[n - 1 - adjust]];
		adjust++;
	}

	assert(adjust <= curSz);
	Vi ans;
	forR(i, curSz - adjust) ans.push_back(idx[i]);
	forR(i, adjust) ans.push_back(idx[n - 1 - i]);
	return ans;
}

#ifdef TEST_LOCAL
int main() {
	auto r = find_subset(15, 17, Vi{ 6, 8, 8, 7 });

	return 0;
}
#endif

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