Submission #137078

#	Time	Username	Problem	Language	Result	Execution time	Memory
137078		anayk	Detecting Molecules (IOI16_molecules)	C++14	69 / 100	56 ms	5980 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 low = 0; int high = 0;
	bool poss = false;
	for(int i = 0; i < n; i++)
	{
		low += w[i];
		high += w[n-1-i];
		cur += w[n-1-i];
		choice[n-1-i] = true;
		
		if(high >= l && low <= u)
		{
			poss = true;
			break;
		}
	}
	
	if(!poss)
		return answer;
	
	if(cur <= u)
	{
		make();
		return answer;
	}
	
	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