結果

問題 No.7 プライムナンバーゲーム
ユーザー satonakatakumisatonakatakumi
提出日時 2021-08-11 16:00:06
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 4,688 bytes
コンパイル時間 2,027 ms
コンパイル使用メモリ 201,872 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-09-25 02:48:24
合計ジャッジ時間 2,978 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 14 ms
6,816 KB
testcase_01 AC 14 ms
6,812 KB
testcase_02 AC 14 ms
6,940 KB
testcase_03 AC 14 ms
6,944 KB
testcase_04 AC 14 ms
6,944 KB
testcase_05 AC 15 ms
6,940 KB
testcase_06 AC 15 ms
6,940 KB
testcase_07 AC 14 ms
6,940 KB
testcase_08 AC 14 ms
6,944 KB
testcase_09 WA -
testcase_10 AC 14 ms
6,944 KB
testcase_11 AC 14 ms
6,940 KB
testcase_12 AC 15 ms
6,944 KB
testcase_13 AC 15 ms
6,940 KB
testcase_14 WA -
testcase_15 WA -
testcase_16 AC 14 ms
6,944 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

// integer
using i8 = std::int8_t;
using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using i128 = __int128_t;
// unsigned integer
using u8 = std::uint8_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;
using u128 = __uint128_t;
// floating
using f32 = float;
using f64 = double;
using f80 = long double;
// vector
using vi8 = std::vector<i8>;
using vi16 = std::vector<i16>;
using vi32 = std::vector<i32>;
using vi64 = std::vector<i64>;
using vi128 = std::vector<i128>;
using vu8 = std::vector<u8>;
using vu16 = std::vector<u16>;
using vu32 = std::vector<u32>;
using vu64 = std::vector<u64>;
using vu128 = std::vector<u128>;
using vf32 = std::vector<f32>;
using vf64 = std::vector<f64>;
using vf80 = std::vector<f80>;
// vector vector
using vvi8 = std::vector<vi8>;
using vvi16 = std::vector<vi16>;
using vvi32 = std::vector<vi32>;
using vvi64 = std::vector<vi64>;
using vvi128 = std::vector<vi128>;
using vvu8 = std::vector<vu8>;
using vvu16 = std::vector<vu16>;
using vvu32 = std::vector<vu32>;
using vvu64 = std::vector<vu64>;
using vvu128 = std::vector<vu128>;
using vvf32 = std::vector<vf32>;
using vvf64 = std::vector<vf64>;
using vvf80 = std::vector<vf80>;
// pair
using pi8 = std::pair<i8,i8>;
using pi16 = std::pair<i16,i16>;
using pi32 = std::pair<i32,i32>;
using pi64 = std::pair<i64,i64>;
using pi128 = std::pair<i128,i128>;
using pu8 = std::pair<u8,u8>;
using pu16 = std::pair<u16,u16>;
using pu32 = std::pair<u32,u32>;
using pu64 = std::pair<u64,u64>;
using pu128 = std::pair<u128,u128>;
using pf32 = std::pair<f32, f32>;
using pf64 = std::pair<f64, f64>;
using pf80 = std::pair<f80, f80>;
// vector pair
using vpi8 = std::vector<pi8>;
using vpi16 = std::vector<pi16>;
using vpi32 = std::vector<pi32>;
using vpi64 = std::vector<pi64>;
using vpi128 = std::vector<pi128>;
using vpu8 = std::vector<pu8>;
using vpu16 = std::vector<pu16>;
using vpu32 = std::vector<pu32>;
using vpu64 = std::vector<pu64>;
using vpu128 = std::vector<pu128>;
using vpf32 = std::vector<pf32>; 
using vpf64 = std::vector<pf64>; 
using vpf80 = std::vector<pf80>; 
// stack
using si8 = std::stack<i8>;
using si16 = std::stack<i16>;
using si32 = std::stack<i32>;
using si64 = std::stack<i64>;
using si128 = std::stack<i128>;
using su8 = std::stack<u8>;
using su16 = std::stack<u16>;
using su32 = std::stack<u32>;
using su64 = std::stack<u64>;
using su128 = std::stack<u128>;
using sf32 = std::stack<f32>;
using sf64 = std::stack<f64>;
using sf80 = std::stack<f80>;
// queue
using qi8 = std::queue<i8>;
using qi16 = std::queue<i16>;
using qi32 = std::queue<i32>;
using qi64 = std::queue<i64>;
using qi128 = std::queue<i128>;
using qu8 = std::queue<u8>;
using qu16 = std::queue<u16>;
using qu32 = std::queue<u32>;
using qu64 = std::queue<u64>;
using qu128 = std::queue<u128>;
using qf32 = std::queue<f32>;
using qf64 = std::queue<f64>;
using qf80 = std::queue<f80>;
// string
using vs = std::vector<std::string>;
using vvs = std::vector<vs>;
// bool
using vb = std::vector<bool>;
using vvb = std::vector<vb>;

constexpr i32 LIM_SIEVE = 500'000'010;

std::bitset<((LIM_SIEVE + 1) >> 1)> is_prime;
void sieve_of_atkin(i32 lim) {
    assert(lim <= LIM_SIEVE);
    lim = (lim + 1) >> 1;
    for (i32 y = 1, m; (m = (y * y + 36) >> 1) < lim; y += 2) if (y % 3 != 0) for (i32 k = 0; m < lim; m += (k += 36) + 18) is_prime.flip(m);
    for (i32 x = 1, m; (m = (4 * x * x + 1) >> 1) < lim; ++x) if (x % 3 != 0) for (i32 k = 0; m < lim; m += (k += 4)) is_prime.flip(m);
    for (i32 y = 2, m; (m = (y * y + 3) >> 1) < lim; y += 2)  if (y % 3 != 0) for (i32 k = 0; m < lim; m += (k += 12)) is_prime.flip(m);
    for (i32 y = 1, m; (m = ((2 * y + 6) * y + 3) >> 1) < lim; ++y) if (y % 3 != 0) for (i32 k = 6 * y; m < lim; m += (k += 12)) is_prime.flip(m);
    for (i32 p = 5, p2; (p2 = p * p) >> 1 < lim; p += 2) if (is_prime[p >> 1]) for (i32 m = p2 >> 1; m < lim; m += p2) is_prime.reset(m);
    if (1 < lim) is_prime.set(1);
}

i32 anss_len;
i32 anss[1'000'010];

i32 enumerate_primes(i32 n, i32 a = 1, i32 b = 0) {
    sieve_of_atkin(n);
    i32 pi = 0;
    if (2 <= n) if (pi++ % a == b) anss[anss_len++] = 2;
    for (i32 i = 3; i <= n; i += 2) if (is_prime[i >> 1]) if (pi++ % a == b) anss[anss_len++] = i;
    return pi;
}

int main() {
    bool dp[10010];
    dp[0] = true;
    dp[1] = true;
    enumerate_primes(10100);
    for (i64 i = 2; i <= 10000; i++) {
        for (i32 j = 0; j < anss_len; j++) {
            i32 e = anss[j];
            if (i - e < 0) break;
            dp[i] |= !dp[i - e];
        }
    }
    i64 N; scanf("%ld", &N);
    if (dp[N]) printf("Win\n");
    else printf("Lose\n");
    return 0;
}
0