Submission #137072

#	Time	Username	Problem	Language	Result	Execution time	Memory
137072		anayk	Detecting Molecules (IOI16_molecules)	C++14	69 / 100	5 ms	636 KiB

molecules

#include "molecules.h"

#include <vector>
#include <algorithm>

#define MAXN 200005

int n;
std::vector<int> answer;
bool choice[MAXN];
std::pair<int, int> vals[MAXN];
int rev[MAXN];

void make()
{
	for(int i = 0; i < n; i++)
		if(choice[i])
			answer.push_back(rev[i]);
}

std::vector<int> find_subset(int l, int u, std::vector<int> w)
{
	n = w.size();
	
	for(int i = 0; i < n; i++)
	{
		vals[i].first = w[i];
		vals[i].second = i;
		choice[i] = false;
	}
	
	std::sort(vals, vals+n);
	
	for(int i = 0; i < n; i++)
	{
		w[i] = vals[i].first;
		rev[i] = vals[i].second;
	}
	
	int cur = 0;
	int avail = -1;
	for(int i = n-1; i >= 0; i--)
	{
		if(cur + w[i] <= u)
		{
			choice[i] = true;
			cur += w[i];
		}
		else
			avail = i;
	}
	
	if(cur >= l)
	{
		make();
		return answer;
	}
	
	if(avail == -1)
		return answer;
	
	choice[avail] = true;
	cur += w[avail];
	
	int x = 0; int y = n-1;
	while(x < y)
	{
		if(choice[x])
		{
			x++;
			continue;
		}
		
		if(!choice[y])
		{
			y--;
			continue;
		}
		
		choice[x] = true;
		choice[y] = false;
		
		cur += w[x] - w[y];
		
		if(cur <= u)
		{
			make();
			return answer;
		}
	}
	
	if(cur - w[0] >= l)
	{
		choice[0] = true;
		make();
	}
	
	return answer;
}

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