Submission #250397

#	Time	Username	Problem	Language	Result	Execution time	Memory
250397		ernestvw	Mechanical Doll (IOI18_doll)	C++11	85.55 / 100	175 ms	19576 KiB

doll

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

#define sz(x) ((int)x.size())

void answer(vector<int> C, vector<int> X, vector<int> Y);

const int K = 1000*1000;

int n, m;
vector<int> a;
vector<vector<int>> adj;

int p = 0;
vector<int> c, x, y;

int new_switch(int g, int d) {
	p++;
	x.push_back(g);
	y.push_back(d);
	return -p;
}

int new_switch(int g) {
	p++;
	x.push_back(-p);
	y.push_back(g);
	return -p;
}

struct node {
	int g, d, st, val;
};

vector<node> tree;

int newNode(int a = 0, int b = 0) {
	tree.push_back({a, b, 0, -1});
	return sz(tree)-1;
}

int buildTree(int t) {
	if(sz(adj[t]) == 2)
		return newNode(-2, -2);
	vector<int> nodes;
	int pr = 1;
	while(pr < sz(adj[t])) pr *= 2;
	for(int i = 0; i < pr / 4; ++i) nodes.push_back(newNode(-2, -2));
	vector<int> sh;
	for(int i = 0; i < sz(adj[t])/2-pr/4; ++i)
		sh.push_back(newNode(-2, -2));
	if(sz(adj[t])%2 == 1) sh.push_back(newNode(-K-K, -2));
	while(sz(sh) < pr / 4) sh.push_back(newNode(-K-K, -K-K));
	reverse(sh.begin(), sh.end());
	for(auto i : sh) nodes.push_back(i);
	if(sz(adj[t]) % 2 == 1)
		tree[nodes.back()].d = -2;
	vector<int> oldNodes;
	while(sz(nodes) > 1) {
		oldNodes = nodes;
		nodes.clear();
		for(int i = 0; i < sz(oldNodes); i += 2) {
			int u = oldNodes[i], v = oldNodes[i + 1];
			if(tree[v].g == -K-K && tree[v].d == -K-K) {
				nodes.push_back(v);
				continue;
			}
			if(tree[u].g == -K-K && tree[u].d == -K-K) {
				nodes.push_back(newNode(-K-K, v));
				continue;
			}
			nodes.push_back(newNode(u, v));
		}
	}
	return nodes[0];

}

void printTree(int u) {
	if(u < 0) {
//		cout << u;
		if(u == -K-K) cout << -1;
		// u=-3-x, -u=3+x, x=-u-3
		else cout << -u-K;
		return;
	}
	cout << "(";
	printTree(tree[u].g);
	cout << ")";
	cout << u;
	cout << "(";
	printTree(tree[u].d);
	cout << ")";
}

int Cnt = 0;
int Root = 0;

void parcourir(int u, int t) {
	if(Cnt == sz(adj[t])) return;
	if(tree[u].st == 0) {
		tree[u].st = 1;
		if(tree[u].g < 0) {
			if(tree[u].g != -K-K)
				tree[u].g = -K-adj[t][Cnt++];
			parcourir(Root, t);
		}
		else parcourir(tree[u].g, t);
	}
	else {
		tree[u].st = 0;
		if(tree[u].d < 0) {
			if(tree[u].d != -K-K)
				tree[u].d = -K-adj[t][Cnt++];
			parcourir(Root, t);
		}
		else parcourir(tree[u].d, t);
	}
}

int MOM = -1;

int construire(int u) {
	if(u < 0) {
		if(u == -K-K) return MOM;
		if(u > -K) return u;
		return -K-u;
	}
	if(u == Root) {
		MOM = new_switch(0, 0);
		int g = construire(tree[u].g);
		int d = construire(tree[u].d);
		x[-MOM-1] = g;
		y[-MOM-1] = d;
		return MOM;
	}
	int g = construire(tree[u].g);
	int d = construire(tree[u].d);
	return new_switch(g, d);
}

int create(int t) {
	if(sz(adj[t]) == 0) return 0;
	if(sz(adj[t]) == 1) return adj[t][0];
	int root = buildTree(t);

//	printTree(root);
//	cout << endl;

	Cnt = 0;
	Root = root;

	parcourir(root, t);

//	printTree(root);
//	cout << endl;

	return construire(root);
}

vector<int> liste;
int PR = 1;
int mom = -1;

int build(int X, int pr) {
	if(pr == 1) {
		mom = new_switch(0, 0);
		int g = build(X, 2 * pr);
		int d = build(X + pr, 2 * pr);
		x[-mom-1] = g;
		y[-mom-1] = d;
		return mom;
	}
	if(pr == PR) return (liste[X] == -1 ? mom : liste[X]);
	int g = build(X, 2 * pr);
	int d = build(X + pr, 2 * pr);
	return new_switch(g, d);
}

int Create(int t) {
	if(sz(adj[t]) == 0) return 0;
	if(sz(adj[t]) == 1) return adj[t][0];
	int pr = 1;
	while(pr < sz(adj[t])) pr *= 2;
	PR = pr;
	liste.assign(pr, -1);
	for(int i = 0; i < pr - sz(adj[t]); ++i)
		liste[i] = -1;
	for(int i = pr - sz(adj[t]); i < pr; ++i)
		liste[i] = adj[t][i - pr + sz(adj[t])];
	return build(0, 1);
}

void create_circuit(int M, vector<int> A) {
	n = (int)A.size();
	m = M;
	a = A;

	c.assign(m + 1, 0);

	adj.assign(m + 1, vector<int>());
	for(int i = 0; i < n - 1; ++i)
		adj[a[i]].push_back(a[i + 1]);
	adj[0].push_back(a[0]);
	adj[a.back()].push_back(0);
	
	for(int i = 0; i <= m; ++i)
		c[i] = create(i);
	
	answer(c, x, y);
}

• 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