DS Certi (Pro) 오답노트 - jjin-choi/study_note GitHub Wiki

#define MAX_N			5
#define MAX_NAME_LEN	7
#define MAX_TAG_LEN		4

typedef unsigned long long ull;

const int MAX = (int)(5e4 + 5);
const int SIZE = 1 << 20;
const int MASK = SIZE - 1;
int M, b_cnt, h_cnt;

void mstrcpy(char dst[], const char src[]) {
	int c = 0;
	while ((dst[c] = src[c]) != '\0') ++c;
}

int mstrcmp(const char str1[], const char str2[]) {
	int c = 0;
	while (str1[c] != '\0' && str1[c] == str2[c]) ++c;
	return str1[c] - str2[c];
}

struct _book {
	char name[7];
	ull types[5];
	int t_cnt;
	int is_delete;

	_book* prev;
	_book* next;
	_book* alloc(char _name[], ull _types[], int _t_cnt, _book* _prev, _book* _next) {
		mstrcpy(name, _name), t_cnt = _t_cnt, is_delete = 0, prev = _prev, next = _next;
		for (int t = 0; t < t_cnt; t++) types[t] = _types[t];

		if (prev) prev->next = this;
		if (next) next->prev = this;
		return this;
	}
	_book* erase() {
		_book* ret = this->prev;
		if (prev) prev->next = this->next;
		if (next) next->prev = this->prev;
		return ret;
	}
	_book* move(_book* section) {
		_book* ret = erase();

		this->next = section->next;
		if (section->next) section->next->prev = this;

		this->prev = section;
		section->next = this;
		return ret;
	}
	bool comp_type(ull type) {
		for (int t = 0; t < t_cnt; t++) {
			if (types[t] == type) return true;
		}
		return false;
	}
} books[MAX + 105], *sections[105];

struct _hash {
	_book* book;
	_hash* next;
	_hash* alloc(_book* _p_book, _hash* _next) {
		book = _p_book, next = _next;
		return this;
	}
} h_buff[MAX], *h_head[SIZE];

#include <stdio.h>

ull str_to_int(char type[]) {
	ull ret = 0;
	for (int s = 0; type[s]; s++) {
		int str = type[s] > 'Z' ? type[s] - 'a' + 26 : type[s] - 'A';
		ret = ret * 53 + str + 1;
	}
	return ret;
}

ull hash_func(char name[]) {
	ull ret = 0;
	for (int n = 0; name[n]; n++) {
		int str = name[n] > 'Z' ? name[n] - 'a' + 26 : name[n] - 'A';
		ret = ret * 53 + str + 1;
	}
	return ret & MASK;
}

_hash* probing(char name[]) {
	ull key = hash_func(name);

	for (_hash* p = h_head[key]; p; p = p->next) {
		if (!p->book->is_delete && !mstrcmp(p->book->name, name)) return p;
	}
	return 0;
}

void init(int M)
{
	::M = M, b_cnt = 0, h_cnt = 0;
	char dummy[5] = { 'D', 'U', 'M', 'M', 'Y' };
	ull types[5] = { 0, 0, 0, 0, 0 };

	for (int m = 1; m <= M; m++) sections[m] = books[b_cnt++].alloc(dummy, types, 0, 0, 0);
}

void add(char mName[MAX_NAME_LEN], int mTypeNum, char mTypes[MAX_N][MAX_TAG_LEN], int mSection)
{
	ull types[5];
	ull key = hash_func(mName);
	for (int t = 0; t < mTypeNum; t++) types[t] = str_to_int(mTypes[t]);

	_book* book = books[b_cnt++].alloc(mName, types, mTypeNum, sections[mSection], sections[mSection]->next);
	h_head[key] = h_buff[h_cnt++].alloc(book, h_head[key]);
}

int moveType(char mType[MAX_TAG_LEN], int mFrom, int mTo)
{
	int cnt = 0;
	ull type = str_to_int(mType);
	for (_book* book = sections[mFrom]->next; book; book = book->next) {
		if (!book->is_delete && book->comp_type(type)) {
			book = book->move(sections[mTo]);
			cnt++;
		}
	}
	return cnt;
}

void moveName(char mName[MAX_NAME_LEN], int mSection)
{
	_hash* p = probing(mName);
	if (p) p->book->move(sections[mSection]);
}

void deleteName(char mName[MAX_NAME_LEN])
{
	_hash* p = probing(mName);
	if (p) {
		p->book->erase();
		p->book->is_delete = 1;
	}
}

int countBook(int mTypeNum, char mTypes[MAX_N][MAX_TAG_LEN], int mSection)
{
	int cnt = 0;
	for (_book* book = sections[mSection]->next; book; book = book->next) {
		for (int t = 0; t < mTypeNum; t++) {
			ull type = str_to_int(mTypes[t]);
			if (!book->is_delete && book->comp_type(type)) {
				cnt++; break;
			}
		}
	}
	return cnt;
}