結果

問題 No.7 プライムナンバーゲーム
コンテスト
ユーザー dgd1724
提出日時 2016-12-01 07:07:01
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
TLE  
実行時間 -
コード長 1,770 bytes
コンパイル時間 2,029 ms
コンパイル使用メモリ 167,764 KB
実行使用メモリ 27,724 KB
最終ジャッジ日時 2024-11-27 15:15:17
合計ジャッジ時間 74,775 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 3 WA * 3 TLE * 11
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

//const static double	de_PI	= 3.14159265358979323846;
//const static double	de_EPS	= 0.000001;
//const static int	de_MOD = 1000000007;
//const static int	de_MAX = 999999999;
//const static int	de_MIN = -999999999;

inline void Enumerate_PrimeNumber(const int &N, std::vector<int> &result) {

	std::vector<bool> flg(N + 1, true);
	for (int i = 2; i*i <= N; i++) {
		if (flg[i]) {
			for (int j = i + i; j <= N; j += i) {
				flg[j] = false;
			}
		}
	}
	for (int i = 2; i < N + 1; i++) {
		if (flg[i]) { result.push_back(i); }
	}

}

inline bool Judge_PrimeNumber(const int &a) {

	if (a < 2) { return false; }
	if (a == 2 || a == 3) { return true; }
	if (a % 2 == 0) { return false; }
	if (a % 6 != 1 && a % 6 != 5) { return false; }

	for (int i = 5; i <= a / i; i += 2) {
		if (a%i == 0) { return false; }
	}

	return true;
}

int main(void) {

	//std::ifstream inf("123.txt");	std::cin.rdbuf(inf.rdbuf());

	int N = 0;
	std::cin >> N;
	std::vector<int> pn;
	Enumerate_PrimeNumber(N, pn);

	bool flg = true;
	std::vector<int> now, next;
	now.push_back(N);
	

	while (1) {
		for (unsigned int j = 0; j < now.size(); j++) {
			int temp = now[j];
			for (unsigned int i = 0; i < pn.size() && pn[i] <= temp; i++) {
				int a = temp - pn[i];
				if (a > 1) {
					if (!Judge_PrimeNumber(a - 2)) {
						if (!Judge_PrimeNumber(a - 3)) {
							next.push_back(a);
						}
					}
				}
			}
		}
		if (next.empty()) { break; }
		std::sort(next.begin(), next.end());
		next.erase(std::unique(next.begin(), next.end()), next.end());
		
		now.clear();
		std::copy(next.begin(), next.end(), std::back_inserter(now));
		next.clear();
		flg = !flg;
		
	}

	if (flg) {
		std::cout << "Lose" << std::endl;
	}
	else {
		std::cout << "Win" << std::endl;
	}

}
0