Guest User

Untitled

a guest
Dec 19th, 2016
506
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.17 KB | None | 0 0
  1. // TEMPLATE {{{
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. #ifndef LOCAL
  5. #define OJ 1
  6. #else
  7. #define OJ 0
  8. #endif
  9.  
  10. #define endl '\n'
  11. #define TIMESTAMP merr << "Execution time: " << (double)clock()/CLOCKS_PER_SEC << " s.\n"
  12. class C_ {}; template <typename T> C_& operator <<(C_& __m, const T& __s) { if (!OJ) cerr << "\E[91m" << __s << "\E[0m"; return __m; }
  13. C_ merr;
  14.  
  15. struct __s { __s() { if (OJ) { ios_base::Init i; cin.sync_with_stdio(0); cin.tie(0); } } ~__s(){ TIMESTAMP; } } __S;
  16. /// END OF TEMPLATE }}}
  17.  
  18. #define size_t unsigned long long
  19.  
  20. const size_t MAX_PRECALC = 10000;
  21. vector<tuple<size_t,size_t,size_t>> PRE(MAX_PRECALC);
  22.  
  23. void try_relax(tuple<size_t,size_t,size_t> t) {
  24.   size_t sum = get<0>(t) + get<1>(t) + get<2>(t);
  25.   if (sum > MAX_PRECALC) return;
  26.   if (get<0>(PRE[sum]) > 0) return;
  27.   PRE[sum] = t;
  28. }
  29.  
  30. void precalc() {
  31.   vector<size_t> tri;
  32.   for (size_t i = 1; i < MAX_PRECALC; i++) {
  33.     size_t t = i*(i-1)/2;
  34.     if (t <= MAX_PRECALC) tri.push_back(t);
  35.   }
  36.   for (size_t i = 0; i < tri.size(); i++) {
  37.     size_t a = tri[i];
  38.     try_relax(make_tuple(a, 0, 0));
  39.     for (size_t j = i; j < tri.size(); j++) {
  40.       size_t b = tri[j];
  41.       try_relax(make_tuple(a, b, 0));
  42.       for (size_t k = j; k < tri.size(); k++) {
  43.         size_t c = tri[k];
  44.         try_relax(make_tuple(a, b, c));
  45.       }
  46.     }
  47.   }
  48. }
  49.  
  50. size_t find(size_t x) {
  51.   if (x == 0) return 0;
  52.   size_t res = (size_t)sqrt(x)/2.0;
  53.   while ((res+999)*(res+1000)/2 <= x) res += 1000;
  54.   while (res*(res+1)/2 <= x) res++;
  55.   return res;
  56. }
  57.  
  58. vector<size_t> solve(size_t x) {
  59.   size_t x1 = find(x);
  60.   x1 = x1*(x1-1)/2;
  61.   size_t x2 = find(x-x1);
  62.   x2 = x2*(x2-1)/2;
  63.   size_t x3 = find(x-x1-x2);
  64.   x3 = x3*(x3-1)/2;
  65.   auto t = PRE[x-x1-x2-x3];
  66.   vector<size_t> res;
  67.   res.push_back(find(x1));
  68.   res.push_back(find(x2));
  69.   res.push_back(find(x3));
  70.   res.push_back(find(get<0>(t)));
  71.   res.push_back(find(get<1>(t)));
  72.   res.push_back(find(get<2>(t)));
  73.   return res;
  74. }
  75.  
  76. int main(void) {
  77.   precalc();
  78.   TIMESTAMP;
  79.   size_t n;
  80.   cin >> n;
  81.   auto x = solve(n-1);
  82.   cout << x.size() << endl;
  83.   for (auto xx : x) {
  84.     cout << xx+!xx << " ";
  85.   }
  86.   cout << endl;
  87.   return 0;
  88. }
Advertisement
Add Comment
Please, Sign In to add comment