結果

問題 No.7 プライムナンバーゲーム
ユーザー satonakatakumisatonakatakumi
提出日時 2021-08-11 15:38:42
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 5,693 bytes
コンパイル時間 2,208 ms
コンパイル使用メモリ 203,452 KB
実行使用メモリ 36,392 KB
最終ジャッジ日時 2024-09-25 02:26:38
合計ジャッジ時間 3,206 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 29 ms
20,608 KB
testcase_01 AC 30 ms
20,608 KB
testcase_02 AC 29 ms
20,608 KB
testcase_03 AC 28 ms
20,608 KB
testcase_04 AC 28 ms
36,392 KB
testcase_05 AC 29 ms
20,608 KB
testcase_06 AC 28 ms
20,608 KB
testcase_07 AC 29 ms
20,608 KB
testcase_08 AC 28 ms
20,736 KB
testcase_09 WA -
testcase_10 AC 28 ms
20,736 KB
testcase_11 AC 29 ms
20,608 KB
testcase_12 AC 29 ms
20,736 KB
testcase_13 AC 29 ms
20,608 KB
testcase_14 WA -
testcase_15 WA -
testcase_16 AC 28 ms
20,736 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>;

#define MAX 300010

u32 s, prime_cnt, sq[65536], sp[65536], primes[26500010];
u64 wheel[15015], is_composite[8192], mask[12][62][8192];

const u32 block_size = 1 << 19;

inline void setbit(u64* ar, u32 bit) { ar[bit >> 6] |= (1ULL << (bit & 63)); }
inline u32 get_idx(u32 i, u32 j) {
    if (sq[j] > i) return (sq[j] - i) >> 1;
    u32 x = sp[j] - i % sp[j];
    if (!(x & 1)) x += sp[j];
    return x >> 1;
}
void small_sieve() {
    for (u32 i = 2; i * i < 65536; i++) for (u32 j = i * i; j < 65536 && !sp[i]; j += i) sp[j] = 1;
    for (u32 i = 2; i < 65536; i++) if (!sp[i]) sp[s] = i, sq[s++] = i * i;
}
void process_block(u32 i) {
    u32 j, k, l, d, m, x, lim = i + block_size, idx = i % 15015, chunk = 0;
    idx = (idx + ((idx * 105) & 127) * 15015) >> 7;
    for (j = 0; (j << 7) < block_size; j += chunk, idx = 0) {
        chunk = std::min(15015 - idx, (block_size >> 7) - j);
        memcpy(is_composite + j, wheel + idx, sizeof(u64) * chunk);
    }
    if (!i) is_composite[0] = (is_composite[0] | 1) & ~110ULL;
    l = block_size >> 1, m = block_size >> 7;
    for (j = 6; j < 18 && i; j++) for (x = get_idx(i, j), k = 0, d = j - 6; k < m; k++) is_composite[k] |= mask[d][x][k];
    for (j = (i == 0) ? 6 : 18; j < s && sq[j] < lim; j++) for (x = get_idx(i, j); x < l; x += sp[j]) setbit(is_composite, x);
}
void populate_primes(u32 i, u32 n) {
    for (u32 j = 0; (j << 7) < block_size; j++) {
        u64 x = ~is_composite[j];
        while (x) {
            u32 p = i + (j << 7) + (__builtin_ctzll(x) << 1) + 1;
            if (p <= n) primes[prime_cnt++] = p;
            x ^= (-x & x);
        }
    }
}
void fast_sieve(u32 n) {
    small_sieve();
    for (u32 i = 1; i <= 5; i++) for (u32 j = i + (i > 3); j < 960960; j += sp[i]) setbit(wheel, j);
    for (u32 i = 6; i <= 17; i++) for (u32 j = 0; j < sp[i]; j++) for (u32 k = j; k < (block_size >> 1); k += sp[i]) setbit(mask[i - 6][j], k);
    if (n >= 2) primes[prime_cnt++] = 2;
    for (u32 i = 0; i <= n; i += block_size) {
        process_block(i);
        populate_primes(i, n);
    }
}
std::vector<u32> enumerate_primes(u32 n, u32 a = 1, u32 b = 0) {
    fast_sieve(n);
    std::vector<u32> res;
    for (u32 u = b; u < prime_cnt; u += a) res.push_back(primes[u]);
    return res;
}


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