50231. Cubic Pairing Task with Hash Table
難度：5/5
回來複習這題的時候要回去看大神的解法。優雅又超快...。我很正式的課完一個hash-table跟Circler queue花超多時間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
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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdint.h>
#define max(a,b) ((a)>(b)?(a):(b))
// #define min(a,b) ((a)<(b)?(a):(b))
typedef struct{
int table[12000][12];
int pos[12000][12];
int table_size;
int capacity;
} hash_table;
int f(int k, int s){
return (77 * k + 2222) % s;
}
void init_ht(hash_table *h, int s, int c){
memset(h->table, -1, sizeof(h->table));
memset(h->pos, -1, sizeof(h->pos));
h->table_size = s;
h->capacity = c;
}
int query_ht(hash_table *h, int k, int pos_idx){
int key = f(k, h->table_size);
int first_slot = -1, exact_idx = -1;
for(int i = 0; i < h->capacity; i++){
if(first_slot == -1 && h->table[key][i] == -1){
first_slot = i;
}
if(h->table[key][i] == k){
exact_idx = i;
break;
}
}
if(exact_idx == -1){
h->table[key][first_slot] = k;
h->pos[key][first_slot] = pos_idx;
return -1;
}
else{
int rtv = h->pos[key][exact_idx];
h->table[key][exact_idx] = -1;
h->pos[key][exact_idx] = -1;
return rtv;
}
}
typedef struct{
int arr[12000];
int front;
int rear;
int size;
} queue;
void init_queue(queue* q){
q->front = 0;
q->rear = 0;
q->size = 0;
}
void push(queue* q, int k){
q->arr[(q->rear)++] = k;
if(q->rear == 12000) q->rear = 0;
q->size++;
}
int pop(queue* q){
int rtv = q->arr[(q->front)++];
if(q->front == 12000) q->front = 0;
q->size--;
return rtv;
}
int get_size(queue* q){
return q->size;
}
int main(){
int n, s, c;
hash_table* h = (hash_table*) malloc(sizeof(hash_table));
scanf("%d %d %d", &n, &s, &c);
init_ht(h, s, c);
int arr[120][120][120];
int now_idx[120][120];
for(int i = 0; i < n; i++){
for(int j = 0; j <= i; j++){
for(int k = 0; k <= i; k++){
scanf("%d", &arr[j][k][i]);
// printf("%d in (%d %d %d)\n", arr[j][k][i], j, k, i);
}
}
}
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
now_idx[i][j] = max(i, j);
}
}
queue* q = (queue*) malloc(sizeof(queue));
init_queue(q);
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
push(q, i * n + j);
}
}
// printf("size = %d\n", get_size(q));
while(get_size(q) != 0){
int now = pop(q); int now_x = now / n, now_y = now % n;
int rtv = query_ht(h, arr[now_x][now_y][now_idx[now_x][now_y]], now);
if(rtv != -1){
printf("%d ", arr[now_x][now_y][now_idx[now_x][now_y]]);
now_idx[now_x][now_y]++;
now_idx[rtv / n][rtv % n]++;
if(now_idx[now_x][now_y] < n) push(q, now);
if(now_idx[rtv / n][rtv % n] < n) push(q, rtv);
}
}
free(h);
}