记录编号	562878	评测结果	AAAAAAAAAA
题目名称	查字典	最终得分	100
用户昵称	yrtiop	是否通过	通过
代码语言	C++	运行时间	0.090 s
提交时间	2021-07-10 10:03:36	内存使用	1.98 MiB

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <string>
using namespace std;
const int maxn = 10005;
string s;
int n,m;
int rd[maxn],son[maxn][2],val[maxn];
string key[maxn];
int rt,sz;
void rotate(int& x,int d) {
    int k = son[x][d ^ 1];
    son[x][d ^ 1] = son[k][d];
    son[k][d] = x;
    x = k;
    return ;
}
void insert(int& p,string s,int x) {
    if(!p) {
        p = ++ sz;
        son[p][0] = son[p][1] = 0;
        rd[p] = rand();
        key[p] = s;
        val[p] = x;
        return ;
    }
    if(key[p] == s)return ;
    int d = s > key[p];
    insert(son[p][d] , s , x);
    if(rd[p] < rd[son[p][d]]) {
        rotate(p , d ^ 1);
    }
    return ;
}
int find(int& p,string s) {
    return key[p] == s ? val[p] : find(son[p][s > key[p]] , s);
}
int main() {
    freopen("scanword.in","r",stdin);
    freopen("scanword.out","w",stdout);
    ios::sync_with_stdio(0);
    cin >> n;
    for(int i = 1;i <= n;++ i) {
        int x;
        cin >> s >> x;
        insert(rt , s , x);
    }
    cin >> m;
    for(int i = 1;i <= m;++ i) {
        cin >> s;
        printf("%d\n",find(rt , s));
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}