Submission #284309

#	Time	Username	Problem	Language	Result	Execution time	Memory
284309		user202729	Detecting Molecules (IOI16_molecules)	C++17	100 / 100	62 ms	7160 KiB

molecules

// moreflags=grader.cpp
// 16
// ... isn't the site revealing too much...
// (... what's with this bug?)
#include "molecules.h"
#include<vector>
#include<algorithm>
#include<numeric>
#if not LOCAL
#define NDEBUG 1
#endif
#include<cassert>

std::vector<int> find_subset(int l, int u, std::vector<int> w) {
	struct Item{int index, value;};
	std::vector<Item> items(w.size());
	for(int index=0; index<(int)w.size(); ++index)
		items[index]={index, w[index]};
	std::sort(begin(items), end(items),[&](Item first, Item sec){return first.value<sec.value;});

	int count;
	{
		std::vector<int64_t> tmp; tmp.reserve(items.size());
		for(auto& it: items) tmp.push_back(it.value);
		std::partial_sum(begin(tmp), end(tmp), tmp.begin());

		count=0; // maximum such that minimum sum <= u
		for(int step=1<<30; step>>=1;)
			if(count+step<=(int)tmp.size() and tmp[count+step-1]<=u)
				count+=step;

		auto const maxSum=tmp.back()-(count==(int)tmp.size()? 0: tmp.end()[-1-count]);
		if(maxSum<l)
			return {};
	}
	// so maximum sum >=l and minimum sum <=u

	std::vector<char> mark(w.size());
	int countLeft=count, countRight=0;
	int64_t total=0;
	for(int i=0; i<count; ++i){
		mark[i]=true;
		total+=items[i].value;
	}

	assert(total<=u);
	while(total<l){
		--countLeft; ++countRight;
		assert(mark[countLeft]); assert(not mark[w.size()-countRight]);
		int64_t const total1=total-items[countLeft].value+items[w.size()-countRight].value;
		if(total1>u){
			int i=countLeft;
			while(total<l){
				assert(mark[i]); assert(not mark[i+1]);
				mark[i]=false; mark[i+1]=true;
				total+=items[i+1].value-items[i].value;
				++i;
			}
			assert(total<=u);
			break;
		}else{
			total=total1;
			mark[countLeft]=false; mark[w.size()-countRight]=true;
		}
	}

	int64_t total_{};
	std::vector<int> result; result.reserve(count);
	for(int index=0; index<w.size(); ++index)
		if(mark[index]){
			result.push_back(items[index].index);
			total_+=items[index].value;
		}
	assert(total==total_);
	assert(l<=total); assert(total<=u);
	return result;
}

Compilation message (stderr)

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

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