Submission #226637

#	Time	Username	Problem	Language	Result	Execution time	Memory
226637		staniewzki	Detecting Molecules (IOI16_molecules)	C++17	100 / 100	110 ms	16112 KiB

molecules

#include<bits/stdc++.h>
using namespace std;
 
#include "molecules.h"

vector<int> find_subset(int l, int r, vector<int> w) {
	int n = size(w);
	vector<vector<int>> q(n);
	for(int i = 0; i < n; i++)
		q[i] = {w[i], i};
	sort(q.begin(), q.end());

	vector<int> ans;
	long long pref = 0, suff = 0;
	for(int i = 0; i < n; i++) {
		ans.emplace_back(q[i][1]);
		pref += q[i][0];
		suff += q[n - 1 - i][0];
		if(pref <= r && l <= suff) {
			for(int j = 0; pref < l; j++) {
				pref -= q[i - j][0];
				pref += q[n - 1 - j][0];
				ans[i - j] = q[n - 1 - j][1];
			}
			return ans;
		}
	}
	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