Submission #415451

#	Time	Username	Problem	Language	Result	Execution time	Memory
415451		_fractal	Mechanical Doll (IOI18_doll)	C++14	47 / 100	248 ms	12060 KiB

doll

#include "doll.h"
#include <iostream>

using namespace std;

vector<int> X, Y;
vector<int> XX, YY;
vector<int> was;
int S;

void rec(int pos, int val) {
	if (was[pos] == 0) {
		if (XX[pos] == 0) {
			X[pos] = val;
			XX[pos] = 1;
			was[pos] ^= 1;
			return;
		}
		else {
			was[pos] ^= 1;
			rec(-X[pos] - 1, val);
		}
	}
	else {
		if (YY[pos] == 0) {
			YY[pos] = 1;
			Y[pos] = val;
			was[pos] ^= 1;
			return;
		}
		else {
			was[pos] ^= 1;
			rec(-Y[pos] - 1, val);
		}
	}
}

void build(int v, int cur, int len) {
	if (cur < len) {
		XX[v] = 1;
		YY[v] = 1;
		S++;
		X[v] = -S;
		was.push_back(0);
		X.push_back(0), Y.push_back(0);
		XX.push_back(0), YY.push_back(0);
		S++;
		Y[v] = -S;
		was.push_back(0);
		X.push_back(0), Y.push_back(0);
		XX.push_back(0), YY.push_back(0);
		build(-X[v] - 1, cur + 1, len);
		build(-Y[v] - 1, cur + 1, len);
	}
	else {
		return;
	}
}

void create_circuit(int M, vector<int> A) {
	int N = A.size();
	vector<int> C(M + 1);
	X.clear(), Y.clear();
	A.push_back(0);
	C[0] = A[0];
	int n = 1, len = 0;
	while (n < N)
		n <<= 1, len++;
	N++;
	S++;
	was.push_back(0);
	X.push_back(0), Y.push_back(0);
	XX.push_back(0), YY.push_back(0);
	for (int i = 1; i <= M; ++i)
		C[i] = -S;
	build(0, 1, len);
	for (int i = 1; i < N - 1; ++i)
		rec(0, A[i]);
	for (int i = N - 2; i < n - 1; ++i)
		rec(0, -1);
	rec(0, A[N - 1]);
	answer(C, X, Y);
}

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