Submission #147106

#	Time	Username	Problem	Language	Result	Execution time	Memory
147106		dolphingarlic	Mechanical Doll (IOI18_doll)	C++14	100 / 100	146 ms	10396 KiB

doll

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

int N, P = 1, switches = 1;
vector<int> X(1<<19), Y(1<<19);
bool state[1<<19];

int build(int l, int r) {
	if (l >= r) return 0;
	if (r < P - N) return -1;

	int ts = switches++, mid = (l + r) / 2;
	X[ts - 1] = build(l, mid);
	Y[ts - 1] = build(mid + 1, r);
	return -ts;
}

void point(int i, int j) {
	int &a = state[-i] ? Y[-i - 1] : X[-i - 1];
	state[-i] = !state[-i];

	if (!a) a = j;
	else point(a, j);
}

void create_circuit(int M, vector<int> A) {
	N = A.size();
    while (P < N) P *= 2;

	build(0, P - 1);

	for (int i = 1; i < N; i++) point(-1, A[i]);
	if (N & 1) point(-1, -1);
	point(-1, 0);

	X.resize(switches), Y.resize(switches);
	vector<int> C(M + 1, -1);
	C[0] = A[0];

    answer(C, X, 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