oj.uz

Submission #75619

# Submission time Handle Problem Language Result Execution time Memory
75619 2018-09-10T14:19:50 Z gs14004 Mechanical Doll (IOI18_doll) C++17
100 / 100
 89 ms 10296 KB 
#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 400005;

int vtx_number, total_leaf;
int X[MAXN], Y[MAXN], mp[MAXN];

void dfs(int s, int e, int v, int d){
	vtx_number++;
	if(e - s == 1){
		if(s < total_leaf) X[vtx_number - 1] = -1;
		else X[vtx_number - 1] = v;
		Y[vtx_number - 1] = v ^ (1 << d);
		return;
	}
	int cur_vtx = vtx_number - 1;
	int m = (s + e) / 2;
	if(m < total_leaf){
		X[cur_vtx] = -1;
	}
	else{
		X[cur_vtx] = -vtx_number - 1;
		dfs(s, m, v, d + 1);
	}
	Y[cur_vtx] = -vtx_number - 1;
	dfs(m+1, e, v ^ (1 << d), d + 1);
}

void create_circuit(int M, std::vector<int> A) {
	if(A.size() == 1){
		vector<int> C(M + 1, 0), X, Y;
		C[0] = A[0];
		answer(C, X, Y);
		return;
	}
	vector<int> C(M + 1, -1);
	C[0] = A[0];
	int K = 0;
	while((1 << K) < A.size()) K++;
	total_leaf = (1 << K) - A.size();
	A.erase(A.begin());
	A.push_back(0);
	dfs(0, (1 << K) - 1, 0, 0);
	for(int i=0; i<vtx_number; i++){
		if(X[i] >= 0) mp[X[i]] = 1;
		if(Y[i] >= 0) mp[Y[i]] = 1;
	}
	int ptr = 0;
	for(int i=0; i<(1<<K); i++){
		if(mp[i]){
			mp[i] = A[ptr++];
		}
	}
	for(int i=0; i<vtx_number; i++){
		if(X[i] >= 0) X[i] = mp[X[i]];
		if(Y[i] >= 0) Y[i] = mp[Y[i]];
	}
	vector<int> vx(X, X + vtx_number);
	vector<int> vy(Y, Y + vtx_number);
	answer(C, vx, vy);
}

Compilation message

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:40:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |  while((1 << K) < A.size()) K++;
      |        ~~~~~~~~~^~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 36 ms 4288 KB Output is correct
3 Correct 43 ms 4172 KB Output is correct
4 Correct 2 ms 204 KB Output is correct
5 Correct 13 ms 1484 KB Output is correct
6 Correct 48 ms 5808 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 36 ms 4288 KB Output is correct
3 Correct 43 ms 4172 KB Output is correct
4 Correct 2 ms 204 KB Output is correct
5 Correct 13 ms 1484 KB Output is correct
6 Correct 48 ms 5808 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 59 ms 6656 KB Output is correct
9 Correct 78 ms 7608 KB Output is correct
10 Correct 85 ms 10296 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 1 ms 204 KB Output is correct
2 Correct 36 ms 4288 KB Output is correct
3 Correct 43 ms 4172 KB Output is correct
4 Correct 2 ms 204 KB Output is correct
5 Correct 13 ms 1484 KB Output is correct
6 Correct 48 ms 5808 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 59 ms 6656 KB Output is correct
9 Correct 78 ms 7608 KB Output is correct
10 Correct 85 ms 10296 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 85 ms 9912 KB Output is correct
15 Correct 65 ms 6852 KB Output is correct
16 Correct 89 ms 9648 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 84 ms 10032 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 2 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 64 ms 5960 KB Output is correct
3 Correct 46 ms 6444 KB Output is correct
4 Correct 71 ms 9152 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 64 ms 5960 KB Output is correct
3 Correct 46 ms 6444 KB Output is correct
4 Correct 71 ms 9152 KB Output is correct
5 Correct 81 ms 9644 KB Output is correct
6 Correct 80 ms 9412 KB Output is correct
7 Correct 77 ms 9392 KB Output is correct
8 Correct 75 ms 9272 KB Output is correct
9 Correct 47 ms 6476 KB Output is correct
10 Correct 73 ms 9256 KB Output is correct
11 Correct 74 ms 9144 KB Output is correct
12 Correct 49 ms 6456 KB Output is correct
13 Correct 49 ms 6092 KB Output is correct
14 Correct 52 ms 6600 KB Output is correct
15 Correct 74 ms 6724 KB Output is correct
16 Correct 2 ms 460 KB Output is correct
17 Correct 49 ms 5940 KB Output is correct
18 Correct 47 ms 5956 KB Output is correct
19 Correct 48 ms 6476 KB Output is correct
20 Correct 73 ms 9156 KB Output is correct
21 Correct 72 ms 9128 KB Output is correct
22 Correct 73 ms 9156 KB Output is correct