Submission #342025

#	Time	Username	Problem	Language	Result	Execution time	Memory
342025		SeDunion	Detecting Molecules (IOI16_molecules)	C++17	9 / 100	1 ms	384 KiB

molecules

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 66;

vector<int> find_subset(int l, int r, vector<int> w) {
	ll S = 0;
	for (int i : w) S += i;
	if (S < l || *min(w.begin(), w.end()) > r) return {};
	int n = w.size();
	for (int i = 0 ; i < n ; ++ i) {
		if (l <= w[i] && w[i] <= r) {
			return {i};
		}
	}
	vector<pair<int,int>> a(n);
	for (int i = 0 ; i < n ; ++ i) a[i] = {w[i], i};
	sort(a.begin(), a.end());
	S = a[0].first;
	vector<int> Ans = {a[0].second};
	for (int i = n - 2 ; i > 0 ; -- i) {
		if (S + a[i].first <= r) {
			S += a[i].first;
			Ans.push_back(a[i].second);
		}
	}
	if (l <= S && S <= r) {
		sort(Ans.begin(), Ans.end());
		return Ans;
	}
	if (l <= S + a.back().first && S + a.back().first <= r) {
		Ans.push_back(a.back().second);
		sort(Ans.begin(), Ans.end());
		return Ans;
	}
	if (l <= S + a.back().first - a[0].first && S + a.back().first - a[0].first <= r) {
		Ans.push_back(a.back().second);
		Ans.erase(find(Ans.begin(), Ans.end(), a[0].second));
		sort(Ans.begin(), Ans.end());
		return Ans;
	}
	S = a.back().first;
	Ans = {a.back().second};
	for (int i = n - 2 ; i >= 0 ; -- i) {
		if (S + a[i].first <= r) {
			S += a[i].first;
			Ans.push_back(a[i].second);
		}
	}
	if (l <= S && S <= r) {
		sort(Ans.begin(), Ans.end());
		return Ans;
	}
  	return {};
	//assert(0);
}
/*
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int n, l, u;
	cin >> n >> l >> u;
	vector<int> w(n);
	for (int &i : w) cin >> i;
	auto A = find_subset(l, u, w);
	cout << A.size() << "\n";
	for (int i : A) cout << i << " ";
}

*/

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