IOI 2018 Mechanical Doll

IOI 2018 Mechanical Doll

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

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

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

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

#include "doll.h" #include using namespace std; std::vector C; std::vector X,Y; vectorAA; 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>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< A) { A.push_back(0); N = A.size(); if (N == 2) { vectorC(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); }

from http://jjang36524.tistory.com/13 by ccl(A) rewrite - 2021-08-18 21:26:20