Submission #102828

#	Time	Username	Problem	Language	Result	Execution time	Memory
102828		dnass	Detecting Molecules (IOI16_molecules)	C++14	100 / 100	63 ms	7372 KiB

molecules

#include "molecules.h"
#include <cstdio>
#include <algorithm>
#include <utility>
#include <vector>
#include <iostream>
#include <cstring>
using namespace std;

typedef long long int lld;

int n;
pair<lld, int> wi[200010];
bool chosen[200010];

vector<int> find_subset(int l, int u, vector<int> w) {
	n = (int) w.size();
	vector<int> ans;
	memset(chosen, false, sizeof chosen);
	for(int i=0;i<n;i++) wi[i] = make_pair(w[i], i);
	sort(wi, wi+n);
	lld sum = 0;
	int ind = n-1;
	for(int i=0;i<n;i++){
		if(sum+wi[i].first<=(lld)u){
			sum += wi[i].first;
			chosen[i] = true;
		}else{
			ind = i-1;
			break;
		}
	}
	if(ind==n-1){
		//cout <<"here"<<endl;
		if((lld)l<=sum&&sum<=(lld)u){
			for(int i=0;i<n;i++){
				ans.push_back(i);
			}
		}
		return ans;
	}
	if((lld)l<=sum&&sum<=(lld)u){
		for(int i=0;i<n;i++){
			if(chosen[i]){
				ans.push_back(wi[i].second);
			}
		}
		return ans;
	}
	int a = n-1;
	while(chosen[n-a-1]&&!chosen[a]){
		//cout << "here " << a << endl;
		sum += wi[a].first-wi[n-a-1].first;
		chosen[a] = true; chosen[n-a-1] = false;
		if((lld)l<=sum&&sum<=(lld)u){
			for(int i=0;i<n;i++){
				if(chosen[i]){
					ans.push_back(wi[i].second);
				}
			}
			return ans;
		}
		a--;
	}
	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