Submission #639967

#	Time	Username	Problem	Language	Result	Execution time	Memory
639967		pere_gil	Detecting Molecules (IOI16_molecules)	C++17	100 / 100	43 ms	7152 KiB

molecules

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

typedef long long ll;
#define ii pair<ll,ll> 

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

	int i=0,j=0;
	ll sum=0;
	while(sum<l || sum>u){
		if(sum<l){
			if(j==n) break;
			sum+=v[j].first;
			j++;
		}
		else{
			if(i>j) break;
			sum-=v[i].first;
			i++;
		}			
	}

	if(sum<l || sum>u) return vector<int> ();

	vector<int> res;
	for(int k=i;k<j;k++) res.push_back(v[k].second);
	return res;
}

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