Submission #597157

#	Time	Username	Problem	Language	Result	Execution time	Memory
597157		Lucpp	Mechanical Doll (IOI18_doll)	C++17	84 / 100	1095 ms	11208 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>
using namespace std;

int S = 0;
vector<int> X, Y;
vector<int> state;

int build(int n, int h){
	if(h == 0) return 1;
	int ind = S++;
	X.resize(S);
	Y.resize(S);
	int k = (1<<(h-1));
	vector<int> le, ri;
	// cerr << n << " " << k << "\n";
	Y[ind] = build(min(k, n), h-1);
	if(k >= n){
		X[ind] = -1; // root
	}
	else{
		X[ind] = build(n-k, h-1);
	}
	return -(ind+1);
}

int exec(){
	int i = -1;
	while(true){
		int j = -i-1;
		if(state[j]) i = Y[j];
		else i = X[j];
		state[j] ^= 1;
		if(i == 1) return j;
		if(i == -1) return -1;
	}
}

void create_circuit(int M, vector<int> A) {
	A.push_back(0);
	int n = (int)A.size();
	int h = (int)ceil(log2(n));
	build(n, h);
	state.resize(S);
	int i = 0;
	while(i < n){
		int j = exec();
		if(j > 0){
			if(state[j]) X[j] = A[i++];
			else Y[j] = A[i++];
		}
	}
	vector<int> C(M + 1, -1);
	answer(C, X, Y);
}

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