Submission #393459

#	Time	Username	Problem	Language	Result	Execution time	Memory
393459		antontsiorvas	Detecting Molecules (IOI16_molecules)	C++14	100 / 100	66 ms	5552 KiB

molecules

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

int len;
pair<int,int> data[200005];

std::vector<int> find_subset(int l, int u, std::vector<int> w) {
	len = w.size();
	for(int i=0; i<len; i++){
		data[i].first = w[i];
		data[i].second = i;
	} 
	sort(data,data+len);
	int beg=0;
	long long int cursum=0;
	vector<int> ret;
	for(int end=0; end<len; end++){
		cursum += data[end].first;
		while(cursum > u && end >= beg){
			cursum -= data[beg].first;
			beg++;
		}
		if(l <= cursum && cursum <= u){
			for(int j=beg; j<=end; j++) ret.push_back(data[j].second);
			sort(ret.begin(),ret.end());
			return ret;
		}
	}
    return std::vector<int>(0);
}

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