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

• 問題: No.7 プライムナンバーゲーム
• ユーザー: m1025o1184t
• 提出日時: 2020-01-03 20:58:18
• 言語: C++14 (gcc 12.3.0 + boost 1.83.0)
• 結果: WA
• 実行時間: -
• コード長: 1,111 bytes
• コンパイル時間: 1,896 ms
• コンパイル使用メモリ: 171,888 KB
• 実行使用メモリ: 6,944 KB
• 最終ジャッジ日時: 2024-05-02 07:28:32
• 合計ジャッジ時間: 2,620 ms
• ジャッジサーバーID （参考情報）: judge4 / judge2

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	4 ms; 6,812 KB
testcase_01	AC	4 ms; 6,816 KB
testcase_02	WA	-
testcase_03	WA	-
testcase_04	AC	3 ms; 6,940 KB
testcase_05	WA	-
testcase_06	AC	7 ms; 6,940 KB
testcase_07	AC	6 ms; 6,944 KB
testcase_08	AC	4 ms; 6,944 KB
testcase_09	WA	-
testcase_10	WA	-
testcase_11	AC	5 ms; 6,940 KB
testcase_12	AC	12 ms; 6,940 KB
testcase_13	AC	12 ms; 6,944 KB
testcase_14	WA	-
testcase_15	WA	-
testcase_16	AC	14 ms; 6,940 KB

ソースコード

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);++i)
#define all(a) (a).begin(),(a).end()
#define dunk(a) cout << (a) << endl
using namespace std;
typedef long long ll;

class Prime
{
	int i, iLimit;

public:
	bool isPrime(int a);
};

bool Prime::isPrime(int a)
{
	if (a == 1) return false;

	iLimit = (int)sqrt(a);
	for (i = 2; i <= iLimit; i++) {
		if (a % i == 0) break;
	}
	if (i == iLimit + 1) {
		return true;
	}
	else {
		return false;
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	bool elf;
	Prime p;
	vector<pair<bool,bool>> dp(1000000);
	vector<int> jud;
	for (int i = 1; i <= n; ++i) {
		elf = p.isPrime(i);
		if (elf) jud.emplace_back(i);
	}
	int k = jud.size();
	
	//Winを仮定して考える
	dp[0].first = true; dp[1].second = true;
	dp[1].first = true; dp[1].second = true;
	for (int i = 0; i <= n; ++i) {
		if (dp[i].first) {
			for (int j = 0; j < k; ++j) {
				dp[i + jud[j]].first = true;
				dp[i + jud[j]].second = (dp[i].second) ? true : false;
			}
		}
	}

	if (dp[n].first && dp[n].second) puts("Win");
	else puts("Lose");

	return 0;
}