Submission #137115

#	Time	Username	Problem	Language	Result	Execution time	Memory
137115		anayk	Detecting Molecules (IOI16_molecules)	C++14	100 / 100	64 ms	6620 KiB

molecules

#include "molecules.h"

#include <vector>
#include <algorithm>
#include <iostream>

#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;
	}
	
	long long cur = 0;
	long long low = 0; long long 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 < n)
	{
		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;
		}
	}
}

int ma1n()
{
	int l, u;
	std::cin >> n >> l >> u;
	
	std::vector<int> w(n);
	for(int i = 0; i < n; i++)
		std::cin >> w[i];
	
	find_subset(l, u, w);
	
	std::cout << answer.size() << std::endl;
	for(int j = 0; j < answer.size(); j++)
		std::cout << answer[j] << " ";
}

Compilation message (stderr)

molecules.cpp: In function 'int ma1n()':
molecules.cpp:107:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int j = 0; j < answer.size(); j++)
                 ~~^~~~~~~~~~~~~~~
molecules.cpp:109:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
molecules.cpp: In function 'std::vector<int> find_subset(int, int, std::vector<int>)':
molecules.cpp:93:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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