Submission #139005

#	Time	Username	Problem	Language	Result	Execution time	Memory
139005		MAMBA	Mechanical Doll (IOI18_doll)	C++17	85.55 / 100	658 ms	20100 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>

using namespace std;

#define rep(i , j , k) for(int i = j; i < (int)k; i++)
#define pb push_back
#define all(x) x.begin(),x.end()

typedef vector<int> vi;

const int N = 2e5 + 10;

vi C , X  ,Y, nx[N];

int n, cnt = 1;

inline int inve(int sz , int l) {
	int res = 0;
	rep(i , 0 , sz)
		if (l & (1 << i))
			res ^= (1 << (sz - 1 - i));
	return res;
}

int build(int root, int lvl , int &g, int st = 0) {
	if ((g >> lvl) & 1) {
		g -= (1 << lvl);
		return root;
	}
	if (lvl == 0) return -(N + st);
	int me = cnt++;
	X.pb(0);
	Y.pb(0);
	X[me - 1] = -build(root , lvl - 1, g , st);
	Y[me - 1] = -build(root , lvl - 1, g , st + (1 << (lvl - 1)));
	return me;
}

void build(vi vec) {
	int z = 0;
	while ((1 << z) < (int)vec.size()) z++;
	int st = cnt;
	int g = (1 << z) - vec.size();


	build(cnt , z , g);


	vi k;
	rep(i , st - 1 , cnt - 1) {
		if (X[i] >= N) k.pb(X[i] - N);
		if (Y[i] >= N) k.pb(Y[i] - N);
	}

	auto cmp = [&](int a, int b) {
		return inve(z , a) < inve(z , b);
	};


	sort(all(k) , cmp);


	map<int , int> mp;
	rep(i , 0 , k.size())
		mp[k[i]] = i;

	rep(i , st - 1, cnt - 1) {
		if (X[i] >= N) X[i] = vec[mp[X[i] - N]];
		if (Y[i] >= N) Y[i] = vec[mp[Y[i] - N]];
	}

}

void create_circuit(int M, vi A) {
	n = A.size();
	A.pb(0);

	rep(i , 0 , n) 
		nx[A[i]].pb(A[i + 1]);

	C.resize(M + 1);

	C[0] = A[0];

	rep(i , 1 , M + 1) {
		if (nx[i].empty()) 
			C[i] = 0;
		else if (nx[i].size() == 1) {
			C[i] = nx[i][0];
		}
		else {
			C[i] = -cnt;
			build(nx[i]);
		}
	}


	answer(C , X , Y);
	return;
}

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