boj 14622

해결방법

에라토스테네스의 체를 이용하여 소수를 구함

각 조건에 맞게 시뮬레이션이 돌려주면된다.

문제의 설명이 조금 이상하긴하다.

아래는 소스코드이다.

#include <iostream> 

#include <iterator>

#include <algorithm> 

#include <vector>

#include <list>

#include <map>

#include <set>

#include <queue>

#include <stack>

#include <string>

#include <cmath>

#include <cstdio>

#include <cstring>

using namespace std;

#define MOD 1000000007

#define INF 2147483647

#define LNF 9223372036854775807

#define pb push_back

#define mp make_pair

typedef long long ll;

typedef unsigned long long ull;

typedef pair<ll,ll> pll;

typedef pair<int,int> pii;

int n,number[5000001];

int main(){

freopen("sample.txt","r",stdin);

scanf("%d",&n);

int len=sqrt(5000000);

ll ascore=0,bscore=0;

vector<int> aBig,bBig;

for(int i=2;i<=len;i++){

if(number[i]==-1) continue;

for(int j=i+i;j<5000001;j+=i) number[j]=-1;

}

number[1]=-1;

for(int i=0,a,b;i<n;i++){

scanf("%d%d",&a,&b);

if(number[a]==-1){

if(bBig.size()<3) bscore+=1000;

else bscore+=bBig[0];

}

else if(number[a]!=0){

ascore-=1000;

}

else{

number[a]=1;

aBig.insert(lower_bound(aBig.begin(),aBig.end(),a),a);

if(aBig.size()>3) aBig.erase(aBig.begin());

}

if(number[b]==-1){

if(aBig.size()<3) ascore+=1000;

else ascore+=aBig[0];

}

else if(number[b]!=0){

bscore-=1000;

}

else{

number[b]=2;

bBig.insert(lower_bound(bBig.begin(),bBig.end(),b),b);

if(bBig.size()>3) bBig.erase(bBig.begin());

}

}

if(ascore<bscore) printf("소수 마스터 갓규성\n");

else if(ascore==bscore) printf("우열을 가릴 수 없음\n");

else printf("소수의 신 갓대웅\n");

return 0;

}