結果

問題 No.7 プライムナンバーゲーム
ユーザー 久我山菜々久我山菜々
提出日時 2018-09-30 17:26:19
言語 C++17
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 7 ms / 5,000 ms
コード長 941 bytes
コンパイル時間 1,006 ms
コンパイル使用メモリ 103,400 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-04-09 04:31:58
合計ジャッジ時間 1,731 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

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