結果

問題 No.7 プライムナンバーゲーム
ユーザー takerous7takerous7
提出日時 2020-03-15 12:21:52
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 1,679 bytes
コンパイル時間 1,733 ms
コンパイル使用メモリ 172,172 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-05-03 17:23:08
合計ジャッジ時間 4,218 ms
ジャッジサーバーID
(参考情報)
judge4 / judge5
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 122 ms
5,248 KB
testcase_01 AC 128 ms
5,376 KB
testcase_02 AC 121 ms
5,376 KB
testcase_03 AC 122 ms
5,376 KB
testcase_04 AC 118 ms
5,376 KB
testcase_05 AC 119 ms
5,376 KB
testcase_06 AC 119 ms
5,376 KB
testcase_07 AC 117 ms
5,376 KB
testcase_08 AC 117 ms
5,376 KB
testcase_09 WA -
testcase_10 AC 123 ms
5,376 KB
testcase_11 AC 121 ms
5,376 KB
testcase_12 AC 121 ms
5,376 KB
testcase_13 AC 117 ms
5,376 KB
testcase_14 WA -
testcase_15 WA -
testcase_16 AC 120 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

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