甲题题解-1116. Come on! Let’s C (20)-（素数筛选法）

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

用vis标记出现过的id，checked标记询问过的id。至于如何判断排名为素数，用素数筛选法预处理一下即可，水题。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string.h>
using namespace std;
/*
素数筛选法
*/
const int maxn=+;
int isPrime[maxn];
int vis[maxn];
int checked[maxn];
int ranklist[maxn];void init(){
for(int i=;i<maxn;i++)
isPrime[i]=;
isPrime[]=;
for(int i=;i<maxn;i++){
if(isPrime[i]){
for(int j=i*;j<maxn;j+=i){
isPrime[j]=;
}
}
}
}int main()
{
init();
int n,k;
int a;
memset(vis,,sizeof(vis));
memset(checked,,sizeof(checked));
scanf("%d",&n);
for(int i=;i<=n;i++){
scanf("%d",&a);
ranklist[a]=i;
vis[a]=;
}
scanf("%d",&k);
for(int i=;i<k;i++){
scanf("%d",&a);
if(!vis[a]){
printf("%04d: Are you kidding?\n",a);
}
else if(!checked[a]){
if(ranklist[a]==){
printf("%04d: Mystery Award\n",a);
}
else if(isPrime[ranklist[a]]){
printf("%04d: Minion\n",a);
}
else{
printf("%04d: Chocolate\n",a);
}
checked[a]=;
}
else{
printf("%04d: Checked\n",a);
}
}
return ;
}