BOJ 34992 트리 선물하기

문제 링크입니다.

문제 요약

$0$ 부터 $2N$까지의 짝수를 순서대로 나열합니다. $1$부터 $2N-1$까지의 홀수를 이용해 수열을 합쳐 이진 트리를 구성합니다.

해당 트리를 이진 탐색 트리처럼 사용했을 때, 집합 $S$에 있는 짝수만을 찾고 $S$에 있지 않은 짝수는 찾지 못하도록 트리를 구성하세요.

풀이

수열의 양 끝, 그러니까 $0$과 $2N$은 트리의 구성 상태와 관계 없이 반드시 찾아집니다. $2N$ 쪽은 $S$의 최대 원소로 잡으면 되니까 상관없고, $0$이 $S$에 없는 경우만 예외 처리합시다.

기본적으로 $0$과 $2$를 $1$로, $1$과 $4$를 $3$으로, … , $2N-3$과 $2N$을 $2N-1$로 이은 이진 트리를 고려합니다. 이 트리는 모든 짝수를 찾을 수 있습니다.

이 트리에서 홀수들의 순서를 적당히 바꿔 $2$ 이상 $2N$ 이하의 원하는 짝수들을 찾지 못하도록 만들어 봅시다. 어떤 짝수를 찾지 못하려면, 자신의 부모가 자신보다 크거나, 자신의 부모가 아닌 어떤 조상이 자신보다 작아야 합니다. 자신의 부모가 자신보다 크면 된다는 점에 초점을 두어, 찾지 못해야 하는 원소 $x$의 부모로 $x+1$을 두는 식으로 구성해 볼 수 있습니다.

이는 필요에 따라 홀수들을 왼쪽부터 순서대로 스왑하는 것으로 쉽게 구현할 수 있습니다. 구간 $[l,\, r]$을 찾지 못해야 하고 $r+2$는 찾을 수 있어야 하면 $l$부터 $r+2$까지 순서대로 $l+1, l+3, \cdots, r+1, l-1$을 부모로 가지면 됩니다.

코드

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

int s[808080];
int par[808080], L[808080], R[808080];

int main(){
	cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);
	int k; cin >> k;
	for(int i = 1; i <= k; i++) cin >> s[i];
	if(s[1] != 0) return !(cout << -1);
	cout << s[k]/2 << '\n';
	for(int i = 1; i <= s[k]; i += 2) par[i/2+1] = i;
	int idx = 2;
	for(int i = 1; i < s[k]/2; i++){
		if(s[idx] != i*2) swap(par[i], par[i+1]); else idx++;
	}
	L[par[1]] = 0; for(int i = 2; i <= s[k]/2; i++) L[par[i]] = par[i-1];
	for(int i = 1; i <= s[k]/2; i++) R[par[i]] = i*2;
	for(int i = 1; i <= s[k]; i += 2) cout << L[i] << ' ' << R[i] << '\n';
}