結果
問題 | No.7 プライムナンバーゲーム |
ユーザー |
|
提出日時 | 2015-12-13 14:30:25 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 9 ms / 5,000 ms |
コード長 | 950 bytes |
コンパイル時間 | 555 ms |
コンパイル使用メモリ | 67,848 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-10-01 15:38:18 |
合計ジャッジ時間 | 1,226 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 17 |
ソースコード
#include <iostream> #include <vector> #include <cmath> using namespace std; int main(){ cin.tie(0); ios::sync_with_stdio(false); int n; cin >> n; vector<int> prime(n-1); vector<bool> judge(n-1, false); for(int i=2; i<=n; ++i) prime[i-2]=i; for(int i=0, sqrtn=sqrt(n), erased=0; i<=sqrtn-erased; ++i){ for(vector<int>::iterator it=prime.begin()+1+i; it<prime.end(); ++it){ if(*it%prime[i]==0){ if(*it<sqrtn) ++erased; prime.erase(it); --it; } } } for(vector<bool>::iterator judge_it=judge.begin(); judge_it!=judge.end(); ++judge_it){ int check_num=(judge_it-judge.begin()+2); for(vector<int>::iterator prime_it=prime.begin(); prime_it!=prime.end() && *prime_it<check_num; ++prime_it){ int tmp=check_num-*prime_it; if(tmp==0 || tmp==1) continue; if(judge[tmp-2]==false){ *judge_it=true; break; } } } cout << ((judge[n-2]==true) ? "Win\n" : "Lose\n"); return 0; }