해적의 mini DB

#define LEN 32 #define KEY 0 #define VALUE 1 #define MAX_KEY LEN #define MAX_DATA LEN #define MAX_TABLE 150000 typedef struct { char key[MAX_KEY + 1]; char data[MAX_DATA + 1]; int keyTbIndex; // kh 삭제할 때 사용함 }Hash; Hash tb[MAX_TABLE]; int keyTb[MAX_TABLE]; int str_cmp(char * str0, char * str1, int len) { register int i; // printf("str_cmp %s %s %d\n",str0,str1,len); for (i = 0; i<len && str0[i] != 0 && str1[i] != 0; i++) { // printf("[10]"); if (str0[i] != str1[i]) return -1; } // printf("i %d %x %x\n",i,str0[i],str1[i]); if (str0[i] != str1[i]) return -1; return 1; } int str_len(char * str) { register int len; for (len = 0; str[len] != 0; len++); return len; } void str_cpy(char * dst, char * src, int len) { register int i; // printf("str_cpy %s %d\n",src,len); //return; for (i = 0; i<len && src[i] != 0; i++) { dst[i] = src[i]; // printf("."); } dst[i] = 0; } unsigned long hash(const char *str) { unsigned long hash = 5381; int c; while (c = *str++) { hash = (((hash << 5) + hash) + c) % MAX_TABLE; } return hash % MAX_TABLE; } void init() { //printf("init()\n"); for (register int i = 0; i<MAX_TABLE; i++) { tb[i].key[0] = 0; tb[i].data[0] = 0; tb[i].keyTbIndex = -1; keyTb[i] = -1; } } void add(char key[LEN + 1], char value[LEN + 1]) { //printf("add %s %s \n",key,value); unsigned long h = hash(key); int cnt; while (tb[h].key[0] != 0) { if (str_cmp(tb[h].key, key, LEN + 1)>0) { //printf("Error1\n"); return; } h = (h + 1) % MAX_TABLE; } str_cpy(tb[h].key, key, LEN + 1); str_cpy(tb[h].data, value, LEN + 1); unsigned long kh = hash(value); cnt = MAX_TABLE; while (keyTb[kh] >= 0 && cnt--) { kh = (kh + 1) % MAX_TABLE; } // if(cnt<0) printf("[err%d]",0); keyTb[kh] = h; tb[h].keyTbIndex = kh; //dump(); } void get(int field, char key[LEN + 1], char value[LEN + 1]) { //printf("get () %d %s %s\n",field,key,value); if (field == KEY) { unsigned long h = hash(key); int cnt = MAX_TABLE; value[0] = 0; while (cnt--) { //printf("[1]"); if (str_cmp(tb[h].key, key, LEN + 1) > 0) { //printf("[2]"); str_cpy(value, tb[h].data, LEN + 1); //printf("[4]"); return; } h = (h + 1) % MAX_TABLE; //printf("[3] h %ld\n",h); } //printf("[5]"); } else { // printf("[1]"); unsigned long kh = hash(value); unsigned long h = keyTb[kh]; int cnt = MAX_TABLE; while (cnt--) { // printf("[2 %d]",cnt); if (str_cmp(tb[h].data, value, LEN + 1) > 0) { // printf("[3]"); str_cpy(key, tb[h].key, LEN + 1); // printf("[4 ]"); return; } do { kh = (kh + 1) % MAX_TABLE; h = keyTb[kh]; // printf("[%d %d]",kh,h); } while (h == -1); } } } void del(int field, char key[LEN + 1], char value[LEN + 1]) { //printf("del () %d %s %s\n",field,key,value); if (field == KEY) { unsigned long h = hash(key); int cnt = MAX_TABLE; while (tb[h].key[0] != 0 && cnt--) { if (str_cmp(tb[h].key, key, LEN) > 0) { tb[h].key[0] = 0; tb[h].data[0] = 0; keyTb[tb[h].keyTbIndex] = -1; tb[h].keyTbIndex = -1; // dump(); return; } h = (h + 1) % MAX_TABLE; } } else { unsigned long kh = hash(value); unsigned long h = keyTb[kh]; int cnt = MAX_TABLE; while (cnt--) { //printf("[1]"); if (str_cmp(tb[h].data, value, LEN) > 0) { //printf("[2]"); tb[h].key[0] = 0; tb[h].data[0] = 0; keyTb[tb[h].keyTbIndex] = -1; tb[h].keyTbIndex = -1; //dump(); return; } do { kh = (kh + 1) % MAX_TABLE; h = keyTb[kh]; //printf("[3 %d %d]\n",kh,h); } while (h == -1); } } //printf("Error2\n"); } void mod(int field, char key[LEN + 1], char value[LEN + 1]) { if (field == KEY) { del(field, key, value); add(key, value); } else { char k[LEN + 1]; get(field, k, value); del(field, k, value); add(key, value); } }

