-
Notifications
You must be signed in to change notification settings - Fork 0
/
Hash.cpp
102 lines (97 loc) · 1.8 KB
/
Hash.cpp
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
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include<stddef.h>
#include<ctype.h>
#define LOOP for(int i=0;i<n;i++)
#define TEST while(t--)
#define T int t
#define TD scanf("%d",&t)
#define N int n
#define ND scanf("%d",&n)
#define LLU long long unsigned
LLU hash_fn(char *s);
typedef struct node {
char *str;
int flag;
}node;
int main(void) {
T;
TD;
TEST {
node* hash[101];
for(int i=0;i<101;i++) {
hash[i]=(node*)malloc(sizeof(node));
hash[i]->str=(char*)malloc(sizeof(char)*16);
hash[i]->flag=0;
}
int operations;
scanf("%d",&operations);
int total=0;
while(operations--) {
char *s;
s=(char*)(malloc(sizeof(char)*20));
scanf("%s",s);
char string[16];
int i=4,count=0;
while(s[i]!='\0') {
string[count++]=s[i++];
}
string[count]='\0';
if(s[0]=='A') {
long long unsigned key=hash_fn(s);
int i=1;
while(i<=20) {
LLU pos=(key+(i*i)+(23*i))%101;
if(!hash[pos]->flag){
hash[pos]->flag=1;
strcpy(hash[pos]->str,string);
total++;
break;
}
else if(strcmp(string,hash[i]->str)==0)
break;
i++;
}
}
else if(s[0]=='D') {
/* char string[16];
int i=4,count=0;
while(s[i]!='\0') {
string[count++]=s[i++];
}*/
//string[count]='\0';
for(int i=0;i<=100;i++) {
if(hash[i]->flag && strcmp(string,hash[i]->str)==0) {
total--;
hash[i]->flag=0;
}
}
}
}
printf("%d\n",total);
for(int i=0;i<101;i++) {
if(hash[i]->flag) {
printf("%d:%s\n",i,hash[i]->str);
}
}
}
}
LLU hash_fn(char *s) {
char string[16];
int i=4,count=0;
while(s[i]!='\0') {
string[count++]=s[i++];
}
string[count]='\0';
i=0;
LLU key=0;
while(i<count) {
char ch=string[i];
key=key+(LLU)ch*(i+1);
i++;
}
key=(key*19)%101;
return key;
}