oj.uz

Submission #221851

# Submission time Handle Problem Language Result Execution time Memory
221851 2020-04-11T09:54:04 Z galca Mechanical Doll (IOI18_doll) C++14
100 / 100
 127 ms 8660 KB 
#include "doll.h"
#include <vector>
#include <iostream>

using namespace std;

// N + 1 = 15
// num_bits = 4
// we should have: 1 + 2 + 4 + 8

void create_circuit(int M, std::vector<int> A) {
	int N = A.size();
	std::vector<int> C(M + 1);
	
	for (int i = 0; i <= M; ++i) {
		C[i] = -1;
	}

	std::vector<int> X, Y;

	// compute depth and number of elements in each tree + remaining counter
	int num_bits = 0;
	int tmp = N;
	while (tmp > 0) {
		++num_bits;
		tmp >>= 1;
	}

	vector<int> trees;

	int current_tree = 1 << (num_bits - 1); // for N = 16, this is 16

	int to_cover = N;
	while (to_cover > 0) {
		if (current_tree & N) {
			trees.push_back(current_tree);
			to_cover -= current_tree;
		}
		else {
			trees.push_back(0);
		}
		
		current_tree >>= 1;
	}
	int tail_counter = trees[trees.size() - 1];
	//cout << " the tail will be " << tail_counter << endl;
	// create the trees
	// all triggers belong to the trees
	// the counter eventually lead to exit

	int idx = 1;

	int el_idx = 0;
	vector<int> order;
	int n_trees = trees.size();
 
	int counter_pos = 1 << n_trees;

	// if i fix the bug here i have a chance to get it working...
	for (int i = 0; i < (1 << num_bits); i++) {
		int mask = 0;
		int mask1 = 1;
		for (int j = 0; j < num_bits; j++) {
			// the layer exists
			int masked_i = i & mask1;
			if ((i & mask) == masked_i) {
				if ((j < trees.size()) && (trees[j] != 0)) {
					//cout << "element " << i << " belong to tree " << j << endl;
					order.push_back(el_idx++);
				}
				else {
					//cout << "element " << i << " is skipped at level " << j << endl;
					order.push_back(-1);
				}
				break;
			}
			mask = (mask << 1) | 1;
			mask1 = (mask1 << 1) | 1;
		}
	}
#if 0
	cout << "the element order is: ";
	for (int i = 0; i < order.size(); i++) {
		cout << order[i] << " ";
	}
	cout << endl;
#endif
	// factor: 2, 4, 8, ...
	// offset: 0, 1, 3, 
	// tree i : elements 0 modulo 1<<(i+1) + i*2+1
	for (int i = 0; i < trees.size(); i++) {
		int current_size = trees[i];

		//cout << "current tree of size " << current_size << endl;

		if (current_size == 0) {
			X.push_back(-1);
			Y.push_back(-(idx + 1));
			++idx;
			continue;
		}

		int tree_factor = 1 << (i + 1);
		int tree_offset = (tree_factor >> 1) - 1;

		// add the root
		X.push_back(-(idx+1));
		Y.push_back(-(idx + current_size));
		
		// the tree itself
		int my_idx = 1;
		int start_idx = idx;
		for (int k = 1; (1 << (k - 1)) < current_size; ++k) {
			int n_nodes = 1 << (k - 1);
			//cout << "creating " << n_nodes << " for the tree of " << current_size << endl;
			for (int n = 1; n <= n_nodes; n++) {
				X.push_back(-(start_idx + my_idx * 2));
				Y.push_back(-(start_idx + my_idx * 2 + 1));
				my_idx++;
			}
		}
		//cout << "overall in the tree of " << current_size << " created " << my_idx << " nodes " << endl;
		// replace last level with triggers
		int n_nodes = current_size >> 1;
		int idx_b = n_nodes != 0 ? (X.size() - n_nodes) : (X.size() - 1);

		for (int n = 0; n < current_size; n++) {
			// revert the number
			int offset = n_nodes;
			int n_tmp = n;
			int n_pos = 0;
			while (n_tmp > 0) {
				if (n_tmp & 1) {
					n_pos += offset;
				}
				n_tmp >>= 1;
				offset >>= 1;
			}

			if (n_pos & 1) {
				int key = order[n*tree_factor + tree_offset];
				if (key < N) {
					Y[idx_b + n_pos / 2] = A[key];
				}
				else {
					Y[idx_b + n_pos / 2] = -1;
				}
				//cout << "connecting trigger at pos " << key << " val " << A[key] << " to Y at " << n_pos / 2 << endl;
				//cout << "idx in Y " << idx_b + n_pos / 2 << endl;
			}
			else {
				int key = order[n*tree_factor + tree_offset];
				if (key < N) {
					X[idx_b + n_pos / 2] = A[key];
				}
				else {
					X[idx_b + n_pos / 2] = -1;
				}
				//cout << "connecting trigger at pos " << key << " val " << A[key] << " to X at " << n_pos / 2 << endl;
				//cout << "idx in X " << idx_b + n_pos / 2 << endl;
			}
		}

		idx += current_size;
	}

#if 0
	cout << "arrays so far " << endl;
	for (int i = 0; i < X.size(); i++) {
		cout << X[i] << " ";
	}
	cout << endl;

	for (int i = 0; i < Y.size(); i++) {
		cout << Y[i] << " ";
	}
	cout << endl;
#endif

	// add the counter
	tail_counter >>= 1;
	while (tail_counter > 0) {
		X.push_back(-1);
		Y.push_back(-(idx+1));
		++idx;
		tail_counter >>= 1;
	}
	Y[Y.size() - 1] = 0;

#if 0
	cout << "arrays with the tail counter " << endl;
	for (int i = 0; i < X.size(); i++) {
		cout << X[i] << " ";
	}
	cout << endl;

	for (int i = 0; i < Y.size(); i++) {
		cout << Y[i] << " ";
	}
	cout << endl;
#endif

	answer(C, X, Y);
}

