Submission #769076

#	Time	Username	Problem	Language	Result	Execution time	Memory
769076		SanguineChameleon	Mechanical Doll (IOI18_doll)	C++17	49 / 100	71 ms	10332 KiB

doll

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

vector<int> A, C, X, Y, cnt;
int N, M, K;

void build(int id, int depth, int cur) {
	if (depth == K - 1) {
		X[id - 1] = (cur < N - 1 ? A[cur + 1] : (cur == ((1 << K) - 1) ? 0 : -1));
		cur += 1 << depth;
		Y[id - 1] = (cur < N - 1 ? A[cur + 1] : (cur == ((1 << K) - 1) ? 0 : -1));
		return;
	}
	X[id - 1] = -(id * 2);
	Y[id - 1] = -(id * 2 + 1);
	build(id * 2, depth + 1, cur);
	build(id * 2 + 1, depth + 1, cur + (1 << depth));
}

void create_circuit(int _M, vector<int> _A) {
	A = _A;
	N = A.size();
	M = _M;
	cnt.resize(M + 1);
	for (int i = 0; i < N; i++) {
		cnt[A[i]]++;
	}
	bool sub3 = true;
	for (int i = 1; i <= M; i++) {
		if (cnt[i] > 1) {
			sub3 = false;
			break;
		}
	}
	if (sub3) {
		C.resize(M + 1);
		C[0] = A[0];
		for (int i = 0; i < N; i++) {
			if (cnt[A[i]] == 1) {
				C[A[i]] = (i + 1 < N ? A[i + 1] : 0);
			}
		}
		answer(C, X, Y);
		return;
	}
	K = 0;
	while ((1 << K) < N) {
		K++;
	}
	C.resize(M + 1, -1);
	C[0] = A[0];
	if (K == 0) {
		answer(C, X, Y);
		return;
	}
	X.resize((1 << K) - 1);
	Y.resize((1 << K) - 1);
	build(1, 0, 0);
	answer(C, X, Y);
}

• 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