Submission #230664

#	Time	Username	Problem	Language	Result	Execution time	Memory
230664		DrSwad	Mechanical Doll (IOI18_doll)	C++17	49 / 100	153 ms	15412 KiB

doll

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

using namespace std;

const int N = int(4e5) + 10;

int c[N];
int x[N], y[N];
int switches_used;

void create_circuit(int m, vector<int> a) {
	a.push_back(0);
	c[0] = a[0];
	int n = a.size();

	vector<vector<int>> v(m + 1);
	for (int i = 0; i < n - 1; i++) v[a[i]].push_back(a[i + 1]);

	for (int i = 1; i <= m; i++) {
		if (v[i].size() > 1) c[i] = -1;
		else if (v[i].size() == 1) c[i] = v[i].back();
	}
	vector<int> leaf;
	for (int i = 0; i < n - 1; i++)	{
		if (v[a[i]].size() > 1) leaf.push_back(a[i + 1]);
	}

	int total_leaves = leaf.size();
	if (total_leaves) {
		int lv = 0;
		while (1 << lv < total_leaves) {
			for (int i = 1 << lv; i < 1 << (lv + 1); i++) x[i] = - (i << 1), y[i] = - (i << 1 | 1);
			lv++;
		}

		for (int i = 1 << (lv - 1); i < 1 << lv; i++) x[i] = y[i] = -1;
		reverse(leaf.begin(), leaf.end());

		for (int i = 0; i < total_leaves; i++) {
			int i0 = (1 << (lv + 1)) - 1 - i;

			int r = 1 << lv;
			for (int j = 0; j < lv; j++) if (i0 >> j & 1) r |= 1 << (lv - 1 - j);

			if (r & 1) y[r >> 1] = leaf[i];
			else x[r >> 1] = leaf[i];
		}

		switches_used = (1 << lv) - 1;
	}

	answer(vector<int>(c + 0, c + m + 1), vector<int>(x + 1, x + switches_used + 1), vector<int>(y + 1, y + switches_used + 1));
}

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