oj.uz

Submission #250398

# Submission time Handle Problem Language Result Execution time Memory
250398 2020-07-17T17:05:33 Z ernestvw Mechanical Doll (IOI18_doll) C++11
100 / 100
 202 ms 20732 KB 
#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);
	
	adj[0] = A;
	adj[0].push_back(0);
	
	for(int i = 0; i <= 0; ++i)
		c[i] = create(i);
	
	for(int i = 1; i <= m; ++i)
		c[i] = c[0];
	
	answer(c, x, y);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 62 ms 11144 KB Output is correct
3 Correct 54 ms 9780 KB Output is correct
4 Correct 3 ms 204 KB Output is correct
5 Correct 14 ms 3788 KB Output is correct
6 Correct 82 ms 14328 KB Output is correct
7 Correct 1 ms 204 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 62 ms 11144 KB Output is correct
3 Correct 54 ms 9780 KB Output is correct
4 Correct 3 ms 204 KB Output is correct
5 Correct 14 ms 3788 KB Output is correct
6 Correct 82 ms 14328 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 137 ms 14264 KB Output is correct
9 Correct 121 ms 16560 KB Output is correct
10 Correct 184 ms 20732 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 62 ms 11144 KB Output is correct
3 Correct 54 ms 9780 KB Output is correct
4 Correct 3 ms 204 KB Output is correct
5 Correct 14 ms 3788 KB Output is correct
6 Correct 82 ms 14328 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 137 ms 14264 KB Output is correct
9 Correct 121 ms 16560 KB Output is correct
10 Correct 184 ms 20732 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 168 ms 18324 KB Output is correct
15 Correct 96 ms 12020 KB Output is correct
16 Correct 144 ms 17296 KB Output is correct
17 Correct 2 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 201 ms 19352 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 79 ms 10004 KB Output is correct
3 Correct 90 ms 10040 KB Output is correct
4 Correct 117 ms 14208 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 79 ms 10004 KB Output is correct
3 Correct 90 ms 10040 KB Output is correct
4 Correct 117 ms 14208 KB Output is correct
5 Correct 202 ms 17560 KB Output is correct
6 Correct 167 ms 16792 KB Output is correct
7 Correct 151 ms 17036 KB Output is correct
8 Correct 131 ms 16232 KB Output is correct
9 Correct 80 ms 10056 KB Output is correct
10 Correct 154 ms 15536 KB Output is correct
11 Correct 135 ms 16020 KB Output is correct
12 Correct 80 ms 11260 KB Output is correct
13 Correct 91 ms 11672 KB Output is correct
14 Correct 114 ms 11912 KB Output is correct
15 Correct 96 ms 12260 KB Output is correct
16 Correct 3 ms 588 KB Output is correct
17 Correct 82 ms 9644 KB Output is correct
18 Correct 78 ms 10668 KB Output is correct
19 Correct 83 ms 10788 KB Output is correct
20 Correct 129 ms 15352 KB Output is correct
21 Correct 163 ms 15640 KB Output is correct
22 Correct 147 ms 14980 KB Output is correct