比赛 咲 -Saki- 互测赛 评测结果 AAAAAAAAAA
题目名称 天才麻将少女什么编 最终得分 100
用户昵称 Citron酱 运行时间 0.124 s
代码语言 C++ 内存使用 3.27 MiB
提交时间 2012-07-19 09:47:41
显示代码纯文本
#include <string>
#include <fstream>
#include <cstdlib>

#define I_F "sakinani.in"
#define O_F "sakinani.out"

const short MAXs=50;
const int MAXc=250;
const int P=32767;

using std::string;

struct sch
{
	string school;
	long s;
	sch *left, *right, *father;
};

struct cha
{
	string name;
	short w;
	int z;
	sch *school;
	cha *left, *right, *father;
};

std::ifstream fin(I_F);

cha c_pool[MAXc];
cha *cp=c_pool;
cha *c_root=NULL;
sch s_pool[MAXs];
sch *sp=s_pool;
sch *s_root=NULL;

template<typename str>
inline void Left_turn(str*,str*&);
template<typename str>
inline void Right_turn(str*,str*&);
void C_insert(const string&, sch*);
cha* C_find(const string&);
sch* S_insert(const string&);
sch* S_find(const string&);
void S_add(sch*, const short&);
void Input();
void Search();
void Output();

int main()
{
	Input();
	Search();
	Output();
	return 0;
}

template<typename str>
inline void Left_turn(str *p, str *&root)
{
	str *f=p->father, *b=p->right;
	if (f->father==NULL)
		root=p;
	else
		if (f==f->father->left)
			f->father->left=p;
		else
			f->father->right=p;
	p->father=f->father;
	f->father=p;
	p->right=f;
	f->left=b;
	if (b!=NULL)
		b->father=f;
}

template<typename str>
inline void Right_turn(str *f, str *&root)
{
	str *p=f->father, *b=f->left;
	if (p->father==NULL)
		root=f;
	else
		if (p==p->father->left)
			p->father->left=f;
		else
			p->father->right=f;
	f->father=p->father;
	p->father=f;
	f->left=p;
	p->right=b;
	if (b!=NULL)
		b->father=p;
}

void C_insert(const string &name, sch *school)
{
	if (c_root==NULL)
	{
		c_root=cp++;
		c_root->name=name;
		c_root->school=school;
		c_root->w=1;
		c_root->z=rand()%P;
		c_root->father=c_root->left=c_root->right=NULL;
	}
	else
	{
		cha *i=c_root;
		bool flag=true;
		while (flag)
			if (name<i->name)
				if (i->left==NULL)
				{
					i->left=cp++;
					i->left->father=i;
					i=i->left;
					i->name=name;
					i->school=school;
					i->w=1;
					i->z=rand()%P;
					i->left=i->right=NULL;
					flag=false;
				}
				else
					i=i->left;
			else
				if (i->right==NULL)
				{
					i->right=cp++;
					i->right->father=i;
					i=i->right;
					i->name=name;
					i->school=school;
					i->w=1;
					i->z=rand()%P;
					i->left=i->right=NULL;
					flag=false;
				}
				else
					i=i->right;
		while (i->father!=NULL && i->z<i->father->z)
			if (i==i->father->left)
				Left_turn(i,c_root);
			else
				Right_turn(i,c_root);
	}
}

cha* C_find(const string &x)
{
	if (c_root==NULL)
		return NULL;
	cha *re=c_root;
	while (re!=NULL && re->name!=x)
		if (x<re->name)
			re=re->left;
		else
			re=re->right;
	return re;
}

sch* S_insert(const string &school)
{
	if (s_root==NULL)
	{
		s_root=sp++;
		s_root->school=school;
		s_root->s=0;
		s_root->father=s_root->left=s_root->right=NULL;
		return s_root;
	}
	else
	{
		sch *i=s_root;
		bool flag=true;
		while (flag)
			if (school<i->school)
				if (i->left==NULL)
				{
					i->left=sp++;
					i->left->father=i;
					i=i->left;
					i->school=school;
					i->s=0;
					i->left=i->right=NULL;
					flag=false;
				}
				else
					i=i->left;
			else
				if (i->right==NULL)
				{
					i->right=sp++;
					i->right->father=i;
					i=i->right;
					i->school=school;
					i->s=0;
					i->left=i->right=NULL;
					flag=false;
				}
				else
					i=i->right;
		return i;
	}
}

sch* S_find(const string &x)
{
	if (s_root==NULL)
		return NULL;
	sch* re=s_root;
	while (re!=NULL && re->school!=x)
		if (x<re->school)
			re=re->left;
		else
			re=re->right;
	return re;
}

void S_add(sch *p, const short &x)
{
	p->s+=x;
	while (p->father!=NULL && p->father->s<p->s)
		if (p==p->father->left)
			Left_turn(p,s_root);
		else
			Right_turn(p,s_root);
}

void Input()
{
	string ta, tb;
	string t;
	cha *p;
	sch *q;
	int n;
	fin>>n;
	for (int i=0; i<n; ++i)
	{
		fin>>ta>>tb;
		q=S_find(tb);
		if (q==NULL)
			q=S_insert(tb);
		C_insert(ta,q);
	}
	fin>>n;
	for (int i=0; i<n; ++i)
	{
		fin>>t;
		p=C_find(t);
		if (p!=NULL)
			p->w=2;
	}
}

void Search()
{
	string t;
	cha *pc;
	fin>>t;
	while (!fin.eof())
	{
		pc=C_find(t);
		if (pc!=NULL)
			S_add(pc->school,pc->w);
		fin>>t;
	}
	fin.close();
}

void Output()
{
	std::ofstream fout(O_F);
	fout<<s_root->school<<std::endl;
	fout.close();
}