結果
問題 | No.7 プライムナンバーゲーム |
ユーザー |
![]() |
提出日時 | 2016-12-25 01:27:50 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 811 bytes |
コンパイル時間 | 1,503 ms |
コンパイル使用メモリ | 166,812 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-12-15 06:41:25 |
合計ジャッジ時間 | 4,158 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 14 WA * 3 |
ソースコード
#include <bits/stdc++.h> using namespace std; int N,M; int P[10010]; void prime(int N){ for(int i= N ; i>=2; i--){ bool flag = true; for( int j = 2; j * j <= i; j++){ if( i % j == 0 ){ flag = false; break; } } if(flag) P[M++]=i; } } bool dfs( const int T, const int N){ if( N <= 1) return T^1; int low = 0, high= M; while(high-low>1){ const int mid=(low+high)/2; if(P[mid] > N) low=mid; else high=mid; } int i = high; while(i < M ){ int x = P[i++]; if(T^dfs(T^1, N - x )) return T^1; } return T; } int main(){ scanf("%d",&N); prime( N ); puts(dfs(0, N)? "Win" : "Lose" ); return 0; }