50234. Maximum Cubic
難度：4.6/51
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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdint.h>
#define max(a,b) ((a)>(b)?(a):(b))
#define left(n) (2 * (n))
#define right(n) (2 * (n) + 1)
#define parent(n) ((n) / 2)
typedef struct{
int arr[1000005];
int pos[1000005];
int n;
} s_heap;
static inline void swap(int* a, int* b){
int t = *a;
*a = *b;
*b = t;
}
int get_largest(s_heap* h, int i){
int l = left(i), r = right(i);
int largest;
if(l <= h->n && h->arr[l] > h->arr[i]){
largest = l;
}
else{
largest = i;
}
if(r <= h->n && h->arr[r] > h->arr[largest]){
largest = r;
}
return largest;
}
void max_heapify(s_heap* h, int i){
int largest = get_largest(h, i);
while(largest != i){
swap(&(h->arr[i]), &(h->arr[largest]));
swap(&(h->pos[i]), &(h->pos[largest]));
i = largest;
largest = get_largest(h, i);
}
}
void build_max_heap(s_heap* h){
for(int i = (h->n / 2); i >= 1; i--){
max_heapify(h, i);
}
}
int extract_max(s_heap* h){
if(h->n < 1) return -1;
else{
int max_num = h->arr[1];
h->arr[1] = h->arr[h->n];
int max_pos = h->pos[1];
h->pos[1] = h->pos[h->n];
h->n -= 1;
max_heapify(h, 1);
return max_pos;
}
}
int insert(s_heap* h, int key, int pos_key){
h->n += 1;
int i = h->n;
h->arr[i] = key;
h->pos[i] = pos_key;
while(i > 1 && h->arr[parent(i)] < h->arr[i]){
swap(&(h->arr[i]), &(h->arr[parent(i)]));
swap(&(h->pos[i]), &(h->pos[parent(i)]));
i = parent(i);
}
}
int main(){
int n, arr[105][105][105];
scanf("%d", &n);
for(int i = 0; i < n; i++){
for(int j = 0; j <= i; j++){
for(int k = 0; k <= i; k++){
scanf("%d", &arr[i][j][k]);
}
}
}
s_heap* h = (s_heap*) malloc(sizeof(s_heap));
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
insert(h, arr[max(i, j)][i][j], max(i, j) * (n * n) + i * n + j);
}
}
while(h->n != 0){
int now_pos = extract_max(h);
int now_x = now_pos / (n * n);
int now_y = (now_pos % (n * n)) / (n);
int now_z = now_pos % n;
printf("%d ", arr[now_x][now_y][now_z]);
if(now_x + 1 < n){
insert(h, arr[now_x + 1][now_y][now_z], (now_x + 1) * (n * n) + now_y * n + now_z);
}
}
}