結果

問題 No.7 プライムナンバーゲーム
コンテスト
ユーザー satonakatakumi
提出日時 2021-08-12 12:53:15
言語 C++17
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 9 ms / 5,000 ms
コード長 1,701 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,001 ms
コンパイル使用メモリ 194,888 KB
最終ジャッジ日時 2025-01-23 17:44:13
ジャッジサーバーID
（参考情報） 		judge3 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 17
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:37:15: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   37 |   i32 N; scanf("%d", &N);
      |          ~~~~~^~~~~~~~~~

ソースコード

diff #
raw source code 

#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