Submission #248075

#	Time	Username	Problem	Language	Result	Execution time	Memory
248075		user202729	Mechanical Doll (IOI18_doll)	C++17	100 / 100	116 ms	6496 KiB

doll

// moreflags=grader.cpp
// (I must have done this problem before...?)

#include "doll.h"

#ifndef LOCAL
#define NDEBUG 1
#endif
#include<cassert>

void create_circuit(int numTrigger, std::vector<int> steps) {
	int numLayer=1; while((1<<numLayer)<(int)steps.size()+1) ++numLayer;
	std::vector<int> base(numLayer+1);
	base[0]=0;
	for(int layer=0; layer<numLayer; ++layer)
		base[layer+1]=base[layer]+(int(steps.size())>>(layer+1))+1;

	auto const numSwitch=base.back();

	auto const size=[&](int layer){
		return base[layer+1]-base[layer];
	};
	assert(size(numLayer-1)==1);
	
	auto const root=base.end()[-2];

	std::vector<int> X(numSwitch), Y(numSwitch);
	for(int layer=1; layer<numLayer;++layer)
		for(int node=base[layer]; node<base[layer+1];++node){
			auto const position1=(node-base[layer])*2;
			Y[node]=-(1+(  position1+base[layer-1]  ));
			X[node]=-(1+(  position1+1<size(layer-1) ? position1+1+base[layer-1] : root  ));
		}

	assert(base[0]==0);

	int index=0; // into steps, with some special cases
	if((steps.size()+1)%2!=0) --index;

	for(int i=0; i<(1<<numLayer);++i){
		int j=0;
		for(int tmp=i, _=0; _<numLayer; ++_){ j=j<<1|(tmp&1); tmp>>=1; }

		auto const node=(1<<(numLayer-1))-1-(j>>1); bool const y=j&1;
		if(node<size(0)){
			(y ? Y[node]: X[node])=(index==-1 ? -(root+1) : index<(int)steps.size() ? steps[index] : 0);
			++index;
		}
	}

	answer(std::vector<int>(numTrigger+1, -(root+1)), std::move(X), std::move(Y));
}

• Subtask 1: 2 / 2
• Subtask 2: 4 / 4
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 18 / 18
• Subtask 6: 56 / 56