結果

問題 No.7 プライムナンバーゲーム
コンテスト
ユーザー PicklesSuperior
提出日時 2018-10-23 23:42:21
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 715 ms / 5,000 ms
コード長 1,500 bytes
コンパイル時間 596 ms
コンパイル使用メモリ 67,716 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-01 16:16:49
合計ジャッジ時間 5,195 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>

using namespace std;

int main(){
    int N;
    cin >> N;

    vector<int> Lose;
    vector<int> prime;
    Lose.push_back(2);
    Lose.push_back(3);
    prime.push_back(2);
    string flag = "Lose";

    for(int i=3;i<=10000;i+=2){
        int k=0;
        for(int j=3;j<=sqrt(i);j+=2){
            if(i%j==0){
                k=1;
                break;
            }
        }
        if(k==0) prime.push_back(i);
    }
    /*
    for(int i=0;i<prime.size();i++){
        cout << prime[i] << " ";
    }
    */
    int prime_size = prime.size();
    for(int i=4;i<=N;i++){
        for(int j=0;j<prime_size;j++){
            if(prime[j] < i){
                for(int k=0;k<Lose.size();k++){
                    if(i - prime[j] == Lose[k]){
                        flag = "Win";
                        break;
                    }
                }
            }else{
                break;
            }
            if(flag == "Win") break;
        }
        if(flag == "Lose"){
            Lose.push_back(i);
        }
        flag = "Lose";
    }
 
    /*
    for(int i=0;i<Lose.size();i++){
        cout << Lose[i] << " ";
    }
    cout << endl;
    */

    flag = "Win";
    for(int i=0;i<Lose.size();i++){
        if(N == Lose[i]){
            flag = "Lose";
            break;
        }
    }
 
    if(flag == "Lose"){
        cout << "Lose" << endl;
    }else{
        cout << "Win" << endl;
    }

    return 0;
}
0