Compilation message

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:67:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |     if ((j < trees.size()) && (trees[j] != 0)) {
      |          ~~^~~~~~~~~~~~~~
doll.cpp:91:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |  for (int i = 0; i < trees.size(); i++) {
      |                  ~~^~~~~~~~~~~~~~
doll.cpp:57:6: warning: unused variable 'counter_pos' [-Wunused-variable]
   57 |  int counter_pos = 1 << n_trees;
      |      ^~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 40 ms 4292 KB Output is correct
3 Correct 32 ms 3884 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 1356 KB Output is correct
6 Correct 54 ms 5172 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 40 ms 4292 KB Output is correct
3 Correct 32 ms 3884 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 1356 KB Output is correct
6 Correct 54 ms 5172 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 63 ms 6224 KB Output is correct
9 Correct 61 ms 6500 KB Output is correct
10 Correct 127 ms 8660 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 2 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 40 ms 4292 KB Output is correct
3 Correct 32 ms 3884 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 1356 KB Output is correct
6 Correct 54 ms 5172 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 63 ms 6224 KB Output is correct
9 Correct 61 ms 6500 KB Output is correct
10 Correct 127 ms 8660 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 2 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 109 ms 8292 KB Output is correct
15 Correct 54 ms 5736 KB Output is correct
16 Correct 82 ms 8088 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 2 ms 204 KB Output is correct
20 Correct 92 ms 8420 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 248 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 264 KB Output is correct
5 Correct 2 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 2 ms 204 KB Output is correct
2 Correct 69 ms 5356 KB Output is correct
3 Correct 51 ms 5356 KB Output is correct
4 Correct 79 ms 7636 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 204 KB Output is correct
2 Correct 69 ms 5356 KB Output is correct
3 Correct 51 ms 5356 KB Output is correct
4 Correct 79 ms 7636 KB Output is correct
5 Correct 78 ms 8024 KB Output is correct
6 Correct 80 ms 7780 KB Output is correct
7 Correct 79 ms 7908 KB Output is correct
8 Correct 91 ms 7768 KB Output is correct
9 Correct 51 ms 5416 KB Output is correct
10 Correct 81 ms 7696 KB Output is correct
11 Correct 75 ms 7636 KB Output is correct
12 Correct 50 ms 5460 KB Output is correct
13 Correct 56 ms 5584 KB Output is correct
14 Correct 55 ms 5580 KB Output is correct
15 Correct 57 ms 5740 KB Output is correct
16 Correct 3 ms 460 KB Output is correct
17 Correct 51 ms 5152 KB Output is correct
18 Correct 49 ms 5324 KB Output is correct
19 Correct 48 ms 5328 KB Output is correct
20 Correct 102 ms 7636 KB Output is correct
21 Correct 74 ms 7640 KB Output is correct
22 Correct 76 ms 7644 KB Output is correct