제출 #713767

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
713767		Foxyy	Mechanical Doll (IOI18_doll)	C++17	53 / 100	258 ms	26816 KiB

doll

#include <bits/stdc++.h>
using namespace std;

#include "doll.h"

const int INF = 0x3f3f3f3f;

struct Switch {
	int x, y;
};
vector<Switch> switches{{-INF, -INF}};
Switch& get_switch(int id) {
	return switches[-id];
}

int new_switch(int x, int y) {
	static int cnt = 0;
	cnt++;
	switches.push_back({x, y});
	return -cnt;
}

int create_switch_tree(int sz) {
//	cerr << "creating a switch tree of size: " << sz << '\n';
	if (sz == 0) {
		return INF;
	}
	if (sz == 1) {
		return new_switch(INF, INF);
	}
	sz--;
	int x = create_switch_tree((sz+1)/2);
	int y = create_switch_tree(sz/2);
	int id = new_switch(x, y);
//	cerr << get_switch(id).x << ' ' << get_switch(id).y << '\n';
//	cerr << id << ' ' << x << ' ' << y << '\n';
	return id;
}

//void print(int switch_id) {
//	cerr << "switch #" << switch_id << ": ";
//	auto [x, y] = get_switch(switch_id);
//	cerr << "x = " << x << ", ";
//	cerr << "y = " << y << '\n';
//	if (x < 0) {
//		print(x);
//	}
//	if (y < 0) {
//		print(y);
//	}
//}

void assign_value(int switch_tree_root, vector<int>& vec) {
//	cerr << "assigning " << (int)vec.size() << " values to a switch tree with root = " << switch_tree_root << '\n';
	
	map<int, pair<int, int>> mp;
	
	function<void(int, int, int)> dfs = [&](int switch_id, int val, int depth) {
		auto& current_switch = get_switch(switch_id);
		
		if (current_switch.x == INF) {
			mp[val] = {switch_id, 0};
		} else {
			dfs(current_switch.x, val, depth+1);
		}
		
		if (current_switch.y == INF) {
			mp[val + (1 << depth)] = {switch_id, 1};
		} else {
			dfs(current_switch.y, val + (1 << depth), depth+1);
		}
	};
	
	dfs(switch_tree_root, 0, 0);
	
	vector<pair<int, int>> leaves;
	for (auto [val, p] : mp) {
		leaves.push_back(p);
	}
	for (int i = 0; i < (int)vec.size()-1; i++) {
		auto [id, lr] = leaves[i];
		if (lr == 0) {
			get_switch(id).x = vec[i];
		} else {
			get_switch(id).y = vec[i];
		}
	}
	for (int i = (int)vec.size()-1; i < (int)leaves.size()-1; i++) {
		auto [id, lr] = leaves[i];
		if (lr == 0) {
			get_switch(id).x = switch_tree_root;
		} else {
			get_switch(id).y = switch_tree_root;
		}
	}
	auto [id, lr] = leaves.back();
	if (lr == 0) {
		get_switch(id).x = vec.back();
	} else {
		get_switch(id).y = vec.back();
	}
}

void create_circuit(int M, std::vector<int> A) {
	const int N = (int)A.size();
	vector<vector<int>> vec(M+1);
	for (int i = 0; i < N-1; i++) {
		vec[A[i]].push_back(A[i+1]);
	}
	vec[A.back()].push_back(0);
	
	vector<int> C(M+1, 0);
	C[0] = A[0];
	for (int i = 1; i <= M; i++) if (not vec[i].empty()) {
		if (vec[i].size() == 1) {
			C[i] = vec[i][0];
		} else {
			int sz = (int)vec[i].size()-1;
			sz = (1 << (__lg(sz)+1)) - 1;
			C[i] = create_switch_tree(sz);
//			print(C[i]);
			assign_value(C[i], vec[i]);
//			print(C[i]);
		}
	}
	
	vector<int> X((int)switches.size()-1);
	vector<int> Y((int)switches.size()-1);
	
	for (int i = 1; i < (int)switches.size(); i++) {
		X[i-1] = get_switch(-i).x;
		Y[i-1] = get_switch(-i).y;
	}
	
	answer(C, X, Y);
}

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