oj.uz

Submission #75133

# Submission time Handle Problem Language Result Execution time Memory
75133 2018-09-08T12:44:38 Z Diuven Mechanical Doll (IOI18_doll) C++14
100 / 100
 165 ms 14124 KB 
#include "doll.h"
typedef std::vector<int> vi;

int n, m, s;
vi X, Y, C;
int L[400010], R[400010], rt;
bool state[400010];
int B[200010];

int make_tree(){
	vi Q, P;
	for(int i=1; i<=n; i++) Q.push_back(i);
	do{
		for(int i=0, sz=Q.size(); i<sz; i+=2){
			s++;
			int a=Q[i], b=(i+1<sz ? Q[i+1] : 0);
			L[s]=a, R[s]=b;
			P.push_back(-s);
		}
		Q.clear(); Q=P; P.clear();
	} while(Q.size()>1U);
	return -Q[0];
}

int find(int v=-rt){
	if(v>=0) return v;
	int ret=find(state[-v] ? L[-v] : R[-v]);
	state[-v]=!state[-v];
	return ret;
}

int f(int x){
	if(x==0) return -rt;
	if(x<0) return x;
	return B[x];
}

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

	C.resize(m+1), C[0]=A[0];

	rt=make_tree();
	for(int i=1; i<=m; i++) C[i]=-rt;

	int pos=1;
	while(pos<=n){
		int now=find();
		if(now==0) continue;
		B[now]=A[pos]; pos++;
	}

	for(int i=1; i<=s; i++){
		X.push_back(f(R[i]));
		Y.push_back(f(L[i]));
	}
	answer(C, X, Y);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 252 KB Output is correct
2 Correct 64 ms 5704 KB Output is correct
3 Correct 57 ms 5676 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 1480 KB Output is correct
6 Correct 91 ms 8552 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 252 KB Output is correct
2 Correct 64 ms 5704 KB Output is correct
3 Correct 57 ms 5676 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 1480 KB Output is correct
6 Correct 91 ms 8552 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 96 ms 9288 KB Output is correct
9 Correct 123 ms 10300 KB Output is correct
10 Correct 153 ms 14124 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 2 ms 252 KB Output is correct
2 Correct 64 ms 5704 KB Output is correct
3 Correct 57 ms 5676 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 1480 KB Output is correct
6 Correct 91 ms 8552 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 96 ms 9288 KB Output is correct
9 Correct 123 ms 10300 KB Output is correct
10 Correct 153 ms 14124 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 165 ms 13336 KB Output is correct
15 Correct 97 ms 8672 KB Output is correct
16 Correct 139 ms 13068 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 155 ms 13780 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 84 ms 7888 KB Output is correct
3 Correct 88 ms 7880 KB Output is correct
4 Correct 144 ms 11768 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 84 ms 7888 KB Output is correct
3 Correct 88 ms 7880 KB Output is correct
4 Correct 144 ms 11768 KB Output is correct
5 Correct 151 ms 13064 KB Output is correct
6 Correct 141 ms 12792 KB Output is correct
7 Correct 162 ms 12536 KB Output is correct
8 Correct 129 ms 12236 KB Output is correct
9 Correct 104 ms 7728 KB Output is correct
10 Correct 149 ms 12184 KB Output is correct
11 Correct 149 ms 11812 KB Output is correct
12 Correct 103 ms 7756 KB Output is correct
13 Correct 82 ms 8336 KB Output is correct
14 Correct 103 ms 8368 KB Output is correct
15 Correct 108 ms 8120 KB Output is correct
16 Correct 3 ms 588 KB Output is correct
17 Correct 92 ms 7724 KB Output is correct
18 Correct 87 ms 7344 KB Output is correct
19 Correct 97 ms 7288 KB Output is correct
20 Correct 163 ms 11280 KB Output is correct
21 Correct 130 ms 11128 KB Output is correct
22 Correct 158 ms 11172 KB Output is correct