Submission #293298

#	Time	Username	Problem	Language	Result	Execution time	Memory
293298		VodkaInTheJar	Detecting Molecules (IOI16_molecules)	C++14	100 / 100	68 ms	9832 KiB

molecules

#include <bits/stdc++.h>
 
using namespace std;

const int maxn = 200003; 

vector <int> find_subset(int l, int u, vector <int> w)
{
	int sz = (int)w.size();
	
	vector <pair <int, int> > v;
	for (int i = 0; i < sz; i++)
	v.push_back({w[i], i});
	
	sort (v.begin(), v.end());
	vector <pair <long long, int> > v1; 
	
	v1.push_back({0, -1});
	
	long long sum = 0; 
	int pos = 0; 
	for (int i = 0; i < sz; i++)
	{
		sum += v[i].first;
		v1.push_back({sum, i});
		
		if (sum >= l)
		{
			while (sum - v1[pos].first > u)
			pos++;
			
			if (pos != (int)v1.size() - 1 && sum - v1[pos].first >= l)
			{
				vector <int> ans; 
				for (int j = v1[pos].second + 1; j <= i; j++)
				ans.push_back(v[j].second);
				
				return ans; 
			}
		}
	}
	
	return {};
}

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