PAT1059

1. 冠军将赢得一份“神秘大奖”（比如很巨大的一本学生研究论文集……）。
2. 排名为素数的学生将赢得最好的奖品 —— 小黄人玩偶！
3. 其他人将得到巧克力。

给定比赛的最终排名以及一系列参赛者的ID，你要给出这些参赛者应该获得的奖品。

#include<iostream>
#include<string>
#include<algorithm>
#include <math.h> 
#include<set>
#include<map>
using namespace std;

bool isprime(int a) {
    if (a % 2 == 0) return false;
    int t = sqrt(a);
    if (t!=1&&a % t == 0) return false;
    for(int i = 3;i < t;i+=2)
        if (a % i == 0) return false;
    return true;
}
int main() {
    int n;cin >> n;
    string s;
    map<string,int> v;
    for (int i = 1;i <= n;++i) {
        cin >> s;
        v.insert({ s,i });
    }

    int t;cin >> t; 
    set<string> iset;
    while (t--) {
        cin >> s;
        auto iter1 = v.find(s);
        if (iter1 == v.end()) {
            cout << s << ": Are you kidding?" << endl;
            continue;
        }
        if (iset.find(s) != iset.end()) {
            cout << s << ": Checked" << endl;
            continue;
        }
        else iset.insert({ s });
        if(iter1->second == 1)
            cout << s << ": Mystery Award" << endl;
        else if(isprime(iter1->second))
            cout << s << ": Minion" << endl;
        else cout << s << ": Chocolate" << endl;
    }           
    return 0;
}

1. 由于用vector进行存储会造成查找的复杂度升高，造成运行超时
2. 判断是否为素数时，为了减少时间复杂度（例如49=7*7）,注意a=3的情况。