結果
問題 | No.7 プライムナンバーゲーム |
ユーザー |
![]() |
提出日時 | 2020-04-15 14:52:09 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 6 ms / 5,000 ms |
コード長 | 1,086 bytes |
コンパイル時間 | 982 ms |
コンパイル使用メモリ | 99,036 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-01 16:32:25 |
合計ジャッジ時間 | 1,636 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 17 |
ソースコード
// I SELL YOU...! #include<iostream> #include<vector> #include<algorithm> #include<functional> #include<queue> #include<chrono> #include<iomanip> #include<map> #include<set> using namespace std; using ll = long long; using P = pair<ll,ll>; using TP = tuple<ll,ll,ll>; void init_io(){ cin.tie(0); ios::sync_with_stdio(false); cout << setprecision(18); } bool dp[11000]; bool used[11000]={}; vector<ll> prime; vector<ll> eratos(int max){ vector<ll> res; vector<bool> cp_list(max+1,true); cp_list[0]=false; cp_list[1]=false; for(ll i=2;i<=max;i++){ if(cp_list[i]){ res.push_back(i); for(ll j=2;j*i<=max;j++){ cp_list[i*j]=false; } } } return res; } bool solve(ll n){ if(used[n]) return dp[n]; used[n] = true; if(n==0||n==1){ return dp[n] = true; }else{ for(auto i:prime){ if(i>n) break; if(!solve(n-i)){ return dp[n] = true; } } return false; } } signed main(){ init_io(); ll n; cin >> n; prime = eratos(n); solve(n); if(dp[n]) cout <<"Win\n"; else cout <<"Lose\n"; }