Submission #97058

#	Time	Username	Problem	Language	Result	Execution time	Memory
97058		youngyojun	Mechanical Doll (IOI18_doll)	C++11	100 / 100	155 ms	10872 KiB

doll

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

const int MAXN = 200055;

int B[MAXN*2][2], C[MAXN*2];

int A[MAXN];

int N, M, K, NP;

int f(int s, int e) {
	if(N <= s) return 1;
	if(s == e) return -1;
	int m = (s+e) >> 1, c = ++K;
	B[c][1] = f(s, m);
	B[c][0] = f(m+1, e);
	return c;
}

void solve() {
	N++; for(NP = 2; NP < N; NP <<= 1);
	f(0, NP-1);
	for(int i = 1, c = 0; c < N;) {
		int &j = B[i][C[i]&1]; C[i]++;
		if(j < 0) {
			j = -A[c++];
			i = 1;
			continue;
		}
		i = j;
	}

	vector<int> CV(M+1, -1), LV, RV;
	for(int i = 1; i <= K; i++) {
		LV.eb(-B[i][0]);
		RV.eb(-B[i][1]);
	}
	answer(CV, LV, RV);
}

void create_circuit(int M, std::vector<int> A) {
	::M = M; ::N = A.size();
	for(int i = 0; i < ::N; i++) ::A[i] = A[i];
	solve();
}

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