oj.uz

Submission #526906

# Submission time Handle Problem Language Result Execution time Memory
526906 2022-02-16T15:55:23 Z benson1029 Mechanical Doll (IOI18_doll) C++14
100 / 100
 103 ms 16224 KB 
#include "doll.h"
#include<bits/stdc++.h>
using namespace std;

int n, N;
int x[800005], y[800005];
vector<int> C, X, Y;
vector< pair< int, pair<int,int> > > v;
int id;

int dfs(int i, int ord, int dep) {
	int tmp = ++id;
	X.push_back(x[i]);
	Y.push_back(y[i]);
	if(x[i] < -1) {
		X[tmp-1] = -dfs(-x[i], ord, dep+1);
	} else if(x[i] == 1) {
		v.push_back({ord, {tmp-1, 0} });
	}
	if(y[i] < -1) {
		Y[tmp-1] = -dfs(-y[i], ord+(1<<dep), dep+1);
	}else if(y[i] == 1) {
		v.push_back({ord+(1<<dep), {tmp-1, 1} });
	}
	return tmp;
}

void create_circuit(int M, std::vector<int> A) {
	if(A.size()==1) {
		C.push_back(A[0]);
		for(int i=0; i<M; i++) C.push_back(0);
		answer(C, X, Y);
		return;
	}
	n = A.size();
	A.push_back(0);
	N = 1;
	while(N < n) N*=2;
	int cnt = N-n;
	for(int i=N/2; i<N; i++) {
		if(cnt>0) {
			x[i] = -1;
			cnt--;
		} else {
			x[i] = 1;
		}
		if(cnt>0) {
			y[i] = -1;
			cnt--;
		} else {
			y[i] = 1;
		}
	}
	for(int i=N/2-1; i>=1; i--) {
		if(x[i*2] == -1 && y[i*2]==-1) {
			x[i] = -1;
		} else {
			x[i] = -i*2;
		}
		if(x[i*2+1]==-1 && y[i*2+1]==-1) {
			y[i] = -1;
		} else {
			y[i] = -(i*2+1);
		}
	}
	C.push_back(A[0]);
	for(int i=0; i<M; i++) C.push_back(-1);
	dfs(1, 0, 0);
	sort(v.begin(), v.end());
	int ptr = 0;
	for(auto i:v) {
		if(i.second.second==0) {
			X[i.second.first] = A[++ptr];
		} else {
			Y[i.second.first] = A[++ptr];
		}
	}
	answer(C, X, Y);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 216 KB Output is correct
2 Correct 32 ms 5676 KB Output is correct
3 Correct 30 ms 5960 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 10 ms 1604 KB Output is correct
6 Correct 54 ms 8240 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 0 ms 216 KB Output is correct
2 Correct 32 ms 5676 KB Output is correct
3 Correct 30 ms 5960 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 10 ms 1604 KB Output is correct
6 Correct 54 ms 8240 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 57 ms 10300 KB Output is correct
9 Correct 55 ms 11656 KB Output is correct
10 Correct 103 ms 16224 KB Output is correct
11 Correct 0 ms 208 KB Output is correct
12 Correct 1 ms 312 KB Output is correct
13 Correct 0 ms 208 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 216 KB Output is correct
2 Correct 32 ms 5676 KB Output is correct
3 Correct 30 ms 5960 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 10 ms 1604 KB Output is correct
6 Correct 54 ms 8240 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 57 ms 10300 KB Output is correct
9 Correct 55 ms 11656 KB Output is correct
10 Correct 103 ms 16224 KB Output is correct
11 Correct 0 ms 208 KB Output is correct
12 Correct 1 ms 312 KB Output is correct
13 Correct 0 ms 208 KB Output is correct
14 Correct 84 ms 16060 KB Output is correct
15 Correct 67 ms 11188 KB Output is correct
16 Correct 79 ms 15880 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 0 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 97 ms 16068 KB Output is correct
21 Correct 0 ms 204 KB Output is correct
22 Correct 1 ms 304 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 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 52 ms 8496 KB Output is correct
3 Correct 47 ms 9176 KB Output is correct
4 Correct 82 ms 12728 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 52 ms 8496 KB Output is correct
3 Correct 47 ms 9176 KB Output is correct
4 Correct 82 ms 12728 KB Output is correct
5 Correct 93 ms 14528 KB Output is correct
6 Correct 78 ms 13520 KB Output is correct
7 Correct 93 ms 13580 KB Output is correct
8 Correct 82 ms 13412 KB Output is correct
9 Correct 45 ms 9260 KB Output is correct
10 Correct 81 ms 13328 KB Output is correct
11 Correct 84 ms 13128 KB Output is correct
12 Correct 47 ms 9520 KB Output is correct
13 Correct 48 ms 9084 KB Output is correct
14 Correct 51 ms 9968 KB Output is correct
15 Correct 57 ms 10160 KB Output is correct
16 Correct 2 ms 588 KB Output is correct
17 Correct 55 ms 8672 KB Output is correct
18 Correct 64 ms 8672 KB Output is correct
19 Correct 48 ms 9440 KB Output is correct
20 Correct 74 ms 12724 KB Output is correct
21 Correct 95 ms 12956 KB Output is correct
22 Correct 95 ms 13084 KB Output is correct