Submission #541978

#	Time	Username	Problem	Language	Result	Execution time	Memory
541978		sliviu	Mechanical Doll (IOI18_doll)	C++17	66.60 / 100	136 ms	10052 KiB

doll

#include <bits/stdc++.h>
#include "doll.h"

using namespace std;

void create_circuit(int m, vector<int> a) {
	if (!(a.size() & 1))
		a.emplace_back(-1);
	a.emplace_back(0);
	int n = a.size(), p = 1, k = 1;
	vector<int> c(m + 1, -1), x(400001), y(400001), parity(400001);
	while (p < n)
		p *= 2;
	function<int(int, int)> Build = [&](int left, int right) {
		if (left == right)
			return 0;
		if (right < p - n)
			return -1;
		int m = (left + right) / 2, cur = k++;
		x[cur - 1] = Build(left, m), y[cur - 1] = Build(m + 1, right);
		return -cur;
	};
	Build(0, p - 1);
	for (int i = 0; i < n; ++i) {
		int cur = -1;
		while (cur) {
			int& next = !parity[-cur - 1] ? x[-cur - 1] : y[-cur - 1];
			parity[-cur - 1] ^= 1;
			cur = next;
			if (!next)
				next = a[i];
		}
	}
	x.resize(k), y.resize(k);
	answer(c, x, y);
}

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