Submission #1011177

#	Time	Username	Problem	Language	Result	Execution time	Memory
1011177		pawned	Detecting Molecules (IOI16_molecules)	C++17	100 / 100	106 ms	19796 KiB

molecules

#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")

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

#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<ll, ll> ii;
typedef vector<ll> vi;

#include "molecules.h"

vector<int> find_subset(int L, int H, vector<int> w) {
	int N = w.size();
	vector<ii> all(N);
	for (int i = 0; i < N; i++) {
		all[i].fi = w[i];
		all[i].se = i;
	}
	sort(all.begin(), all.end());
/*	cout<<"all: ";
	for (int i = 0; i < N; i++) {
		cout<<"("<<all[i].fi<<", "<<all[i].se<<"); ";
	}
	cout<<endl;*/
	// consider all prefix left and right sums
	set<ii> preR;
	preR.insert({0, N});
	ll curr = 0;	// current sum
	for (int i = N - 1; i >= 0; i--) {
		curr += all[i].fi;
		preR.insert({curr, i});
	}
/*	cout<<"preR: ";
	for (ii p : preR)
		cout<<"("<<p.fi<<", "<<p.se<<"); ";
	cout<<endl;*/
	curr = 0;	// current sum
	for (int i = 0; i <= N; i++) {	// take up to i, exclusive
//		cout<<i<<": "<<curr<<endl;
		ii lb = {L - curr, -1};
		ii ub = {H - curr, 1e9};
//		cout<<"lb, ub: "<<lb.fi<<" "<<lb.se<<" "<<ub.fi<<" "<<ub.se<<endl;
		// if any in [lb, ub] in preR, works
		if (preR.lower_bound(lb) != preR.lower_bound(ub)) {	// found
			auto it = preR.lower_bound(lb);
			ii res = *it;
			int rv = res.se;
			vector<int> ans;
			for (int j = 0; j < i; j++) {
				ans.pb(all[j].se);
			}
			for (int j = rv; j < N; j++) {
				ans.pb(all[j].se);
			}
			return ans;
		}
		preR.erase(*(--preR.end()));
		curr += all[i].fi;
	}
	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