Submission #889158

#	Time	Username	Problem	Language	Result	Execution time	Memory
889158		Muhammad_Aneeq	Detecting Molecules (IOI16_molecules)	C++17	100 / 100	161 ms	27284 KiB

molecules

#include <vector>
#include <set>
#include <algorithm>
#include <map>
using namespace std;
vector<int> find_subset(int l,int u,vector<int>w)
{
	
	long long sum=0;
	multiset<long long>ind;
	vector<long long>f={begin(w),end(w)};
	for (auto i:f)
		sum+=i;
	if (sum<l)
		return {};
	sum=0;
	sort(begin(w),end(w));
	multiset<long long>s;
	long long pre=0;
	for (long long i=0;i<w.size();i++)
	{
		sum+=w[i];
		s.insert(sum);
		ind.insert(i);
		if (sum<l)
			continue;
		if (sum>=l&&sum<=u)
			break;
		auto z=s.upper_bound(sum-l);
		if (z==s.begin())
			continue;
		z--;
		auto g=begin(s);
		while (*g!=*z)
		{
			s.erase(s.find(*begin(s)));
			ind.erase(ind.find(*begin(ind)));
			g=begin(s);
		}	
		pre=*begin(s);
		s.erase(s.find(*begin(s)));
		ind.erase(ind.find(*begin(ind)));
		if (sum-pre>=l&&sum-pre<=u)
			break;
	}
	if (s.size()==0||*(--end(s))<l+pre||*(--end(s))>u+pre)
		return {};
	vector<int>ans;
	map<long long,vector<long long>>d;
	for (long long i=0;i<f.size();i++)
		d[f[i]].push_back(i);
	for (auto i:ind)
	{
		ans.push_back(d[w[i]].back());
		d[w[i]].pop_back();
	}
	return ans;
}

Compilation message (stderr)

molecules.cpp: In function 'std::vector<int> find_subset(int, int, std::vector<int>)':
molecules.cpp:20:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |  for (long long i=0;i<w.size();i++)
      |                     ~^~~~~~~~~
molecules.cpp:50:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |  for (long long i=0;i<f.size();i++)
      |                     ~^~~~~~~~~

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