#ifndef _CRT_SECURE_NO_WARNINGS #define _CRT_SECURE_NO_WARNINGS #endif #include <stdio.h> #include <stdlib.h> #include <string.h> #define MAXN 100000 #define LEN 32 struct Data { char *key; char *value; }; static Data data[MAXN]; static int N = 0; static int Q; static int q; static int delque[2000]; #define CMD_GET 7 #define CMD_ADD 8 #define CMD_DEL 9 #define CMD_MOD 10 #define KEY 0 #define VALUE 1 extern void init(); extern void add(char key[LEN + 1], char value[LEN + 1]); extern void get(int field, char key[LEN + 1], char value[LEN + 1]); extern void del(int field, char key[LEN + 1], char value[LEN + 1]); extern void mod(int field, char key[LEN + 1], char value[LEN + 1]); static int seed; static int pseudo_rand() { seed = seed * 214013 + 2531011; return (seed >> 16) & 0x7fff; } static char* makeword() { char *w; int len = pseudo_rand() % (LEN - 8) + 8; w = (char *)malloc(sizeof(char) * (len + 1)); for (int i = 0; i < len; ++i) { int c = pseudo_rand() % 62; w[i] = (c < 26) ? c + 'a' : ((c < 52) ? c - 26 + 'A' : c - 52 + '0'); } w[len] = '\0'; return w; } static void deleteword(Data &datum) { free(datum.key); free(datum.value); datum.key = datum.value = NULL; } static void init_m() { for (int i = 0; i < N; ++i) if (data[i].key) { free(data[i].key); free(data[i].value); } init(); } static bool run() { scanf("%d%d%d", &N, &Q, &seed); for (int i = 0; i < N; ++i) { data[i].key = makeword(); data[i].value = makeword(); add(data[i].key, data[i].value); } bool okay = true; q = 0; for (int i = 0; okay && i < Q; ++i) { char key[LEN + 1], value[LEN + 1]; int index, cmd, field; cmd = pseudo_rand() % 10; if (cmd < CMD_GET) { do index = pseudo_rand() % N; while (data[index].key == NULL); field = pseudo_rand() % 2; if (field == KEY) { strcpy(key, data[index].key); get(field, key, value); if (strcmp(value, data[index].value)) okay = false; } else if (field == VALUE) { strcpy(value, data[index].value); get(field, key, value); if (strcmp(key, data[index].key)) okay = false; } } else if (cmd < CMD_ADD) { if (q > 0) index = delque[--q]; else if (N < MAXN) index = N++; else continue; data[index].key = makeword(); data[index].value = makeword(); strcpy(key, data[index].key); strcpy(value, data[index].value); add(key, value); } else if (cmd < CMD_DEL) { do index = pseudo_rand() % N; while (data[index].key == NULL); field = pseudo_rand() % 2; if (field == KEY) { strcpy(key, data[index].key); value[0] = '\0'; } else if (field == VALUE) { key[0] = '\0'; strcpy(value, data[index].value); } deleteword(data[index]); delque[q++] = index; del(field, key, value); } else if (cmd < CMD_MOD) { do index = pseudo_rand() % N; while (data[index].key == NULL); field = pseudo_rand() % 2; if (field == KEY) { free(data[index].value); data[index].value = makeword(); } else if (field == VALUE) { free(data[index].key); data[index].key = makeword(); } strcpy(key, data[index].key); strcpy(value, data[index].value); mod(field, key, value); } } return okay; } int main() { int TC; freopen("input.txt", "r", stdin); setbuf(stdout, NULL); scanf("%d", &TC); int totalscore = 0; for (int testcase = 1; testcase <= TC; ++testcase) { int score; init_m(); score = run() ? 100 : 0; printf("#%d %d\n", testcase, score); totalscore += score; } printf("total score = %d\n", totalscore / TC); return 0; }

10 100000 100000 13277011 100000 100000 78266573 100000 100000 50567591 100000 100000 93729909 100000 100000 14771441 100000 100000 10864360 100000 100000 62483997 100000 100000 91198972 100000 100000 12295247 100000 100000 3312967