Submission #221851

#	Time	Username	Problem	Language	Result	Execution time	Memory
221851		galca	Mechanical Doll (IOI18_doll)	C++14	100 / 100	127 ms	8660 KiB

doll

#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 (stderr)

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 / 2
• Subtask 2: 4 / 4
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 18 / 18
• Subtask 6: 56 / 56