結果
問題 | No.7 プライムナンバーゲーム |
ユーザー |
![]() |
提出日時 | 2021-01-18 22:26:17 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 7 ms / 5,000 ms |
コード長 | 1,046 bytes |
コンパイル時間 | 1,485 ms |
コンパイル使用メモリ | 169,928 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-01 16:42:04 |
合計ジャッジ時間 | 2,152 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 17 |
ソースコード
#include <bits/stdc++.h> #define rep(i, n) for (int i=0; i<(n); i++) using namespace std; template<class T> inline bool chmax(T& a, T b){ if (a < b){ a = b; return true; } return false; } template<class T> inline bool chmin(T& a, T b){ if (a > b){ a = b; return true; } return false; } vector<int> prime_sieve(int n){ vector<int> sieve(n+1, 0), prime; for (int i=2; i<n+1; i++){ if (sieve[i]==0){ sieve[i] = i; prime.emplace_back(i); } for (int p: prime){ if (p > sieve[i] || i * p > n) break; sieve[i * p] = p; } } return sieve; } bool dp[10101]; int main(){ int n; cin>>n; dp[0] = true; dp[1] = true; vector<int> sieve = prime_sieve(n); vector<int> p; for (int x = 2; x<=n; x++){ if (x == sieve[x]) p.push_back(x); bool win = false; for(int i=0; i<p.size(); i++) if(!dp[x-p[i]]) win=true; dp[x] = win; } if (dp[n]) cout<<"Win"<<endl; else cout<<"Lose"<<endl; return 0; }