Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // TEMPLATE {{{
- #include <bits/stdc++.h>
- using namespace std;
- #ifndef LOCAL
- #define OJ 1
- #else
- #define OJ 0
- #endif
- #define endl '\n'
- #define TIMESTAMP merr << "Execution time: " << (double)clock()/CLOCKS_PER_SEC << " s.\n"
- class C_ {}; template <typename T> C_& operator <<(C_& __m, const T& __s) { if (!OJ) cerr << "\E[91m" << __s << "\E[0m"; return __m; }
- C_ merr;
- struct __s { __s() { if (OJ) { ios_base::Init i; cin.sync_with_stdio(0); cin.tie(0); } } ~__s(){ TIMESTAMP; } } __S;
- /// END OF TEMPLATE }}}
- #define size_t unsigned long long
- const size_t MAX_PRECALC = 10000;
- vector<tuple<size_t,size_t,size_t>> PRE(MAX_PRECALC);
- void try_relax(tuple<size_t,size_t,size_t> t) {
- size_t sum = get<0>(t) + get<1>(t) + get<2>(t);
- if (sum > MAX_PRECALC) return;
- if (get<0>(PRE[sum]) > 0) return;
- PRE[sum] = t;
- }
- void precalc() {
- vector<size_t> tri;
- for (size_t i = 1; i < MAX_PRECALC; i++) {
- size_t t = i*(i-1)/2;
- if (t <= MAX_PRECALC) tri.push_back(t);
- }
- for (size_t i = 0; i < tri.size(); i++) {
- size_t a = tri[i];
- try_relax(make_tuple(a, 0, 0));
- for (size_t j = i; j < tri.size(); j++) {
- size_t b = tri[j];
- try_relax(make_tuple(a, b, 0));
- for (size_t k = j; k < tri.size(); k++) {
- size_t c = tri[k];
- try_relax(make_tuple(a, b, c));
- }
- }
- }
- }
- size_t find(size_t x) {
- if (x == 0) return 0;
- size_t res = (size_t)sqrt(x)/2.0;
- while ((res+999)*(res+1000)/2 <= x) res += 1000;
- while (res*(res+1)/2 <= x) res++;
- return res;
- }
- vector<size_t> solve(size_t x) {
- size_t x1 = find(x);
- x1 = x1*(x1-1)/2;
- size_t x2 = find(x-x1);
- x2 = x2*(x2-1)/2;
- size_t x3 = find(x-x1-x2);
- x3 = x3*(x3-1)/2;
- auto t = PRE[x-x1-x2-x3];
- vector<size_t> res;
- res.push_back(find(x1));
- res.push_back(find(x2));
- res.push_back(find(x3));
- res.push_back(find(get<0>(t)));
- res.push_back(find(get<1>(t)));
- res.push_back(find(get<2>(t)));
- return res;
- }
- int main(void) {
- precalc();
- TIMESTAMP;
- size_t n;
- cin >> n;
- auto x = solve(n-1);
- cout << x.size() << endl;
- for (auto xx : x) {
- cout << xx+!xx << " ";
- }
- cout << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment