Submission #769078

#	Time	Username	Problem	Language	Result	Execution time	Memory
769078		SanguineChameleon	Mechanical Doll (IOI18_doll)	C++17	53 / 100	73 ms	10868 KiB

doll

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

vector<int> A, C, X, Y, all_cnt, cur_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;
	all_cnt.resize(M + 1);
	cur_cnt.resize(M + 1);
	for (int i = 0; i < N; i++) {
		all_cnt[A[i]]++;
	}
	bool sub3 = true;
	for (int i = 1; i <= M; i++) {
		if (all_cnt[i] > 2) {
			sub3 = false;
			break;
		}
	}
	if (sub3) {
		C.resize(M + 1);
		C[0] = A[0];
		int K = 0;
		for (int i = 1; i <= M; i++) {
			if (all_cnt[i] == 2) {
				K++;
				C[i] = -K;
			}
		}
		X.resize(K);
		Y.resize(K);
		for (int i = 0; i < N; i++) {
			cur_cnt[A[i]]++;
			int nxt = (i + 1 < N ? A[i + 1] : 0);
			if (all_cnt[A[i]] == 1) {
				C[A[i]] = nxt;
			}
			if (all_cnt[A[i]] == 2) {
				if (cur_cnt[A[i]] == 1) {
					X[-C[A[i]] - 1] = nxt;
				}
				else {
					Y[-C[A[i]] - 1] = nxt;
				}
			}
		}
		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: 4 / 4
• Subtask 3: 0 / 10
• Subtask 4: 10 / 10
• Subtask 5: 9.0000000036 / 18
• Subtask 6: 28.0000000112 / 56