백준15942 Thinking Heap

작성일 | In

문제 링크

  • http://icpc.me/15942

문제 출처

  • 2018 UCPC E번

풀이

minheap이므로 p의 조상에는 k보다 작은 값, p의 후손에는 k보다 큰 값을 넣어야 합니다.
루트에서 p의 부모까지는 1부터 순서대로, p에는 k를 배치하고, p의 후손들은 dfs을 돌면서 N, N-1, …을 배치하면 됩니다.
나머지는 적당히 오름차순으로 채워주면 됩니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <bits/stdc++.h>
using namespace std;

int n, k, p;
int ans[202020];
int upCnt;
int downCnt;

vector<int> up;

void getUp(){
	int t = p;
	while(t >>= 1){
		up.push_back(t);
	}
	reverse(up.begin(), up.end());
	if(up.size() >= k){
		cout << -1; exit(0);
	}
	for(auto i : up) ans[i] = ++upCnt;
}

void dfs(int v){
	ans[v] = downCnt--;
	if(v*2 <= n) dfs(v*2);
	if(v*2+1 <= n) dfs(v*2+1);
}

void getDown(){
	downCnt = n;
	if(2*p <= n) dfs(2*p);
	if(2*p+1 <= n) dfs(2*p+1);
	if(downCnt < k){
		cout << -1; exit(0);
	}
}

int heapN = 0;
int heap[202020];

void upHeap(int x){
	while(x > 1){
		if(heap[x/2] <= heap[x]) break;
		swap(heap[x], heap[x/2]);
		x >>= 1;
	}
}

void insert(int v){
	heap[++heapN] = v;
	upHeap(heapN);
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> k >> p;
	ans[p] = k;
	getUp();
	getDown();

	queue<int> q;
	for(int i=upCnt+1; i<=downCnt; i++){
		if(i == k) continue;
		q.push(i);
	}
	for(int i=1; i<=n; i++){
		if(ans[i]) continue;
		ans[i] = q.front(); q.pop();
	}
	for(int i=1; i<=n; i++) cout << ans[i] << "\n";
}