Submission #254466

#	Time	Username	Problem	Language	Result	Execution time	Memory
254466		babo	Detecting Molecules (IOI16_molecules)	C++14	100 / 100	64 ms	7024 KiB

molecules

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

L n;
L s,e;

struct S{
	L idx, weight;
};

bool operator<(S a,S b){
	return a.weight<b.weight;
}

vector<int> find_subset(int l,int u, vector<int> w){
	n=(L)w.size();
	vector<int> ans(n);
	L i;
	s=l,e=u;
	L W=0;
	vector<S>v;
	for(i=0;i<n;i++)
		v.push_back((S){i,w[i]});
	sort(v.begin(),v.end());
	for(i=n-1;i>=0;i--)
	{
		W+=v[i].weight;
		ans[v[i].idx]=1;
		if(W>e)
		{
			L j=n-1;
			while(i>0)
			{
				W+=v[i-1].weight;
				ans[v[i-1].idx]=1;
				W-=v[j].weight;
				ans[v[j].idx]=0;
				i--;j--;
				if(s<=W&&W<=e)
				{
					vector<int>ans2;
					for(i=0;i<n;i++)
						if(ans[i]) ans2.push_back(i);
					return ans2;
				}
			}
			break;
		}
		else if(W>=s)
		{
					vector<int>ans2;
					for(i=0;i<n;i++)
						if(ans[i]) ans2.push_back(i);
					return ans2;
		}
	}
	vector<int> ans2(0);
	return ans2;
}

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