結果
問題 | No.7 プライムナンバーゲーム |
ユーザー |
|
提出日時 | 2019-04-12 17:00:03 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 4 ms / 5,000 ms |
コード長 | 1,625 bytes |
コンパイル時間 | 825 ms |
コンパイル使用メモリ | 89,484 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-01 16:19:09 |
合計ジャッジ時間 | 1,516 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 17 |
ソースコード
#include <assert.h> #include <ctype.h> #include <float.h> #include <limits.h> #include <math.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <sys/types.h> #include <algorithm> #include <bitset> #include <complex> #include <iostream> #include <list> #include <map> #include <numeric> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <unordered_map> #include <unordered_set> #include <vector> using namespace std; #define SZ(a) (int)(a).size() #define FOR(i,a,b) for (int i=(a); i<=(b); ++i) #define REP(i,n) for (int i=0; i<(n); ++i) #define ALL(c) c.begin(), c.end() #define CLR(c,n) memset(c, n, sizeof(c)) #define MCPY(d, s) memcpy(d, s, sizeof(d)) #define TR(it, c) for (auto it = c.begin();it != c.end(); ++it) #define CONTAIN(it, c) (c.find(it) != c.end()) typedef vector<int> VI; typedef pair<int, int> PII; template <class T> void checkmin(T &a, T b) { if (b<a) a=b; } template <class T> void checkmax(T &a, T b) { if (b>a) a=b; } typedef long long LL; const int INF=0x3F3F3F3F; const int N=10000; bool win[N+1], pp[N+1]; int p[N], np; void init() { pp[0] = pp[1] = true; for (int i = 2; i * i <= N; ++i) { if (pp[i]) continue; for (int j = i * i; j <= N; j += i) pp[j] = true; } FOR(i, 2, N) if (!pp[i]) p[np++] = i; win[0] = win[1] = true; FOR(n, 2, N) { REP(i, np) { if (p[i] > n) break; if (!win[n-p[i]]) { win[n] = true; break; } } } } int main(int argc, char *argv[]) { init(); int n; string ans[2] = {"Lose", "Win"}; while (cin >> n) cout << ans[win[n]] << endl; }