fork download 
  1. // Runs in 0.035 sec
  2.  
  3. #include <cstdint>
  4. #include <iostream>
  5. #include <vector>
  6. #include <algorithm>
  7. #include <iterator>
  8. using namespace std;
  9.  
  10. int main();
  11.  
  12. typedef uint_fast32_t number;
  13. typedef uint_fast32_t sequencelength;
  14.  
  15. class lengthsbase
  16. {
  17.   static const size_t cachesize;
  18.   vector<sequencelength> t;
  19.  
  20.   typedef uint_fast32_t index;
  21.   static number indextonumber(index);
  22.   static index numbertoindex(number);
  23.   static const number maxcachednumber;
  24.  
  25. public:
  26.   lengthsbase();
  27.  
  28.   const sequencelength operator[] (number);
  29.  
  30.   class iterator;
  31.   iterator find(number);
  32. } b;
  33.  
  34. class lengthsbase::iterator:
  35.   public ::iterator<forward_iterator_tag, sequencelength const, void>
  36. {
  37.   friend class lengthsbase;
  38.  
  39.   lengthsbase &b;
  40.   number i;
  41.   iterator(lengthsbase&, number);
  42.  
  43. public:
  44.   iterator &operator=(const iterator&);
  45.   iterator &operator++();
  46.   friend bool operator==(const iterator&, const iterator&);
  47.  
  48.   const sequencelength operator*() const;
  49. };
  50.  
  51. int main()
  52. {
  53.   ios_base::sync_with_stdio(false);
  54.  
  55.   number i, j;
  56.   while(cin >> i >> j)
  57.     cout << i << ' ' << j << ' '
  58.       << *max_element(b.find(min(i,j)), ++b.find(max(i,j)))
  59.       << '\n';
  60.  
  61.   return 0;
  62. }
  63.  
  64. const sequencelength lengthsbase::operator[] (number i)
  65. {
  66.   number next = i%2 == 0 ? i/2 : 3*i+1;
  67.  
  68.   if(i>maxcachednumber)
  69.     return operator[](next)+1;
  70.  
  71.   if(t[numbertoindex(i)] == 0)
  72.     t[numbertoindex(i)] = i == 1 ? 1 : operator[](next) + 1;
  73.  
  74.   return t[numbertoindex(i)];
  75. }
  76.  
  77. lengthsbase::iterator lengthsbase::find(number i)
  78. {
  79.   return iterator(*this, i);
  80. }
  81.  
  82. const size_t lengthsbase::cachesize = 0x100000;
  83.  
  84. const number lengthsbase::maxcachednumber = indextonumber(cachesize-1);
  85.  
  86. lengthsbase::lengthsbase() : t(cachesize, 0) {}
  87.  
  88. number lengthsbase::indextonumber(lengthsbase::index i)
  89. {
  90.   return i+1;
  91. }
  92.  
  93. lengthsbase::index lengthsbase::numbertoindex(number i)
  94. {
  95.   return i-1;
  96. }
  97.  
  98. const sequencelength lengthsbase::iterator::operator *() const
  99. {
  100.   return b[i];
  101. }
  102.  
  103. lengthsbase::iterator::iterator(lengthsbase &b, const number i): b(b), i(i) {}
  104.  
  105. lengthsbase::iterator &lengthsbase::iterator::operator=
  106.   (const lengthsbase::iterator &it)
  107. {
  108.   b=it.b;
  109.   i=it.i;
  110.   return *this;
  111. }
  112.  
  113. lengthsbase::iterator &lengthsbase::iterator::operator ++()
  114. {
  115.   ++i;
  116.   return *this;
  117. }
  118.  
  119. bool operator ==
  120.   (const lengthsbase::iterator &it, const lengthsbase::iterator &jt)
  121. {
  122.   return &(it.b) == &(jt.b) && it.i == jt.i;
  123. }
  124.  
  125. bool operator !=
  126.   (const lengthsbase::iterator &it, const lengthsbase::iterator &jt)
  127. {
  128.   return !(it == jt);
  129. }
Success #stdin #stdout 0s 3280KB
comments (?)
stdin 
1 10
100 200
201 210
900 1000
stdout 
1 10 20
100 200 125
201 210 89
900 1000 174
https://ideone.com/Gzu3KH
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!