Submission #414177

#	Time	Username	Problem	Language	Result	Execution time	Memory
414177		Temmie	Mechanical Doll (IOI18_doll)	C++17	47 / 100	315 ms	16180 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>

//void answer(std::vector <int> c, std::vector <int> x, std::vector <int> y) {
	//std::cerr << "answered" << std::endl;
	//for (int i : c) std::cerr << i << " ";
	//std::cout << std::endl;
	//for (int i : x) std::cerr << i << " ";
	//std::cout << std::endl;
	//for (int i : y) std::cerr << i << " ";
	//std::cout << std::endl;
//}

struct Switch {
	int id;
	int left, right;
	int depth = 1;
	bool dir = false; // false = left , true = right
};

std::vector <Switch> sw;

void make_tree(int node, int depth, int max_depth) {
	if (depth == max_depth) return;
	assert(depth < max_depth);
	sw[node].left = (int)sw.size() + 1;
	sw[node].right = (int)sw.size() + 2;
	sw.push_back({ (int)sw.size() + 1, -1, -1, depth + 1 });
	sw.push_back({ (int)sw.size() + 1, -1, -1, depth + 1 });
	make_tree(sw[node].left - 1, depth + 1, max_depth);
	make_tree(sw[node].right - 1, depth + 1, max_depth);
}

void find_exits(int node, int depth, int max_depth, int exit_number) {
	if (depth == max_depth) {
		if (sw[node].dir == false) {
			sw[node].left = exit_number;
		} else {
			sw[node].right = exit_number;
		}
		sw[node].dir ^= 1;
		return;
	}
	assert(depth < max_depth);
	if (sw[node].dir == false) {
		find_exits(sw[node].left - 1, depth + 1, max_depth, exit_number);
	} else {
		find_exits(sw[node].right - 1, depth + 1, max_depth, exit_number);
	}
	sw[node].dir ^= 1;
}

void create_circuit(int m, std::vector <int> a) {
	int n = a.size();
	int size = 1;
	int depth = 0;
	while (size < n) {
		size <<= 1;
		depth++;
	}
	//std::cerr << n << ": " << size << ", " << depth <<std::endl;
	sw.push_back({ 1, -1, -1 });
	make_tree(0, 1, depth);
	int cnt = 0;
	for (int i = 0; i < n - 1; i++) {
		find_exits(0, 1, depth, a[i + 1]);
		cnt++;
	}
	for (; cnt < size - 1; cnt++) {
		find_exits(0, 1, depth, -1);
	}
	find_exits(0, 1, depth, 0);
	std::vector <int> c(m + 1), x(sw.size()), y(sw.size());
	c[0] = a[0];
	for (int i = 1; i <= m; i++) {
		c[i] = -1;
	}
	for (auto node : sw) {
		if (node.depth != depth) {
			x[node.id - 1] = -node.left;
			y[node.id - 1] = -node.right;
		} else {
			x[node.id - 1] = node.left;
			y[node.id - 1] = node.right;
		}
	}
	//for (auto s : sw) {
		//std::cerr << s.id << " " << s.left << ", " << s.right << " and "
		//<< s.depth << " dir: " << s.dir << std::endl;
	//}
	answer(c, x, y);
}

//int main() {
	
	//for (int i = 1; i <= 10; i++) {
		//std::vector <int> a(i, 0);
		//create_circuit(1, a);
	//}
	
	//std::vector <int> a = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 };
	//int m = 11;
	//create_circuit(m, a);
	
	//std::vector <int> a = { 1, 2, 1, 3 };
	//int m = 4;
	//create_circuit(m, a);
	
//}

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