#245505 (C++11) No.7 プライムナンバーゲーム

• 問題: No.7 プライムナンバーゲーム
• ユーザー: kt_tenel
• 提出日時: 2018-03-19 22:06:28
• 言語: C++11 (gcc 11.4.0)
• 結果: AC
• 実行時間: 10 ms / 5,000 ms
• コード長: 1,800 bytes
• コンパイル時間: 695 ms
• コンパイル使用メモリ: 92,132 KB
• 実行使用メモリ: 5,248 KB
• 最終ジャッジ日時: 2024-10-01 16:09:53
• 合計ジャッジ時間: 1,320 ms
• ジャッジサーバーID （参考情報）: judge4 / judge1

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 5,248 KB
testcase_01	AC	2 ms; 5,248 KB
testcase_02	AC	9 ms; 5,248 KB
testcase_03	AC	3 ms; 5,248 KB
testcase_04	AC	2 ms; 5,248 KB
testcase_05	AC	2 ms; 5,248 KB
testcase_06	AC	4 ms; 5,248 KB
testcase_07	AC	4 ms; 5,248 KB
testcase_08	AC	3 ms; 5,248 KB
testcase_09	AC	6 ms; 5,248 KB
testcase_10	AC	1 ms; 5,248 KB
testcase_11	AC	5 ms; 5,248 KB
testcase_12	AC	7 ms; 5,248 KB
testcase_13	AC	2 ms; 5,248 KB
testcase_14	AC	10 ms; 5,248 KB
testcase_15	AC	9 ms; 5,248 KB
testcase_16	AC	8 ms; 5,248 KB

ソースコード

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <sstream>
#include <set>
#include <map>
#include <vector>
#include <list>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <queue>
#include <bitset>     //UWAGA - w czasie kompilacji musi byc znany rozmiar wektora - nie mozna go zmienic
#include <cassert>
#include <iomanip>        //do setprecision
#include <ctime>
#include <complex>
using namespace std;

#define FOR(i,b,e) for(int i=(b);i<(e);++i)
#define FORQ(i,b,e) for(int i=(b);i<=(e);++i)
#define FORD(i,b,e) for(int i=(b)-1;i>=(e);--i)
#define REP(x, n) for(int x = 0; x < (n); ++x)

#define ST first
#define ND second
#define PB push_back
#define MP make_pair
#define LL long long
#define ULL unsigned LL
#define LD long double

const double pi = 3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342;
const int mod=1000000007;
int prime[100002]={};
int Er_N=10000;
void Er(){//Eratosthenes  1:PRIME  0:NOT PRIME
	for(int i = 2; i < Er_N; i++){
		prime[i] = 1;
	}
	int limit_Er_roop=sqrt(Er_N);
	for(int i = 2; i < limit_Er_roop; i++){
		if(prime[i]){
			for(int j = 0; i * (j + 2) < Er_N; j++){
				prime[i *(j + 2)] = 0;
			}
		}
	}
}
int idx;
int a[5000];
int wl[10001];//1:win 0:lose

void mem(int n){
		if(wl[n]!=-1)return;
		int f=0;
		FORD(i,idx,0){
			int t=n-a[i];
			if(t<=2)continue;
			if(wl[t]==-1)mem(t);
			if(wl[t]==0)f=1;
		}
		wl[n]=f;
}

int main(){
	Er();
	idx=0;
	string re[2]={"Lose","Win"};
	FOR(i,0,10000){
		if(prime[i])a[idx++]=i;
	}
	FOR(i,0,10001){
		wl[i]=-1;
	}
	wl[0]=wl[1]=1;
	wl[2]=wl[3]=0;
	FOR(i,2,4){
		FOR(j,0,idx){
			int t=i+a[j];
			if(t>10000)break;
			wl[t]=1;
		}
	}
	int n;
	cin>>n;
	mem(n);
	cout<<re[wl[n]]<<endl;

    return 0;
}