結果

問題 No.7 プライムナンバーゲーム
コンテスト
ユーザー takerous7
提出日時 2020-03-15 12:21:52
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,679 bytes
コンパイル時間 1,594 ms
コンパイル使用メモリ 173,456 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2024-11-24 20:24:11
合計ジャッジ時間 4,584 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 14 WA * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define  rep(i, n) for(int i = 0; i < n; i++) 
#define  all(x) (x).begin(),(x).end()     // 昇順ソート
#define  rall(v) (v).rbegin(), (v).rend() // 降順ソート
#define  INF 1LL << 60
typedef long long int LL;
typedef long long int ll;
#define pll pair<ll, ll>
#define F first
#define S second
const int MOD = 1000000007;
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return true; } return false; }
//sort(all(x))とするとソートできるよ
// 10^x は pow(10,(x)) 
// 任意のlogは　対数の底の変換を使う    log(N) / log(任意の底)

std::vector<bool> IsPrime;
void sieve(LL max){
    if(max+1 > IsPrime.size()){     // resizeで要素数が減らないように
        IsPrime.resize(max+1,true); // IsPrimeに必要な要素数を確保
    } 
    IsPrime[0] = false; // 0は素数ではない
    IsPrime[1] = false; // 1は素数ではない

    for(LL i=2; i*i<=max; ++i) // 0からsqrt(max)まで調べる
        if(IsPrime[i]) // iが素数ならば
            for(LL j=2; i*j<=max; ++j) // (max以下の)iの倍数は
                IsPrime[i*j] = false;      // 素数ではない
}


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

    bool win[10001];
    win[0] = true;
    win[1] = true;
    for(int i = 2;i <= 10000;i++){
        rep(j,10001){
            if(!IsPrime[j])continue;
            if(j == 1)continue;
            if(i - j < 0)break;
            win[i] |= !win[i-j];
        }
    }

    if(win[N])cout << "Win" << endl;
    else cout << "Lose" << endl;
}
0