Submission #169551

#	Time	Username	Problem	Language	Result	Execution time	Memory
169551		Lawliet	Detecting Molecules (IOI16_molecules)	C++14	100 / 100	64 ms	6252 KiB

molecules

#include "molecules.h"
#include <bits/stdc++.h>

using namespace std;
typedef pair<int,int> pii;
typedef long long int lli;

vector< int > ans;

vector< pii > sweep;

vector<int> find_subset(int lower, int upper, vector<int> w) 
{
	int N = w.size();

	for(int i = 0 ; i < N ; i++)
		sweep.push_back( { w[i] , i } );

	sort( sweep.begin() , sweep.end() );

	int R = 0;
	lli sum = 0;

	for(int L = 0 ; L < N ; L++)
	{
		if( L > R )
		{
			R = L;
			sum = 0;
		}

		while( R < N && sum < lower )
			sum += sweep[ R++ ].first;

		if( lower <= sum && sum <= upper )
		{
			for(int j = L ; j < R ; j++)
				ans.push_back( sweep[j].second );

			return ans;
		}

		sum -= sweep[L].first;
	}

    return ans;
}

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