Submission #769069

#	Time	Username	Problem	Language	Result	Execution time	Memory
769069		SanguineChameleon	Mechanical Doll (IOI18_doll)	C++17	47 / 100	61 ms	9768 KiB

doll

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

vector<int> A, C, X, Y;
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;
	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: 0 / 2
• Subtask 2: 0 / 4
• Subtask 3: 0 / 10
• Subtask 4: 10 / 10
• Subtask 5: 9.0000000036 / 18
• Subtask 6: 28.0000000112 / 56