Submission #249986

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
249986	2020-07-16T16:07:33 Z	ernestvw	Mechanical Doll (IOI18_doll)	C++11	6 / 100	87 ms	13080 KB

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);

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;
}

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

int build(int X, int pr) {
	if(pr == 1) {
		mom = new_switch(0, 0);
		x[-mom-1] = build(X, 2 * pr);
		y[-mom-1] = build(X + pr, 2 * pr);
		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];
	if(sz(adj[t]) == 2) return new_switch(adj[t][0], adj[t][1]);
	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);
}

/*int Create(int t, int i, int j) {
	if(i > j) return 0;
	if(i == j) return adj[t][i];
	if(i + 2 == j) {
		int p1 = new_switch(adj[t][i], adj[t][i + 1]);
		int p2 = new_switch(-p-2, adj[t][i + 2]);
		return new_switch(p1, p2);
	}
	if(i + 3 == j)
		return new_switch(new_switch(adj[t][i], adj[t][i + 2]), new_switch(adj[t][i + 1], adj[t][i + 3]));
	return new_switch(create(t, i, (i + j) / 2), create(t, (i + j) / 2 + 1, j));
}*/


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) {
		cout << i << ": ";
		for(int j : adj[i])cout<<j<<" ";
		cout<<endl;
	}
*/
	for(int i = 0; i <= m; ++i)
		c[i] = create(i);

	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	35 ms	6604 KB	Output is correct
3	Correct	28 ms	5420 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	15 ms	3788 KB	Output is correct
6	Correct	49 ms	8004 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	35 ms	6604 KB	Output is correct
3	Correct	28 ms	5420 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	15 ms	3788 KB	Output is correct
6	Correct	49 ms	8004 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	58 ms	7840 KB	Output is correct
9	Correct	67 ms	9116 KB	Output is correct
10	Correct	87 ms	11764 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
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	35 ms	6604 KB	Output is correct
3	Correct	28 ms	5420 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	15 ms	3788 KB	Output is correct
6	Correct	49 ms	8004 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	58 ms	7840 KB	Output is correct
9	Correct	67 ms	9116 KB	Output is correct
10	Correct	87 ms	11764 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	Runtime error	60 ms	13080 KB	Execution killed with signal 11
15	Halted	0 ms	0 KB	-