oj.uz

Submission #78782

# Submission time Handle Problem Language Result Execution time Memory
78782 2018-10-08T17:56:03 Z tincamatei Mechanical Doll (IOI18_doll) C++14
100 / 100
 120 ms 11844 KB 
#include <bits/stdc++.h>
#include "doll.h"

using namespace std;

int lastid;

vector<int> X, Y;
vector<pair<int, pair<bool, int> > > poz;

int dfs(int depth, int N, int p, bool branch, int papa, int bit = 0) {
	if(depth >= 0) {
		int id = -((int)X.size()) - 1;
		X.push_back(0);
		Y.push_back(0);
		if((1 << depth) > N) {
			X[-id - 1] = -1;
			int r1 = dfs(depth - 1, N, p | (1 << bit), 1, id, bit + 1);
			Y[-id - 1] = r1;
		} else {
			int r1 = dfs(depth - 1, (1 << depth), p, 0, id, bit + 1);
			int r2 = dfs(depth - 1, N ^ (1 << depth), p | (1 << bit), 1, id, bit + 1);
			X[-id - 1] = r1;
			Y[-id - 1] = r2;
		}
		return id;
	} else {
		if((1 << bit) - 1 == p) {
			return 0;
		}
		else if(N == 0) {
			return -1;
		}
		else {
			poz.push_back(make_pair(p, make_pair(branch, papa)));
			return 2;
		}
	}
}

void create_circuit(int M, std::vector<int> A) {
	vector<int> C(M + 1, -1);
	
	int maxlg = 0;
	int N = A.size();
	while((1 << maxlg) <= N)
		++maxlg;
	lastid = -maxlg;

	dfs(maxlg - 1, N, 0, 0, 0);
	
	sort(poz.begin(), poz.end());
	
	for(int i = 0; i < poz.size(); ++i) {
		if(poz[i].second.first)
			Y[-poz[i].second.second - 1] = A[i];
		else
			X[-poz[i].second.second - 1] = A[i];
	}

	answer(C, X, Y);
}

Compilation message

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:54:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<bool, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |  for(int i = 0; i < poz.size(); ++i) {
      |                 ~~^~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 41 ms 4328 KB Output is correct
3 Correct 37 ms 4300 KB Output is correct
4 Correct 2 ms 204 KB Output is correct
5 Correct 12 ms 1356 KB Output is correct
6 Correct 61 ms 6464 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 41 ms 4328 KB Output is correct
3 Correct 37 ms 4300 KB Output is correct
4 Correct 2 ms 204 KB Output is correct
5 Correct 12 ms 1356 KB Output is correct
6 Correct 61 ms 6464 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 101 ms 7732 KB Output is correct
9 Correct 75 ms 8120 KB Output is correct
10 Correct 111 ms 11844 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 1 ms 204 KB Output is correct
2 Correct 41 ms 4328 KB Output is correct
3 Correct 37 ms 4300 KB Output is correct
4 Correct 2 ms 204 KB Output is correct
5 Correct 12 ms 1356 KB Output is correct
6 Correct 61 ms 6464 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 101 ms 7732 KB Output is correct
9 Correct 75 ms 8120 KB Output is correct
10 Correct 111 ms 11844 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 104 ms 11468 KB Output is correct
15 Correct 69 ms 7488 KB Output is correct
16 Correct 101 ms 11296 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 110 ms 11632 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 232 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 58 ms 6596 KB Output is correct
3 Correct 59 ms 6552 KB Output is correct
4 Correct 116 ms 9940 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 58 ms 6596 KB Output is correct
3 Correct 59 ms 6552 KB Output is correct
4 Correct 116 ms 9940 KB Output is correct
5 Correct 119 ms 11176 KB Output is correct
6 Correct 117 ms 10988 KB Output is correct
7 Correct 105 ms 11052 KB Output is correct
8 Correct 102 ms 10792 KB Output is correct
9 Correct 57 ms 6632 KB Output is correct
10 Correct 113 ms 10792 KB Output is correct
11 Correct 112 ms 10364 KB Output is correct
12 Correct 60 ms 6880 KB Output is correct
13 Correct 61 ms 7272 KB Output is correct
14 Correct 65 ms 7368 KB Output is correct
15 Correct 65 ms 7448 KB Output is correct
16 Correct 3 ms 460 KB Output is correct
17 Correct 84 ms 6908 KB Output is correct
18 Correct 59 ms 6816 KB Output is correct
19 Correct 67 ms 6796 KB Output is correct
20 Correct 100 ms 10588 KB Output is correct
21 Correct 97 ms 10316 KB Output is correct
22 Correct 120 ms 10296 KB Output is correct