結果

問題 No.2479 Sum of Squares
ユーザー rei-artistrei-artist
提出日時 2023-09-23 01:18:57
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 5,590 bytes
コンパイル時間 10,004 ms
コンパイル使用メモリ 348,588 KB
実行使用メモリ 4,380 KB
最終ジャッジ日時 2023-09-23 01:19:09
合計ジャッジ時間 10,334 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 AC 2 ms
4,376 KB
testcase_02 AC 2 ms
4,376 KB
testcase_03 AC 1 ms
4,376 KB
testcase_04 AC 2 ms
4,376 KB
testcase_05 AC 2 ms
4,380 KB
testcase_06 AC 2 ms
4,376 KB
testcase_07 AC 2 ms
4,376 KB
testcase_08 AC 2 ms
4,376 KB
testcase_09 AC 1 ms
4,376 KB
testcase_10 AC 2 ms
4,380 KB
testcase_11 AC 1 ms
4,376 KB
testcase_12 AC 1 ms
4,380 KB
testcase_13 AC 1 ms
4,376 KB
testcase_14 AC 2 ms
4,380 KB
testcase_15 AC 2 ms
4,380 KB
testcase_16 AC 1 ms
4,376 KB
testcase_17 AC 1 ms
4,380 KB
testcase_18 AC 1 ms
4,376 KB
testcase_19 AC 2 ms
4,376 KB
testcase_20 AC 1 ms
4,380 KB
testcase_21 AC 1 ms
4,376 KB
testcase_22 AC 1 ms
4,376 KB
testcase_23 AC 1 ms
4,376 KB
testcase_24 AC 2 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC target("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>

#include <atcoder/all>
using namespace std;
using namespace atcoder;
#ifdef DEBUG
#include "_debug.h"
#else
#define tr(...)
#define trp(a, ...) a
#endif

typedef long long ll;
typedef unsigned long long ull;
template <typename T> using v = vector<T>;
template <typename T> using vv = v<v<T>>;
template <typename T> using vvv = v<vv<T>>;
template <typename T> using vvvv = v<vvv<T>>;

#define LR(i, n) for (int i = 0; i < (n); i++)
#define LR2(i, s, e) for (int i = (s); i < (e); i++)
#define RL(i, n) for (int i = (n)-1; i >= 0; i--)
#define RL2(i, s, e) for (int i = (e)-1; i >= (s); i--)
#define ALL(a) (a).begin(), (a).end()

template <typename, typename = void_t<>> struct has_val : false_type {};
template <typename T>
struct has_val<T, void_t<decltype(declval<T>().val())>> : true_type {};
template <typename T, enable_if_t<has_val<T>::value, nullptr_t> = nullptr>
ostream &operator<<(ostream &out, const T &o) {
  return out << o.val();
}
ostream &operator<<(ostream &out, const string &v) {
  for (auto i = v.cbegin(); i != v.cend(); i++) out << *i;
  return out;
}
template <class T, size_t N>
ostream &operator<<(ostream &out, const array<T, N> &v) {
  for (auto i = v.cbegin(); i != v.cend(); i++)
    out << (i != v.cbegin() ? " " : "") << *i;
  return out;
}
template <template <class...> class C, class... T>
ostream &operator<<(ostream &out, const C<T...> &v) {
  for (auto i = v.cbegin(); i != v.cend(); i++)
    out << (i != v.cbegin() ? " " : "") << *i;
  return out;
}
template <size_t I = 0, typename... Tp>
inline enable_if_t<I == sizeof...(Tp), void> in_tuple(
    istream &in, tuple<Tp...> &t) {}
template <size_t I = 0, typename... Tp>
    inline enable_if_t <
    I<sizeof...(Tp), void> in_tuple(istream &in, tuple<Tp...> &t) {
  in >> get<I>(t);
  in_tuple<I + 1, Tp...>(in, t);
}
template <class... Args> istream &operator>>(istream &in, tuple<Args...> &t) {
  in_tuple(in, t);
  return in;
}
template <class A, class B> istream &operator>>(istream &in, pair<A, B> &o) {
  in >> o.first, in >> o.second;
  return in;
}
template <class T, size_t N> istream &operator>>(istream &in, array<T, N> &v) {
  LR(i, N) in >> v[i];
  return in;
}
template <class T> istream &operator>>(istream &in, vector<T> &v) {
  LR(i, v.size()) in >> v[i];
  return in;
}

template <typename T1, typename T2> T1 div_ceil(T1 x, T2 y) {
  return (x + y - 1) / y;
}
template <typename T1, typename T2> T1 div_floor(T1 x, T2 y) {
  return x / y - (x % y != 0 && (y < 0) != (x < 0));
}
template <typename A, size_t N, typename T>
void fill_array(A (&array)[N], const T &val) {
  std::fill((T *)array, (T *)(array + N), val);
}
template <typename T, typename I, typename S>
void assign(vector<T> &v, const I &val, const S n) {
  v.assign(n, val);
}
template <typename V, typename I, typename S, typename... A>
void assign(vector<V> &vec, const I &val, const S &n, const A... tail) {
  vec.resize(n);
  for (auto &v : vec) assign(v, val, tail...);
}
template <typename T> inline bool chmax(T &a, T b) {
  return ((a < b) ? (a = b, true) : (false));
}
template <typename T> inline bool chmin(T &a, T b) {
  return ((a > b) ? (a = b, true) : (false));
}
template <template <class...> class C, class T> inline T pop_back(C<T> &c) {
  T res = move(c.back());
  c.pop_back();
  return res;
}
template <template <class...> class C, class T> inline T pop_front(C<T> &c) {
  T res = move(c.front());
  c.pop_front();
  return res;
}
void yesno(bool b) { cout << (b ? "Yes" : "No") << endl; }

struct in {
  template <class T> operator T() const {
    T a;
    cin >> a;
    return a;
  }
};
struct vin {
  size_t s1;
  explicit vin(size_t s1) : s1(s1){};
  template <class C> operator v<C>() const {
    v<C> a(s1);
    cin >> a;
    return a;
  }
};
struct vvin {
  size_t s1, s2;
  vvin(size_t s1, size_t s2) : s1(s1), s2(s2){};
  template <class C> operator vv<C>() const {
    vv<C> a(s1, v<C>(s2));
    cin >> a;
    return a;
  }
};

template <int N = 1> struct mkv {
  const v<int> &sizes;
  const optional<any> &value;
  mkv(const v<int> &sizes, const optional<any> &value = nullopt)
      : sizes(sizes), value(value) {}
  template <class C> operator v<C>() {
    int n = sizes[sizes.size() - N];
    if (N == 1) {
      return value.has_value() ? v<C>(n, any_cast<C>(value.value())) : v<C>(n);
    } else {
      return v<C>(n, (C)mkv<N - 1>(sizes, value));
    }
  }
};
template <> struct mkv<0> {
  mkv(const v<int> &sizes, const optional<any> &value = nullopt) {}
  template <class T> operator T() { return T(); }
};

const int INT_INF = 0x3fffffff;
const ll LL_INF = 0x1fffffffffffffffll;
const double EPS = 0.0000001;
int cmp_eps(double x, double y) {
  return (x > y + EPS) ? 1 : (y > x + EPS) ? -1 : 0;
}
using mint = modint998244353;
template <typename T> T find_highest_bound(T ok, T ng, function<bool(T)> f) {
  while (ng != ok) {
    T m = (ng + ok + 1) / 2;
    if (f(m)) {
      ok = m;
    } else {
      ng = m - 1;
    }
  }
  return ok;
}

ll sqrt(ll x) {
  return find_highest_bound<ll>(0, INT_INF, [&](ll a) { return a * a <= x; });
}

struct hiki {
  ll S = in();

  hiki() {}
  void komoru() {
    v<ll> ans;
    while (S > 0) {
      ll sq = sqrt(S);
      ans.push_back(sq * sq);
      S -= sq * sq;
    }
    cout << ans.size() << endl;
    cout << ans << endl;
  }
};

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout << fixed << setprecision(10);
  hiki().komoru();

  return 0;
}

// https://yukicoder.me/problems/no/2479
0