IOI 2018 Mechanical Doll

서브태스크 1: 스위치 없이 그냥 이어주면 2점을 쉽게 받을 수 있다.

서브태스크 2~4만 푸는 풀이는 잘 모르겠고, 63점 풀이로 넘어간다.

63점 풀이: 첫 번째는 A0, 두 번째는 A1...으로 보내기 위해, 이진 트리를 만들 수 있다. 2^K 꼴의 이진 트리를 만든 뒤, 처음 i번째로 방문하는 원소에다가는(i<=N) A[방문 번호-1]을 스위치 이진 트리의 리프에 넣어주고, 나머지 원소와 트리거는 루트로 다시 보내주면 된다.

100점 풀이: 루트로 가는 노드를 한 쪽으로 몰아둔 뒤에 뭉치면 노드를 절약할 수 있다. 이를 위해서 루트로 가는 스위치 이진 트리의 리프를 한쪽으로 몰아주고, 나머지를 잘 배치해 준 뒤 모든 자손이 루트로 가는 노드는 자신이 루트로 가도록 만들면 된다.

#include "doll.h"
#include <algorithm>
using namespace std;
std::vector<int> C;
std::vector<int> X,Y;
vector<int>AA;
int N,trN;
int nod;
void ud(int b,int nc)
{
	if (b == 0)
		C[0] = nc;
	else if (b < 0)
	{
		X[-b - 1] = nc;
	}
	else
	{
		Y[b - 1] = nc;
	}
}
vector<pair<int, int>>li;
void dfs(int s, int e, int bef,int d,int er)
{
	if (e < trN - N)
	{
		ud(bef, -1);
		return;
	}
	if (s == e)
	{
		li.push_back({d,bef });
		return;
	}
	nod--;
	int cn = nod;
	ud(bef, nod);
	X.push_back(0);
	Y.push_back(0);
	dfs(s, (s + e) / 2, cn,d,er+1);
	dfs((s + e) / 2 + 1, e,-cn,d+(1<<er),er+1);
}
void create_circuit(int M, std::vector<int> A) 
{
	A.push_back(0);
	N = A.size();
	if (N == 2)
	{
		vector<int>C(M + 1, 0), X, Y;
		C[0] = A[0];
		answer(C, X, Y);
		return;
	}
	AA = A;
	for (int i = 0; i <= M; ++i) 
	{
		C.push_back(-1);
	}
	for (trN = 1; trN < N; trN *= 2);
	dfs(0, trN - 1, 0,0,0);
	sort(li.begin(), li.end());
	int i;
	for (i = 0; i < li.size(); i++)
	{
		ud(li[i].second, AA[i]);
	}
	answer(C, X, Y);
}