제출 #221487

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
221487		galca	자동 인형 (IOI18_doll)	C++14	9 / 100	123 ms	8464 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;

	int num_bits = 0;
	int tmp = N + 1;
	while (tmp > 0) {
		++num_bits;
		tmp >>= 1;
	}

	int idx = 1;
	for (int k = 1; k < num_bits; ++k) {
		int n_nodes = 1 << (k-1);
		for (int n = 1; n <= n_nodes; n++) {
			X.push_back(-(idx * 2));
			Y.push_back(-(idx * 2 + 1));
			idx++;
		}
	}

	// N nodes of the last level are connected to the triggers, the last one
	// 2^bits-N-1 to -1
	// and the last one to origin
	int n_leaves = 1 << (num_bits-1);

	int idx_b = X.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
	for (int n = 0; n < n_leaves; n++) {
		X.push_back(-1);
		Y.push_back(-1);
	}

	for (int n = 0; n < N; n++) {
		// revert the number
		int offset = n_leaves;
		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) {
			Y[idx_b + n_pos/2] = A[n];
			//cout << "connecting trigger " << n << " to Y at " << n_pos / 2 << endl;
		}
		else {
			X[idx_b + n_pos/2] = A[n];
			//cout << "connecting trigger " << n << " to X at " << n_pos / 2 << endl;
		}
	}

	Y[Y.size()-1] = 0;
#if 0
	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);
}

• Subtask 1: 0 / 2
• Subtask 2: 0 / 4
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 9 / 18
• Subtask 6: 0 / 56