Submission #414387

#	Time	Username	Problem	Language	Result	Execution time	Memory
414387		Temmie	Mechanical Doll (IOI18_doll)	C++17	0 / 100	2 ms	332 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;
//}

int inf = 1 << 30;

std::vector <std::pair <int, int>> sw;
std::vector <int> c, x, y;
std::vector <int> dir;

void place(int node, int to_place) {
	//std::cerr << "<" << node << ", " << to_place << ">" << std::endl;
	int tir = dir[node];
	dir[node] ^= 1;
	if (tir == 0) {
		//left
		if (sw[node].first == inf) {
			sw[node].first = to_place;
			return;
		}
		//std::cerr << sw[node].first << std::endl;
		assert(sw[node].first <= 0);
		place(-sw[node].first, to_place);
		return;
	} else {
		//right
		if (sw[node].second == inf) {
			sw[node].second = to_place;
			return;
		}
		assert(sw[node].second <= 0);
		place(-sw[node].second, to_place);
		return;
	}
	assert(false);
}

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::vector <int> layer;
	for (int i = 0; i < ((n + 1) >> 1); i++) {
		sw.emplace_back(inf, inf * (i == ((n + 1) >> 1) - 1 ? -1 : 1));
		layer.push_back(i);
	}
	for (int i = 0; i < depth - 1; i++) {
		//std::cerr << "layer: ";
		//for (int j : layer) std::cerr << j << " ";
		//std::cerr << std::endl;
		std::vector <int> new_layer;
		for (int j = 0; j < (int)layer.size(); j += 2) {
			new_layer.push_back(sw.size());
			sw.emplace_back(-layer[j],
			j + 1 < (int)layer.size() ? -layer[j + 1] : -inf);
		}
		std::swap(layer, new_layer);
	}
	assert((int)layer.size() == 1);
	for (auto& p : sw) std::swap(p.first, p.second);
	int first = layer[0];
	//std::cerr << "first: " << first << std::endl;
	for (auto& p : sw) {
		if (p.first == -inf) {
			p.first = -first;
		}
		if (p.second == -inf) {
			p.second = -first;
		}
	}
	//for (auto p : sw) std::cerr << "(" << p.first << ", " << p.second << ")" << std::endl;
	c.resize(m + 1, -first);
	c[0] = a[0]; // this is 1 idx
	a.push_back(0);
	dir.resize(sw.size(), 0);
	for (int i = 1; i < (int)a.size(); i++) {
		//std::cerr << "palce idx = " << i << " (" << a[i] << ")" << std::endl;
		place(first, a[i] /* this is 1 idx */);
	}
	for (int& i : c) if (i <= 0) i--; // make 1 idx
	for (auto p : sw) {
		//std::cerr << "p: (" << p.first << ", " << p.second << ")" << std::endl;
		x.push_back(p.first -(p.first < 0));
		y.push_back(p.second -(p.second < 0));
	}
	answer(c, x, y);
}

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

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