Submission #769742

#	Time	Username	Problem	Language	Result	Execution time	Memory
769742		SanguineChameleon	Mechanical Doll (IOI18_doll)	C++17	100 / 100	58 ms	12180 KiB

doll

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

void create_circuit(int M, vector<int> A) {
	int N = A.size();
	A.push_back(M + 1);
	vector<int> C(M + 1);
	C[0] = A[0];
	if (N == 1) {
		C[A[0]] = 0;
		answer(C, vector<int>(), vector<int>());
		return;
	}
	int K = 0;
	while ((1 << K) < N) {
		K++;
	}
	vector<int> X;
	vector<int> Y;
	vector<int> cur_layer(1 << K, M + 1);
	int cnt = 0;
	for (int i = 0; i < (1 << K) - 1; i++) {
		int last = 0;
		for (int j = 0; j < K; j++) {
			last |= ((i >> j) & 1) << (K - 1 - j);
		}
		if (last < ((1 << K) - N)) {
			continue;
		}
		cur_layer[last] = A[++cnt];
	}
	cur_layer[(1 << K) - 1] = 0;
	cnt = 0;
	for (int i = K - 1; i >= 0; i--) {
		vector<int> nxt_layer(1 << i, M + 1);
		for (int j = 0; j < (1 << i); j++) {
			if (cur_layer[j << 1] != M + 1 || cur_layer[j << 1 | 1] != M + 1) {
				cnt++;
				nxt_layer[j] = -cnt;
				X.push_back(cur_layer[j << 1]);
				Y.push_back(cur_layer[j << 1 | 1]);
			}
		}
		cur_layer.swap(nxt_layer);
	}
	for (int i = 1; i <= M; i++) {
		C[i] = cur_layer[0];
	}
	for (int i = 0; i < cnt; i++) {
		if (X[i] == M + 1) {
			X[i] = cur_layer[0];
		}
		if (Y[i] == M + 1) {
			Y[i] = cur_layer[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