Submission #830731

#	Time	Username	Problem	Language	Result	Execution time	Memory
830731		tranxuanbach	Mechanical Doll (IOI18_doll)	C++17	100 / 100	85 ms	18076 KiB

doll

#include "doll.h"

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

#define For(i, l, r) for (auto i = (l); i < (r); i++)
#define ForE(i, l, r) for (auto i = (l); i <= (r); i++)
#define FordE(i, l, r) for (auto i = (l); i >= (r); i--)
#define isz(a) ((signed)a.size())

const int N = 2e5 + 5, M = 1e5 + 5, S = 2 * N;
const int inf = 1e9 + 7;

int n, m;
int a[N];

int s;
int ans[M];
int ansx[S], ansy[S];

int layer;
int order[S];
vector <pair <int, int>> leaves;
int par[S];

int index_reorder[S];

void reorder(){
	int cntdone = 0;
	ForE(u, 1, s){
		if (ansx[u] == inf and ansy[u] == inf){
			continue;
		}
		index_reorder[u] = ++cntdone;
	}
	ForE(u, 1, s){
		if (ansx[u] == inf and ansy[u] == inf){
			continue;
		}
		if (ansx[u] < 0){
			ansx[u] = -index_reorder[-ansx[u]];
		}
		if (ansy[u] < 0){
			ansy[u] = -index_reorder[-ansy[u]];
		}
		swap(ansx[u], ansx[index_reorder[u]]);
		swap(ansy[u], ansy[index_reorder[u]]);
	}
	s = cntdone;
}

void create_circuit(int _m, vector <int> _a){
	n = isz(_a);
	m = _m;
	For(i, 0, n){
		a[i] = _a[i];
	}

	a[n] = 0;
	n++;

	ans[0] = -1;
	ForE(i, 1, m){
		ans[i] = -1;
	}
	fill(ansx + 1, ansx + S, inf);
	fill(ansy + 1, ansy + S, inf);
	
	layer = 0;
	while ((1 << layer) < n){
		layer++;
	}
	s = (1 << layer) - 1;

	FordE(u, -1, -(1 << (layer - 1)) + 1){
		ansx[-u] = u * 2;
		par[-(u * 2)] = u;
		ansy[-u] = u * 2 - 1;
		par[-(u * 2 - 1)] = u;
	}
	For(i, 0, (1 << layer)){
		int u = 0;
		For(bit, 0, layer){
			u = u * 2 + (i >> bit & 1);
		}
		order[u] = i;
	}
	For(u, (1 << layer) - n, (1 << layer)){
		leaves.emplace_back(order[u], u);
	}
	sort(leaves.begin(), leaves.end());
	For(i, 0, n){
		int u = leaves[i].second;
		int p = -(u / 2) - (1 << (layer - 1));
		if (u % 2 == 0){
			ansx[-p] = a[i];
		}
		else{
			ansy[-p] = a[i];
		}
	}

	ForE(u, -s, -1){
		if (ansx[-u] == inf and ansy[-u] == inf){
			int p = par[-u];
			if (ansx[-p] == u){
				ansx[-p] = inf;
			}
			else{
				ansy[-p] = inf;
			}
			continue;
		}
		if (ansy[-u] == inf){
			ansy[-u] = -1;
		}
		if (ansx[-u] == inf){
			ansx[-u] = -1;
		}
	}
	reorder();
	answer(vector <int>(ans, ans + m + 1), vector <int>(ansx + 1, ansx + s + 1), vector <int>(ansy + 1, ansy + s + 1));
}

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