結果
問題 | No.680 作れる数 |
ユーザー |
|
提出日時 | 2018-04-27 23:45:25 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 1,335 bytes |
コンパイル時間 | 2,013 ms |
コンパイル使用メモリ | 192,328 KB |
最終ジャッジ日時 | 2025-01-05 10:26:20 |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 20 |
ソースコード
#include <bits/stdc++.h> #define show(x) cerr << #x << " = " << x << endl using namespace std; using ll = long long; using ld = long double; constexpr ll MOD = 1000000007LL; template <typename T> constexpr T INF = numeric_limits<T>::max() / 10; template <typename Functor> struct fix_type { Functor functor; template <typename... Args> decltype(auto) operator()(Args&&... args) const& { return functor(functor, std::forward<Args>(args)...); } }; template <typename Functor> fix_type<typename std::decay<Functor>::type> fix(Functor&& functor) { return {std::forward<Functor>(functor)}; } int main() { ll N; cin >> N; if (N == 0) { cout << "YES" << endl; return 0; } int depth = 0; for (ll minimum = 1; minimum <= N; minimum = 2 * minimum + 1) { depth++; } ll s = 1; ll t = 1; for (int i = 0; i < depth; i++) { ll sum = 0; for (ll j = i + 1, tmp = t * 2; j < depth; j++, tmp = 2 * tmp + 1) { sum += tmp; } if (s + sum == N) { cout << "YES" << endl; return 0; } if (s + sum < N) { s += t * 2 + 1; t = t * 2 + 1; } else { s += t * 2; t = t * 2; } } cout << (s == N ? "YES" : "NO") << endl; return 0; }