Submission #199488

#	Time	Username	Problem	Language	Result	Execution time	Memory
199488		monus1042	Detecting Molecules (IOI16_molecules)	C++17	100 / 100	81 ms	7160 KiB

molecules

#include "molecules.h"
#include <bits/stdc++.h>
using namespace std;
 
vector<int> find_subset(int l, int u, vector<int> w) {
	vector<int> ans;
	int ss=w.size();
	vector< pair<long long,int> > orig(ss);
	for (int i=0; i<ss; i++) orig[i].first=(long long)w[i], orig[i].second=i;
	sort(orig.begin(), orig.end());
	if ((long long)u<orig[0].first) return ans;
	int left=0, right=0;
	long long sum=orig[0].first;
	while(1){
		if (sum>(long long)u){
			sum-=orig[left].first;
			left++;
			if (left>right) break;
		}else if (sum<(long long)l){
			right++;
			if (right<ss) sum+=orig[right].first;
			else break;
		}else{
			for (int i=left; i<=right; i++) ans.push_back(orig[i].second);
			break;
		}
	}
	
    return ans;
}

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