結果

問題 No.7 プライムナンバーゲーム
コンテスト
ユーザー 久我山菜々
提出日時 2018-09-30 17:26:19
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 23 ms / 5,000 ms
コード長 941 bytes
コンパイル時間 924 ms
コンパイル使用メモリ 99,688 KB
最終ジャッジ日時 2025-01-06 14:12:40
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
#include<cmath>

int main(int, char**) {
  int n;
  std::cin >> n;

  std::vector<bool> primes(n + 1, true);
  primes[0] = primes[1] = false;
  for(int i{2}; i < std::sqrt(n) + 1; ++i) {
    if(!primes[i]) continue;

    for(int j{i * 2}; j < n + 1; j += i) {
      primes[j] = false;
    }
  }

  std::vector<int> ps;
  for(int i{}; i < n + 1; ++i) {
    if(primes[i]) ps.push_back(i);
  }

  // 2 or 3をもらうと負け。

  std::vector<int> results(n + 1, -1);
  results[2] = results[3] = 0; // 0 まけ 1 かち

  for(int i{4}; i <= n; ++i) {
    bool atta{};
    for(int j{}; j < i; ++j) {
      if(ps[j] > i) break;

      if(results[i - ps[j]] == 0) {
        atta = true;
        break;
      }
    }
    if(atta) {
      results[i] = 1;
    } else {
      results[i] = 0;
    }
  }

  std::cout << (results[n] ? "Win" : "Lose") << std::endl;

  return 0;
}
0