Submission #425415

#	Time	Username	Problem	Language	Result	Execution time	Memory
425415		frodakcin	Cave (IOI13_cave)	C++17	100 / 100	258 ms	452 KiB

cave

#include "cave.h"
#include <cstring>
#include <vector>
#include <numeric>
#include <cassert>

void exploreCave(int N)
{
	int S[N], D[N]; // vla legal ?
	memset(S, 0, sizeof S);

	std::vector<int> cand(N);
	std::iota(cand.begin(), cand.end(), 0);

	for(int i=0;i<N;++i)
	{
		int v = tryCombination(S);
		assert(v == -1 || v >= i);
		bool down = v==i;
		int l=0, r=cand.size();
		for(;r-l>1;)
		{
			int m=l+(r-l)/2;
			for(int j=l;j<m;++j) S[cand[j]]^=1;
			v = tryCombination(S);
			assert(v == -1 || v >= i);
			for(int j=l;j<m;++j) S[cand[j]]^=1;
			if((v==i) == down)
				l=m;
			else
				r=m;
		}
		if(down)
			S[cand[l]] ^= 1;

		D[cand[l]]=i;
		cand.erase(cand.begin()+l);
	}

	answer(S, D);
}

• Subtask 1: 12 / 12
• Subtask 2: 13 / 13
• Subtask 3: 21 / 21
• Subtask 4: 30 / 30
• Subtask 5: 24 / 24