Submission #287979

#	Time	Username	Problem	Language	Result	Execution time	Memory
287979		user202729	The Big Prize (IOI17_prize)	C++17	100 / 100	64 ms	5352 KiB

prize

// moreflags=grader.cpp
// 11
// :(
#include "prize.h"
#if not LOCAL
#define NDEBUG
#endif
#include<vector>
#include<algorithm>
#include<cassert>

std::vector<std::vector<int>> result;

int find_best(int const n) {
	/*
	if(n<=5000){
		for(int i = 0; ; i++) {
			assert(i<n);
			std::vector<int> res = ask(i);
			if(res[0] + res[1] == 0)
				return i;
		}
	}
	assert(n>5000);
	*/
	
	result.clear(); result.resize(n);
	auto const ask=[&](int pos)->void{
		if(result[pos].empty())
			result[pos]=::ask(pos);
	};

	int maxTotal{};
	for(int index=0; index<473; ++index){
		auto const pos=n*index/473;
		ask(pos);
		maxTotal=std::max(maxTotal, result[pos][0]+result[pos][1]);
	}
	// so far 473 questions asked

	auto const isLollipop=[&](int pos){
		return result[pos][0]+result[pos][1]==maxTotal;
	};

	for(int index=0; index<473; ++index){
		auto left=n*index/473, right=n*(index+1)/473;
		assert(not result[left].empty());
		assert(right==n or not result[right].empty());
		while(left+1<right and not isLollipop(left)) ask(++left);
	}
	// 473+x questions asked, x non-lollipops found

	auto const process=[&](auto process, int left, int right, int countRight, int delta){
		// given delta non-lollipops in (left..right), ask them all in k*delta questions
		// with right-left<=2**k-1
		// countRight=number of non-lollipops in (left..)
		if(delta==0) return;
		assert(delta>0);
		assert(countRight>=delta);
		assert(left<right);

		auto const middle=(left+right)>>1;
		ask(middle);
		int pos=middle;
		while(not isLollipop(pos)){
			++pos;
			if(pos==right) break;
			ask(pos);
		}
		auto const deltaMid=pos-middle;
		if(pos==right){
			for(int pos=middle; pos<right; ++pos) assert(not isLollipop(pos));
			process(process, left, middle, countRight, delta-deltaMid);
		}else{
			auto const countRight1=result[pos][1];
			auto const deltaLeft=countRight-countRight1-deltaMid;
			process(process, left, middle, countRight, deltaLeft);
			process(process, pos+1, right, result[pos][1], delta-deltaLeft-deltaMid);
		}
	};

	auto const cutCondition=[&](int pos){
		return pos==n or (not result[pos].empty() and isLollipop(pos));
	};
	for(int pos=0; pos<n; ++pos) if(cutCondition(pos)){
		int next=pos+1; while(not cutCondition(next)) ++next;
		int right=next;
		while(pos+1<right and not result[right-1].empty()){
			assert(not isLollipop(right-1));
			--right;
		}
		if(pos+1==right) continue;

		assert(std::all_of(result.begin()+pos+1, result.begin()+right, [&](auto const& it){
			return it.empty();}));
		for(int pos=right; pos<next; ++pos)
			assert(not isLollipop(pos));

		assert(isLollipop(pos)); assert(next==n or isLollipop(next));
		int const delta=result[pos][1]-(next==n ? 0: result[next][1]);
		process(process, pos+1, right, result[pos][1], delta-(next-right));
	}

	// all non-lollipops found
	for(int pos=0;; ++pos) if(not result[pos].empty() and result[pos][0]==0 and result[pos][1]==0)
		return pos;
}

• Subtask 1: 20 / 20
• Subtask 2: 80 / 80