比赛 |
咲 -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();
}