結果

問題 No.7 プライムナンバーゲーム
コンテスト
ユーザー Tatsu_mr
提出日時 2024-10-01 21:36:06
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 16 ms / 5,000 ms
コード長 2,211 bytes
コンパイル時間 3,705 ms
コンパイル使用メモリ 256,676 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-10-01 21:36:11
合計ジャッジ時間 4,228 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define rep(i, n) for(long long i = 0; i < n; i++)
#define ALL(v) (v).begin(), (v).end()
using namespace std;

using lint = long long;

struct Sieve {
    private:
    int n;
    vector<int> IdxtoVal, ValtoIdx;
    vector<bool> deleted;
    
    void build() {
        int sz = (n % 30 == 0 ? n / 30 : n / 30 + 1);
        sz *= 8;
        IdxtoVal = {1, 7, 11, 13, 17, 19, 23, 29};
        for (int i = 0; i < 8; i++) {
            ValtoIdx[IdxtoVal[i]] = i;
        }
        deleted.assign(sz, false);
        for (int i = 1; i < sz; i++) {
            if (deleted[i]) {
                continue;
            }
            int p = getval(i);
            for (int j = i; j < sz; j++) {
                int q = getval(j);
                if (q > n / p) {
                    break;
                }
                deleted[getidx(p * q)] = true;
            }
        }
    }
    
    int getval(int i) {
        return i / 8 * 30 + IdxtoVal[i % 8];
    }
    
    int getidx(int x) {
        return x / 30 * 8 + ValtoIdx[x % 30];
    }
    
    public:
    Sieve(int n_) : n(n_), IdxtoVal(8), ValtoIdx(30) {
        build();
    }
    
    bool isprime(int x) {
        if (x == 1) {
            return false;
        } else if (x == 2 || x == 3 || x == 5) {
            return true;
        } else if (x % 2 == 0 || x % 3 == 0 || x % 5 == 0) {
            return false;
        } else {
            return !deleted[getidx(x)];
        }
    }
    
    vector<int> primes() {
        vector<int> res;
        for (int i = 2; i <= n; i++) {
            if (isprime(i)) {
                res.emplace_back(i);
            }
        }
        return res;
    }
};

int main() {
    int n;
    cin >> n;
    auto ps = Sieve(n).primes();
    vector<int> dp(n + 1, -1);
    dp[0] = dp[1] = 1;
    auto f = [&](auto f, int x) -> int {
        if (dp[x] != -1) {
            return dp[x];
        }
        int res = 0;
        for (auto p : ps) {
            if (p > x) {
                break;
            }
            if (f(f, x - p) == 0) {
                res = 1;
            }
        }
        dp[x] = res;
        return res;
    };
    cout << (f(f, n) ? "Win" : "Lose") << endl;
}
0