s.c (1292B)
1 #include <stdio.h> 2 #include <stdlib.h> 3 #include <string.h> 4 #include <stdint.h> 5 6 /* TODO change this to a rbtree */ 7 8 struct node { 9 struct node *l; 10 struct node *p; 11 int key; 12 }; 13 14 struct node *add_node(struct node **headp, int key) 15 { 16 struct node *tmp; 17 struct node *head = *headp; 18 19 if (!head) { 20 head = malloc(sizeof(struct node)); 21 head->l = NULL; 22 head->p = NULL; 23 head->key = key; 24 return head; 25 } 26 27 tmp = malloc(sizeof(struct node)); 28 tmp->l = NULL; 29 tmp->p = NULL; 30 tmp->key = key; 31 32 while (1) { 33 if (key > head->key) { 34 if (head->p) 35 head = head->p; 36 else 37 break; 38 } else { 39 if (head->l) 40 head = head->l; 41 else 42 break; 43 } 44 } 45 46 if (key > head->key) 47 head->p = tmp; 48 else 49 head->l = tmp; 50 51 return tmp; 52 } 53 54 int search_btree(struct node *head, int key) 55 { 56 while (head) { 57 if (key == head->key) 58 return 1; 59 if (key > head->key) 60 head = head->p; 61 else 62 head = head->l; 63 } 64 return 0; 65 } 66 67 int solve() 68 { 69 struct node *head = NULL; 70 uint32_t res; 71 int n, i; 72 73 scanf("%d", &n); 74 75 res = 0; 76 for (i = 0; i < n; i++) { 77 int x; 78 79 scanf("%d", &x); 80 if (!search_btree(head, x)) { 81 res++; 82 if (!head) 83 head = add_node(&head, x); 84 else 85 add_node(&head, x); 86 } 87 } 88 89 printf("%u\n", res); 90 91 return 0; 92 } 93 94 int main() 95 { 96 int t = 1; 97 while (t--) 98 solve(); 99 }