oj.uz

Submission #235550

# Submission time Handle Problem Language Result Execution time Memory
235550 2020-05-28T13:54:05 Z pit4h Mechanical Doll (IOI18_doll) C++14
100 / 100
 157 ms 12216 KB 
#include<bits/stdc++.h>
#define st first
#define nd second
#define pii pair<int, int>
#include "doll.h"
using namespace std;
const int MAXN =4e5+5;
int n, base=1, e[2*MAXN][2], rep[2*MAXN];
bool turn[2*MAXN];
void get_edges(int id, int l, int r) {	
	if(l==r) {
		if((base-l) * 2 >= n) {
			e[id][1]=1;
		}
		if((base-l) * 2 + 1 >= n) {
			e[id][0]=1;
		}
		return;
	}
	int m = (l+r)/2;
	e[id][0] = id*2;
	e[id][1] = id*2+1;
	if((base-r) * 2 >= n) {
		e[id][1]=1;
	}
	if((base-m) * 2 >= n) {
		e[id][0]=1;
	}
	if(e[id][0]==id*2) {
		get_edges(id*2, l, m);
	}
	if(e[id][1]==id*2+1) {
		get_edges(id*2+1, m+1, r);
	}
}
void simulate(int id, int v) {
	int nxt = e[id][turn[id]];
	turn[id] ^= 1;
	if(!nxt) {
		e[id][!turn[id]]=-v;
		return;
	}
	simulate(nxt, v);
}
void create_circuit(int m, vector<int> a) {
	vector<int> c(m+1);
	c[0]=a[0];
	a.push_back(0);
	a.erase(a.begin());
	n = a.size();
	for(int i=1; i<=m; ++i) {
		c[i]=-1;
	}	
	while(base < n) {
		base *= 2;
	}
	get_edges(1, 1, base);
	for(int i: a) {
		simulate(1, i);
	}
	int nr = 0;
	for(int i=1; i<2*base; ++i) {
		if(e[i][0]!=0 || e[i][1]!=0) {
			rep[i]=++nr;
		}
	}
	vector<int> x(nr), y(nr);
	for(int i=1; i<2*base; ++i) {
		if(rep[i]!=0) {
			if(e[i][0]<=0) {
				x[rep[i]-1]=-e[i][0];
			}
			else {
				x[rep[i]-1]=-rep[e[i][0]];
			}
			if(e[i][1]<=0) {
				y[rep[i]-1]=-e[i][1];
			}
			else {
				y[rep[i]-1]=-rep[e[i][1]];
			}
		}
	}
	answer(c, x, y);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 204 KB Output is correct
2 Correct 48 ms 4444 KB Output is correct
3 Correct 48 ms 4536 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 11 ms 1484 KB Output is correct
6 Correct 84 ms 6672 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 2 ms 204 KB Output is correct
2 Correct 48 ms 4444 KB Output is correct
3 Correct 48 ms 4536 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 11 ms 1484 KB Output is correct
6 Correct 84 ms 6672 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 82 ms 8004 KB Output is correct
9 Correct 127 ms 8476 KB Output is correct
10 Correct 145 ms 12216 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 2 ms 204 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 204 KB Output is correct
2 Correct 48 ms 4444 KB Output is correct
3 Correct 48 ms 4536 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 11 ms 1484 KB Output is correct
6 Correct 84 ms 6672 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 82 ms 8004 KB Output is correct
9 Correct 127 ms 8476 KB Output is correct
10 Correct 145 ms 12216 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 2 ms 204 KB Output is correct
14 Correct 143 ms 11840 KB Output is correct
15 Correct 97 ms 7720 KB Output is correct
16 Correct 132 ms 11604 KB Output is correct
17 Correct 1 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 138 ms 12020 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 2 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 74 ms 6772 KB Output is correct
3 Correct 97 ms 6788 KB Output is correct
4 Correct 135 ms 10268 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 74 ms 6772 KB Output is correct
3 Correct 97 ms 6788 KB Output is correct
4 Correct 135 ms 10268 KB Output is correct
5 Correct 132 ms 11484 KB Output is correct
6 Correct 157 ms 11340 KB Output is correct
7 Correct 130 ms 11340 KB Output is correct
8 Correct 138 ms 11016 KB Output is correct
9 Correct 80 ms 6844 KB Output is correct
10 Correct 157 ms 10996 KB Output is correct
11 Correct 136 ms 10672 KB Output is correct
12 Correct 89 ms 7096 KB Output is correct
13 Correct 82 ms 7460 KB Output is correct
14 Correct 94 ms 7500 KB Output is correct
15 Correct 94 ms 7668 KB Output is correct
16 Correct 3 ms 588 KB Output is correct
17 Correct 73 ms 7076 KB Output is correct
18 Correct 81 ms 7024 KB Output is correct
19 Correct 83 ms 7080 KB Output is correct
20 Correct 125 ms 10856 KB Output is correct
21 Correct 143 ms 10648 KB Output is correct
22 Correct 128 ms 10636 KB Output is correct