結果
問題 | 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 << endlusing 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;}