結果
問題 | No.7 プライムナンバーゲーム |
ユーザー | plasma_e |
提出日時 | 2017-02-06 21:21:20 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 11 ms / 5,000 ms |
コード長 | 13,828 bytes |
コンパイル時間 | 889 ms |
コンパイル使用メモリ | 102,220 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-01 15:55:13 |
合計ジャッジ時間 | 1,569 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,248 KB |
testcase_02 | AC | 11 ms
5,248 KB |
testcase_03 | AC | 3 ms
5,248 KB |
testcase_04 | AC | 2 ms
5,248 KB |
testcase_05 | AC | 2 ms
5,248 KB |
testcase_06 | AC | 5 ms
5,248 KB |
testcase_07 | AC | 4 ms
5,248 KB |
testcase_08 | AC | 2 ms
5,248 KB |
testcase_09 | AC | 6 ms
5,248 KB |
testcase_10 | AC | 2 ms
5,248 KB |
testcase_11 | AC | 4 ms
5,248 KB |
testcase_12 | AC | 9 ms
5,248 KB |
testcase_13 | AC | 9 ms
5,248 KB |
testcase_14 | AC | 11 ms
5,248 KB |
testcase_15 | AC | 11 ms
5,248 KB |
testcase_16 | AC | 10 ms
5,248 KB |
コンパイルメッセージ
main.cpp:78:101: warning: friend declaration 'constexpr decltype(auto) utility::operator+(const addable<T>&, const addable<T>&)' declares a non-template function [-Wnon-template-friend] 78 | friend constexpr decltype(auto) operator+(addable<T>const& lhs, addable<T>const& rhs); | ^ main.cpp:78:101: note: (if this is not what you intended, make sure the function template has already been declared and add '<>' after the function name here) main.cpp:87:111: warning: friend declaration 'constexpr decltype(auto) utility::operator-(const subtractable<T>&, const subtractable<T>&)' declares a non-template function [-Wnon-template-friend] 87 | friend constexpr decltype(auto) operator-(subtractable<T>const& lhs, subtractable<T>const& rhs); | ^ main.cpp:95:111: warning: friend declaration 'constexpr decltype(auto) utility::operator*(const multipliable<T>&, const multipliable<T>&)' declares a non-template function [-Wnon-template-friend] 95 | friend constexpr decltype(auto) operator*(multipliable<T>const& lhs, multipliable<T>const& rhs); | ^ main.cpp:103:105: warning: friend declaration 'constexpr decltype(auto) utility::operator/(const dividable<T>&, const dividable<T>&)' declares a non-template function [-Wnon-template-friend] 103 | friend constexpr decltype(auto) operator/(dividable<T>const& lhs, dividable<T>const& rhs); | ^
ソースコード
#include<iostream> #include<vector> #include<set> #include<algorithm> #include<queue> #include<functional> #include<numeric> #include<limits> #include<map> #include<bitset> #include<array> #include<random> namespace utility { template<class T>struct addable; template<class T>struct subtractable; template<class T>struct multipliable; template<class T>struct dividable; template<class T,class U>constexpr decltype(auto) operator+(T const& lhs, U const& rhs) { auto x = lhs; x += rhs; return x; } template<class T, class U>constexpr decltype(auto) operator-(T const& lhs, U const& rhs) { auto x = lhs; x -= rhs; return x; } template<class T, class U>constexpr decltype(auto) operator*(T const& lhs, U const& rhs) { auto x = lhs; x *= rhs; return x; } template<class T, class U>constexpr decltype(auto) operator/(T const& lhs, U const& rhs) { auto x = lhs; x /= rhs; return x; } template<class T>struct equality_comparable { constexpr decltype(auto) operator!=(equality_comparable<T>const& rhs)const { return !(static_cast<T const&>(*this) == static_cast<T const&>(rhs)); } }; template<class T>struct less_than_comparable { constexpr decltype(auto)operator<(equality_comparable<T>const& rhs)const { return static_cast<T const&>(*this) < static_cast<T const&>(rhs); } constexpr decltype(auto)operator>(T const& rhs)const { return rhs < *this; } constexpr decltype(auto)operator<=(T const& rhs)const { return !(rhs < *this); } constexpr decltype(auto)operator>=(T const& rhs)const { return !(*this < rhs); } }; template<class T>struct addable { constexpr decltype(auto) operator+=(addable<T>const& rhs) { return static_cast<T const&>(*this) += static_cast<T const&>(rhs); } friend constexpr decltype(auto) operator+(addable<T>const& lhs, addable<T>const& rhs); }; template<class T>struct subtractable { constexpr decltype(auto) operator-=(subtractable<T>const& rhs) { return static_cast<T const&>(*this) -= static_cast<T const&>(rhs); } friend constexpr decltype(auto) operator-(subtractable<T>const& lhs, subtractable<T>const& rhs); }; template<class T>struct multipliable { constexpr decltype(auto) operator*=(multipliable<T>const& rhs) { return static_cast<T const&>(*this) *= static_cast<T const&>(rhs); } friend constexpr decltype(auto) operator*(multipliable<T>const& lhs, multipliable<T>const& rhs); }; template<class T>struct dividable { constexpr decltype(auto) operator/=(dividable<T>const& rhs) { return static_cast<T const&>(*this) /= static_cast<T const&>(rhs); } friend constexpr decltype(auto) operator/(dividable<T>const& lhs, dividable<T>const& rhs); }; struct nullopt_t { }; constexpr nullopt_t nullopt{}; template<class T>class optional:private equality_comparable<optional<T>> { union { T val; nullopt_t null; }; bool flag; public: constexpr optional(nullopt_t n = nullopt) : null(), flag(false) { } constexpr T& operator*() { if (flag) { return val; } throw std::invalid_argument("this optional value has not any value"); } constexpr T const& operator*()const { if (flag) { return val; } throw std::invalid_argument("this optional value has not any value"); } constexpr void reset() { null = nullopt; flag = false; } constexpr operator bool()const { return flag; } template<class... Us>void emplace(Us&&... args) { val = T(std::forward<Us>(args)...); flag = true; } constexpr auto& operator=(T const& v) { val = v; flag = true; return *this; } constexpr auto& operator=(T&& v) { val = v; flag = true; return *this; } constexpr auto& operator=(nullopt_t) { null = nullopt; flag = false; return *this; } constexpr optional(T const& v) :optional() { *this = v; } constexpr optional(T&& v) : optional() { *this = std::move(v); } constexpr bool operator==(optional const& rhs)const { return flag&&rhs.flag ? val == rhs.val : flag == rhs.flag; } optional(optional const&) = default; optional(optional&&) = default; optional& operator=(optional const&) = default; optional& operator=(optional&&) = default; ~optional() = default; }; } namespace math { template<class T>constexpr T pow(T val, std::uint64_t p) { return p == 0 ? T(1) : p == 1 ? val : p == 2 ? val*val : p % 2 == 0 ? pow(pow(val, p / 2), 2) : pow(pow(val, p / 2), 2)*val; } template<class T,class U>constexpr int ilog(T val, U base) { T v(1); for (int i{};;++i) { if (val <= v) { return i; } v *= base; } } template<std::uint64_t Mod>class mod_number: private utility::equality_comparable<mod_number<Mod>>, private utility::addable<mod_number<Mod>>, private utility::subtractable<mod_number<Mod>>, private utility::multipliable<mod_number<Mod>>, private utility::dividable<mod_number<Mod>> { std::uint64_t value; public: mod_number(std::uint64_t v = 0) :value(v%Mod) { } mod_number(int v) :value(v%Mod) { } mod_number(std::int64_t v) :value(v%Mod) { } mod_number(std::uint32_t v) :value(v%Mod) { } bool operator==(mod_number const& rhs) { return value == rhs.value; } auto& operator+=(mod_number const& rhs) { value += rhs.value; value %= Mod; return *this; } auto& operator-=(mod_number const& rhs) { value += Mod - rhs.value; value %= Mod; return *this; } auto& operator*=(mod_number const& rhs) { value *= rhs.value; value %= Mod; return *this; } auto& operator/=(mod_number const& rhs) { return operator*=(pow(rhs, Mod - 2)); } }; constexpr int bitcount(unsigned int x) { x = (x & 0x55555555) + ((x & 0xAAAAAAAA) >> 1); x = (x & 0x33333333) + ((x & 0xCCCCCCCC) >> 2); x = (x & 0x0F0F0F0F) + ((x & 0xF0F0F0F0) >> 4); x = (x & 0x00FF00FF) + ((x & 0xFF00FF00) >> 8); x = (x & 0x0000FFFF) + ((x & 0xFFFF0000) >> 16); return static_cast<int>(x); } constexpr int bitcount(unsigned long long x) { x = (x & 0b0101010101010101010101010101010101010101010101010101010101010101) + ((x & 0b1010101010101010101010101010101010101010101010101010101010101010) >> 1); x = (x & 0b0011001100110011001100110011001100110011001100110011001100110011) + ((x & 0b1100110011001100110011001100110011001100110011001100110011001100) >> 2); x = (x & 0b0000111100001111000011110000111100001111000011110000111100001111) + ((x & 0b1111000011110000111100001111000011110000111100001111000011110000) >> 4); x = (x & 0b0000000011111111000000001111111100000000111111110000000011111111) + ((x & 0b1111111100000000111111110000000011111111000000001111111100000000) >> 8); x = (x & 0b0000000000000000111111111111111100000000000000001111111111111111) + ((x & 0b1111111111111111000000000000000011111111111111110000000000000000) >> 16); x = (x & 0b0000000000000000000000000000000011111111111111111111111111111111) + ((x & 0b1111111111111111111111111111111100000000000000000000000000000000) >> 32); return static_cast<int>(x); } constexpr int bitcount(int x) { return bitcount(static_cast<unsigned int>(x)); } constexpr int bitcount(long long x) { return bitcount(static_cast<unsigned long long>(x)); } constexpr auto infinity = utility::nullopt; template<class T>class infable : private utility::addable<T>, private utility::subtractable<T>, private utility::multipliable<T>, private utility::dividable<T>, private utility::equality_comparable<T>, private utility::less_than_comparable<T> { utility::optional<T> val; public: constexpr infable(T v = T()) :val(v) { } constexpr infable(utility::nullopt_t) : val() { } constexpr T const& get()const { return *val; } constexpr bool operator<(infable<T>const& rhs)const { if (val&&rhs.val) { return *val < rhs.get(); } else if (val && !rhs.val) { return true; } else { return false; } } constexpr bool operator==(infable<T>const& rhs)const { return val == rhs.val; } constexpr decltype(auto) operator+=(infable<T>const& rhs) { if (val) { if (rhs.val) { *val += rhs.get(); } else { val = infinity; } } return *this; } constexpr decltype(auto) operator-=(infable<T>const& rhs) { if (val) { if (rhs.val) { *val -= rhs.get(); } else { val = infinity; } } return *this; } constexpr decltype(auto) operator*=(infable<T>const& rhs) { if (val) { if (rhs.val) { *val *= rhs.get(); } else { val = infinity; } } return *this; } constexpr decltype(auto) operator/=(infable<T>const& rhs) { if (val) { if (rhs.val) { *val /= rhs.get(); } else { val = infinity; } } return *this; } }; } namespace container { namespace detail { template<class T, std::size_t Depth>struct tree_array { std::array<T, (1 << (Depth + 1)) - 1> ar; constexpr T& operator()(std::size_t index, std::size_t depth) { return ar[(1ull << depth) + index - 1]; } constexpr T const& operator()(std::size_t index, std::size_t depth)const { return ar[(1ull << depth) + index - 1]; } }; } template<class T, std::size_t Size = 1 << 13>class addtree { std::array<T, 2 * Size - 1> data; T get(std::size_t left, std::size_t right, std::size_t i, std::size_t l, std::size_t r) { if (r <= left || right <= l) return T(); if (left <= l&&r <= right) { return data[i]; } else { return get(left, right, 2 * i + 1, l, (l + r) / 2) + get(left, right, 2 * i + 2, (l + r) / 2, r); } } public: addtree() :data{} { } void change(T const& val, std::size_t index) { T from = data[index + Size - 1]; for (std::size_t i = 1, c = math::ilog(Size, 2);i <= Size;(i <<= 1), --c) { data[i + (index >> c) - 1] -= from; data[i + (index >> c) - 1] += val; } } auto begin()const { return std::next(data.begin(), Size - 1); } auto end()const { return data.end(); } T get(std::size_t left, std::size_t right) { return left > right ? T() : get(left, right + 1, 0, 0, Size); } }; template<class T, std::size_t Depth = 13>class minmaxtree { detail::tree_array<std::pair<T, T>, Depth> data; T min(std::size_t left, std::size_t right, std::size_t L, std::size_t R, std::size_t depth)const { if (right <= L || R <= left) { return std::numeric_limits<T>::max(); } else if (left <= L&&R <= right) { return data(L >> (Depth - depth), depth).first; } else { return std::min( min(left, right, L, (L + R) / 2, depth + 1), min(left, right, (L + R) / 2, R, depth + 1)); } } T max(std::size_t left, std::size_t right, std::size_t L, std::size_t R, std::size_t depth)const { if (right <= L || R <= left) { return std::numeric_limits<T>::min(); } else if (left <= L&&R <= right) { return data(L >> (Depth - depth), depth).second; } else { return std::max( max(left, right, L, (L + R) / 2, depth + 1), max(left, right, (L + R) / 2, R, depth + 1)); } } public: void change(T const& val, std::size_t index) { data(index, Depth).first = val; data(index, Depth).second = val; for (int i = 1;i <= Depth;++i) { data(index >> i, Depth - i).first = std::min( data((index >> i) << 1, Depth - i + 1).first, data(((index >> i) << 1) + 1, Depth - i + 1).first); data(index >> i, Depth - i).second = std::max( data((index >> i) << 1, Depth - i + 1).second, data(((index >> i) << 1) + 1, Depth - i + 1).second); } } T min(std::size_t left, std::size_t right)const { return right < left ? std::numeric_limits<T>::max() : min(left, right + 1, 0, 1 << Depth, 0); } T max(std::size_t left, std::size_t right)const { return right < left ? std::numeric_limits<T>::min() : max(left, right + 1, 0, 1 << Depth, 0); } minmaxtree() :data{} { } }; template<class T>using dijkstra_queue = std::priority_queue<T, std::vector<T>, std::greater<>>; } namespace algorithm { template<class RandomAccessRange>void sort(RandomAccessRange& range) { std::sort(std::begin(range), std::end(range)); } template<class T, std::size_t I>void sort(T(&range)[I]) { std::sort(std::begin(range), std::end(range)); } } void Main(); int main() { std::ios::sync_with_stdio(false); Main(); } //撣 int check(int j, std::vector<int> const& primes) { static std::vector<int> vec(j + 1, -1); if (vec[j] != -1) { return vec[j]; } if (j < 2) { return 1; } for (auto p : primes) { if (p > j) { break; } if (check(j - p, primes) == 0) { vec[j] = 1; return 1; } } vec[j] = 0; return 0; } void Main() { int N; std::cin >> N; std::vector<int> primes = { 2 }; for (int i = 3;i <= N;i += 2) { for (auto p : primes) { if (i%p == 0) { goto next; } } primes.emplace_back(i); next:; } if (check(N, primes)) { std::cout << "Win" << std::endl; } else { std::cout << "Lose" << std::endl; } }