結果

問題 No.7 プライムナンバーゲーム
ユーザー satonakatakumisatonakatakumi
提出日時 2021-08-12 12:53:15
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 12 ms / 5,000 ms
コード長 1,701 bytes
コンパイル時間 2,236 ms
コンパイル使用メモリ 201,616 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-01 16:44:53
合計ジャッジ時間 2,963 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 12 ms
5,248 KB
testcase_03 AC 3 ms
5,248 KB
testcase_04 AC 2 ms
5,248 KB
testcase_05 AC 2 ms
5,248 KB
testcase_06 AC 5 ms
5,248 KB
testcase_07 AC 4 ms
5,248 KB
testcase_08 AC 3 ms
5,248 KB
testcase_09 AC 6 ms
5,248 KB
testcase_10 AC 2 ms
5,248 KB
testcase_11 AC 4 ms
5,248 KB
testcase_12 AC 9 ms
5,248 KB
testcase_13 AC 8 ms
5,248 KB
testcase_14 AC 10 ms
5,248 KB
testcase_15 AC 10 ms
5,248 KB
testcase_16 AC 9 ms
5,248 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using i32 = std::int32_t;
using i64 = std::int64_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;

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[10011];
  dp[0] = true;
  dp[1] = true;
  i32 N; scanf("%d", &N);
  enumerate_primes(N);
  for (i32 i = 2; i <= N; i++) {
    bool x = false;
    for (i32 j = 0; j < anss_len; j++) {
      i32 e = anss[j];
      if (e > i) break;
      x |= !dp[i - e];
    }
    dp[i] = x;
  }
  if (dp[N]) printf("Win\n");
  else printf("Lose\n");
}
0