Submission #88407

#	Time	Username	Problem	Language	Result	Execution time	Memory
88407		Pajaraja	Detecting Molecules (IOI16_molecules)	C++17	100 / 100	70 ms	7232 KiB

molecules

#include "molecules.h"
#include <algorithm>
#include <vector>
using namespace std;
struct h
{
	long long v;
	int i;
};
bool cmp(h a,h b){return a.v<b.v;};
h he[200000];
long long par[200001];
std::vector<int> find_subset(int l, int u, std::vector<int> w) 
{
	vector<int> sol;
    int n=w.size();
    for(int i=0;i<n;i++)
    {
		he[i].i=i;
    	he[i].v=w[i];
	}
	sort(he,he+n,cmp);
	par[0]=0;
	for(int i=1;i<=n;i++) par[i]=par[i-1]+he[i-1].v;
	for(int i=0;i<n;i++)
	{
		if(!((par[n]-par[n-1-i]<l)||(par[i+1]>u)))
		{
			long long p=par[i+1];
			for(int j=0;j<n-i;j++)
			{
				if(p>=l&&p<=u)
				{
					for(int g=0;g<i+1;g++)
					{
						sol.push_back(he[j+g].i);
					}
					return sol;
				}
				p-=he[j].v;
				p+=he[j+i+1].v;
			}
		}
	}
	return sol;
}

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