Submission #342032

#	Time	Username	Problem	Language	Result	Execution time	Memory
342032		SeDunion	Detecting Molecules (IOI16_molecules)	C++17	Compilation error	0 ms	0 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) {
	while (w.size() && w.back() > r) w.pop_back();
	if (w.empty()) return {};
	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 = 1 ; i < n - 1 ; ++ 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 = 0 ; i < n - 1 ; ++ i) {
		if (S + a[i].first <= r) {
			S += a[i].first;
			Ans.push_back(a[i].second);
		}
	}
	if (l <= S - a.back().first && S- a.back().first <= r) {
		Ans.erase(find(Ans.begin(), Ans.end(), a.back().first));
		sort(Ans.begin(), Ans.end());
		return Ans;
	}
	if (l <= S && S <= r) {
		sort(Ans.begin(), Ans.end());
		return Ans;
	}
	S = 0;
	Ans = {};
	for (int i = 0 ; i < n - 1 ; ++ i) {
		if (S + a[i].first <= r) {
			S += a[i].first;
			Ans.push_back(a[i].second);
		}
	}
	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 && S <= r) {
		sort(Ans.begin(), Ans.end());
		return Ans;
	}
	S = a[0].first;
	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 - a.back().first && S- a.back().first <= r) {
		Ans.erase(find(Ans.begin(), Ans.end(), a.back().first));
		sort(Ans.begin(), Ans.end());
		return Ans;
	}
	if (l <= S && S <= r) {
		sort(Ans.begin(), Ans.end());
		return Ans;
	}
	S = 0;
	Ans = {};
	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 + a.back().first && S + a.back().first <= r) {
		Ans.push_back(a.back().second);
		sort(Ans.begin(), Ans.end());
		return Ans;
	}
	if (l <= S && S <= r) {
		sort(Ans.begin(), Ans.end());
		return Ans;
	}
	return {};
}

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 << " ";
}

Compilation message (stderr)

/tmp/ccN8SSdB.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccSwqVrg.o:molecules.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status