結果
問題 | No.7 プライムナンバーゲーム |
ユーザー | 佐藤淳平 |
提出日時 | 2019-09-11 23:45:08 |
言語 | C++11 (gcc 11.4.0) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 8,839 bytes |
コンパイル時間 | 1,745 ms |
コンパイル使用メモリ | 172,700 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-02 16:55:25 |
合計ジャッジ時間 | 2,222 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 2 ms
5,376 KB |
testcase_05 | AC | 1 ms
5,376 KB |
testcase_06 | AC | 2 ms
5,376 KB |
testcase_07 | AC | 1 ms
5,376 KB |
testcase_08 | AC | 2 ms
5,376 KB |
testcase_09 | AC | 2 ms
5,376 KB |
testcase_10 | AC | 2 ms
5,376 KB |
testcase_11 | AC | 2 ms
5,376 KB |
testcase_12 | WA | - |
testcase_13 | AC | 2 ms
5,376 KB |
testcase_14 | WA | - |
testcase_15 | AC | 2 ms
5,376 KB |
testcase_16 | AC | 2 ms
5,376 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; using i8 = int8_t; using i16 = int16_t; using i32 = int32_t; using i64 = int64_t; using u8 = uint8_t; using u16 = uint16_t; using u32 = uint32_t; using u64 = uint64_t; using f32 = float; using f64 = double; using vi32 = std::vector<i32>; using vu32 = std::vector<u32>; using vf32 = std::vector<f32>; using vi64 = std::vector<i64>; using vu64 = std::vector<u64>; using vf64 = std::vector<f64>; using vvi32 = std::vector<vi32>; using vvu32 = std::vector<vu32>; using vvf32 = std::vector<vf32>; using vvi64 = std::vector<vi64>; using vvu64 = std::vector<vu64>; using vvf64 = std::vector<vf64>; using pi32 = std::pair<i32,i32>; using pu32 = std::pair<u32,u32>; using pf32 = std::pair<f32,f32>; using pi64 = std::pair<i64,i64>; using pu64 = std::pair<u64,u64>; using pf64 = std::pair<f64,f64>; #define ALL(obj) (obj).begin(),(obj).end() #define RALL(obj) ((obj).rbegin(),(obj).rend()) #define SZ(obj) ((i32)(obj).size()) #define EACH(it,o) for(auto it=(o).begin();it!=(o).end();++it) #define IN(l,n,r) ((l)<=(n) && (n)<(r)) #define UNIQUE(obj) (obj).erase(std::unique(ALL(obj)),(obj).end()) #define CLR(ar,val) memset(ar, val, sizeof(ar)) #define FOR(i,a,b) for(i32 i=(i32)(a); i<(i32)(b); i++) #define RFOR(i,a,b) for(i32 i=(i32)(b)-1;i>=(i32)(a);--i) #define REP(i,n) FOR(i,0,n) #define RREP(i,n) RFOR(i,0,n) #define PRINT(n) cout << (n) <<"\n"; #define cauto const auto& #define mp make_pair #define pb push_back const i32 INF = 0x3F3F3F3F; const i64 INF64 = 0x3F3F3F3F3F3F3F3F; const f64 EPS = 1e-8; const i32 MOD = 1000000007; static const f64 PI = 3.1415926535897932; static const f64 NAPIER = 2.7182818284590452; const char alphabetl[26] = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'}; const char alphabetu[26] = {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z'}; i32 dx[4] = {1, 0, -1, 0}; i32 dy[4] = {0, 1, 0, -1}; template<typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); } template<typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); } i64 BIT_COUNT_ONES(i64 x) { return __builtin_popcountll(x); } i64 BIT_COUNT_ZEROS(i64 x) { return 64 - BIT_COUNT_ONES(x); } //gcd(a, b) = a * x + b * y i64 extgcd(i64 a, i64 b, i64 &x, i64 &y) { i64 d = a; if(b != 0) { d = extgcd(b, a % b, y, x); y -= (a / b) * x; } else { x = 1; y = 0; } return d; } std::vector<i64> convert_base(i64 x, i64 b) { std::vector<i64> ret; i64 t = 1, k = abs(b); while (x) { ret.emplace_back((x * t) % k); if (ret.back() < 0) ret.back() += k; x -= ret.back() * t; x /= k; t *= b / k; } if (ret.empty()) ret.emplace_back(0); std::reverse(ALL(ret)); return ret; } std::vector<bool> prime_table(i32 n) { std::vector<bool> prime(n + 1, true); if(n >= 0) prime[0] = false; if(n >= 1) prime[1] = false; for(i32 i = 2; i * i <= n; i++) { if(!prime[i]) continue; for(i32 j = i + i; j <= n; j += i) { prime[j] = false; } } return prime; } //a ^ x === b (mod p) i64 mod_log(i64 a, i64 b, i64 p) { i64 ok = p, ng = -1; while(ok - ng > 1) { auto mid = (ok + ng) / 2; if (mid * mid >= p) ok = mid; else ng = mid; } std::unordered_map<i64, i64> baby; baby.reserve(ok); i64 factor = 1; for (i64 i = 0, e = b; i < ok; i++) { baby[e] = i; (factor *= a) %= p; (e *= a) %= p; } for (i64 i = 1, e = factor; i <= ok; i++) { auto it = baby.find(e); if (it != baby.end()) return i * ok - it -> second; (e *= factor) %= p; } return -1; } //input pair tuple vector template<typename T1,typename T2> std::istream& operator >> (std::istream& is,std::pair<T1,T2>& p){is>>p.first>>p.second;return is;} template<typename T1> std::istream& operator >> (std::istream& is,std::tuple<T1>& t){is >> std::get<0>(t);return is;} template<typename T1,typename T2> std::istream& operator >> (std::istream& is,std::tuple<T1,T2>& t){is >> std::get<0>(t) >> std::get<1>(t);return is;} template<typename T1,typename T2,typename T3> std::istream& operator >> (std::istream& is,std::tuple<T1,T2,T3>& t){is >>std::get<0>(t)>>std::get<1>(t)>>std::get<2>(t);return is;} template<typename T1,typename T2,typename T3,typename T4> std::istream& operator >> (std::istream& is,std::tuple<T1,T2,T3,T4>& t){is >> std::get<0>(t)>>std::get<1>(t)>>std::get<2>(t)>>std::get<3>(t);return is;} template<typename T1,typename T2,typename T3,typename T4,typename T5> std::istream& operator >> (std::istream& is, const std::tuple<T1,T2,T3,T4,T5>& t){is >> std::get<0>(t) >> std::get<1>(t) >> std::get<2>(t) >> std::get<3>(t) >> std::get<4>(t);return is;} template<typename T1,typename T2,typename T3,typename T4,typename T5,typename T6> std::istream& operator >> (std::istream& is, const std::tuple<T1,T2,T3,T4,T5,T6>& t){is >> std::get<0>(t) >> std::get<1>(t) >> std::get<2>(t) >> std::get<3>(t) >> std::get<4>(t) >> std::get<5>(t);return is;} template<typename T1,typename T2,typename T3,typename T4,typename T5,typename T6,typename T7> std::istream& operator >> (std::istream& is, const std::tuple<T1,T2,T3,T4,T5,T6,T7>& t){is >> std::get<0>(t) >> std::get<1>(t) >> std::get<2>(t) >> std::get<3>(t) >> std::get<4>(t) >> std::get<5>(t) >> std::get<6>(t);return is;} template<typename T> std::istream& operator >> (std::istream& is,std::vector<T>& as){REP(i,SZ(as))is >>as[i];return is;} //output set pair map tuple vector template<typename T> std::ostream& operator << (std::ostream& os, const std::set<T>& ss){for(auto a:ss){if(a!=ss.begin())os<<" "; os<<a;}return os;} template<typename T1,typename T2> std::ostream& operator << (std::ostream& os, const std::pair<T1,T2>& p){os<<p.first<<" "<<p.second;return os;} template<typename K,typename V> std::ostream& operator << (std::ostream& os, const std::map<K,V>& m){bool isF=true;for(auto& p:m){if(!isF)os<<std::endl;os<<p;isF=false;}return os;} template<typename T1> std::ostream& operator << (std::ostream& os, const std::tuple<T1>& t){os << std::get<0>(t);return os;} template<typename T1,typename T2> std::ostream& operator << (std::ostream& os, const std::tuple<T1,T2>& t){os << std::get<0>(t)<<" "<<std::get<1>(t);return os;} template<typename T1,typename T2,typename T3> std::ostream& operator << (std::ostream& os, const std::tuple<T1,T2,T3>& t){os << std::get<0>(t)<<" "<<std::get<1>(t)<<" "<<std::get<2>(t);return os;} template<typename T1,typename T2,typename T3,typename T4> std::ostream& operator << (std::ostream& os, const std::tuple<T1,T2,T3,T4>& t){os << std::get<0>(t)<<" "<<std::get<1>(t)<<" "<<std::get<2>(t)<<" "<<std::get<3>(t);return os;} template<typename T1,typename T2,typename T3,typename T4,typename T5> std::ostream& operator << (std::ostream& os, const std::tuple<T1,T2,T3,T4,T5>& t){os << std::get<0>(t)<<" "<<std::get<1>(t)<<" "<<std::get<2>(t)<<" "<<std::get<3>(t)<<" "<<std::get<4>(t);return os;} template<typename T1,typename T2,typename T3,typename T4,typename T5,typename T6> std::ostream& operator << (std::ostream& os, const std::tuple<T1,T2,T3,T4,T5,T6>& t){os << std::get<0>(t)<<" "<<std::get<1>(t)<<" "<<std::get<2>(t)<<" "<<std::get<3>(t)<<" "<<std::get<4>(t)<<" "<<std::get<5>(t);return os;} template<typename T1,typename T2,typename T3,typename T4,typename T5,typename T6,typename T7> std::ostream& operator << (std::ostream& os, const std::tuple<T1,T2,T3,T4,T5,T6,T7>& t){os << std::get<0>(t)<<" "<<std::get<1>(t)<<" "<<std::get<2>(t)<<" "<<std::get<3>(t)<<" "<<std::get<4>(t)<<" "<<std::get<5>(t)<<" "<<std::get<6>(t);return os;} template<typename T> std::ostream& operator << (std::ostream& os, const std::vector<T>& as){REP(i,as.size()){if(i!=0)os<<" "; os<<as[i];}return os;} template<typename T> std::ostream& operator << (std::ostream& os, const std::vector<std::vector<T>>& as){REP(i,SZ(as)){if(i!=0)os<<std::endl; os<<as[i];}return os;} void Main(); int main() {std::cin.tie(nullptr);std::ios::sync_with_stdio(false);std::cout<<std::fixed<<std::setprecision(15);Main();return 0;} void Main() { i32 N; cin >> N; bool dp[10010]; dp[0] = dp[1] = true; auto prime = prime_table(N); vi32 P; for (i32 i = 2; i <= N; i++) if (prime[i]) P.pb(i); for (i32 i = 2; i <= N; i++) { if (!dp[i]) { for (i32 j = 0; j < SZ(P); j++) { if (i + P[j] > N) break; dp[i+P[j]] = true; } } } if (dp[N]) cout << "Win" << endl; else cout << "Lose" << endl; }