結果
問題 |
No.7 プライムナンバーゲーム
|
ユーザー |
![]() |
提出日時 | 2025-01-04 01:40:36 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 38 ms / 5,000 ms |
コード長 | 1,212 bytes |
コンパイル時間 | 3,865 ms |
コンパイル使用メモリ | 284,064 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2025-01-04 01:40:42 |
合計ジャッジ時間 | 5,293 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 17 |
ソースコード
#include <bits/stdc++.h> using namespace std; #ifdef LOCAL #include "settings/debug.cpp" #else #define Debug(...) void(0) #endif #define rep(i, n) for (int i = 0; i < (n); ++i) using ll = long long; using ull = unsigned long long; int main() { int n; cin >> n; vector<int> primes; { vector<bool> is_prime(n + 1, true); is_prime[0] = is_prime[1] = false; for (int i = 2; i <= n; ++i) { if (is_prime[i]) { primes.push_back(i); for (int j = i * 2; j <= n; j += i) is_prime[j] = false; } } } vector memo(2, vector<int>(n + 1, -1)); // x を受け取ったとき me は勝てるか function<bool(int, int)> dfs = [&](int me, int n) { if (n == 0 || n == 1) return !me; if (memo[me][n] >= 0) return !!(memo[me][n]); if (me == 0) { for (int x : primes) { if (n >= x) { if (dfs(1, n - x)) return !!(memo[me][n] = 1); } } return !!(memo[me][n] = 0); } else { for (int x : primes) { if (n >= x) { if (!dfs(0, n - x)) return !!(memo[me][n] = 0); } } return !!(memo[me][n] = 1); } }; cout << (dfs(0, n) ? "Win" : "Lose") << endl; return 0; }