Submission #969780

#	Time	Username	Problem	Language	Result	Execution time	Memory
969780		starchan	Detecting Molecules (IOI16_molecules)	C++17	69 / 100	36 ms	3420 KiB

molecules

#include<bits/stdc++.h>
#include "molecules.h"
using namespace std;
#define in array<int, 2>
#define pb push_back
#define pob pop_back
#define INF (int)1e17
#define MX (int)3e5+5
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)

vector<int> find_subset(int l, int r, vector<int> W)
{
	int Sum = 0;
	int n = W.size(); vector<in> w(n);
	for(int i = 0; i < n; i++)
	{
		w[i] = {W[i], i};
		Sum+=W[i];
	}
	if((l <= Sum) && (Sum <= r))
	{
		vector<int> v;
		for(int i = 0; i < n; i++)
			v.pb(i);
		return v;
	}
	sort(w.begin(), w.end());
	int k, sl, sr; 
	k = -1; sl = sr = 0;
	for(int i = 0; i < n; i++)
	{
		sl+=w[i][0]; sr+=w[n-1-i][0];
		if((r >= sl) && (sr >= l))
		{
			k = i+1;
			break;
		}
	}
	vector<int> v; 
	if(k == -1)
		return v;
	vector<bool> vis(k, 1); vis.resize(n);
	int S = sl;
	for(int i = 0; i < min(k, n-k); i++)
	{
		if((l <= S) && (S <= r))
			break;
		vis[n-1-i] = 1; vis[i] = 0;
		S+=(w[n-1-i][0]-w[i][0]);
	}
	if((l <= S) && (S <= r))
	{
		for(int i = 0; i < n; i++)
			if(vis[i])
				v.pb(w[i][1]);
		sort(v.begin(), v.end());
	}
	return v;
}

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