Mlxa

FUN lazy arrays

Dec 4th, 2017
92
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <map>
  4. #include <cmath>
  5. #include <cassert>
  6. using namespace std;
  7.  
  8. typedef long long ll;
  9. typedef long double ld;
  10. #define De cerr<<
  11. #define W cout <<
  12. #define R cin >>
  13. const ll INF(1e9);
  14.  
  15. template <class T> void
  16. multiass(T& a, T& b, T c, T d)
  17. {    a = c, b = d;  }
  18.  
  19. template <class data>
  20. class Lazy
  21. {   /* arr[K + IND * K]: [ (null) # # ] [ 1 # # ] [ 2 # # ] <- IND = 2; INS = 0; K = 3; (K != sqrt(IND) just for ex.)
  22.     Index:                   0    1 2     3 4 5     6 7 8
  23.     Pred:                    6    * *     0 * *     3 * *
  24.     Index from 1 to IND */
  25.     public:
  26.     const ll mCNT = 1e4, mSIZE = mCNT * getK(mCNT); // mCNT -- max IND; mSIZE - max IND * K;
  27.     const ll EMPTY = -1e5;
  28.     ll IND = 0, INS = 0, K = 0;
  29.     vector< pair<data, int> > arr;
  30.     /* IND -- number of indexed.
  31.        INS -- number of inserted.
  32.        K = getK(IND) -- number of empty cells after not empty. */
  33.  
  34.     ll getK (ll n) { return max((ll)2, (ll)(sqrt(n))); }
  35.  
  36.     Lazy () {                         W "DEFAULT" << endl;
  37.     }
  38.  
  39.     Lazy (int len){                  W "LENGTH" << endl;
  40.         IND = len, K = getK(len);
  41.         arr.resize(K + IND * K);
  42.         for (int i(0); i < K + IND * K; ++i)    arr[i] = {EMPTY, EMPTY};
  43.  
  44.         for (int i(0); i <= IND * K; i += K)
  45.         {   arr[i].first = 0;
  46.             arr[i].second = i - K;
  47.         }   arr[0].second = IND * K;
  48.     }
  49.  
  50.     data& operator [] (int index) { //W "OPER.[]" << endl;
  51.         assert(0 <= index and index <= IND);
  52.         if (!index) W "You really want null?" << endl;
  53.         return arr[K * index].first;
  54.     }
  55.     data& at (int index) {          W "AT IND." << endl;
  56.         norm();
  57.         return (*this)[index];
  58.     }
  59.  
  60.     void inside () {
  61.         W "--------------------------------[ INSIDE ]--------------------------------" << endl;
  62.         W "IND = " << IND << ";\t" << "INS = " << INS << ";\t" << "K = " <<  K  << ";\n";
  63.         W "\tValues:\t"; for (auto i : arr)                     W " "<<i.first << '\t'; W endl;
  64.         W "\t Index:\t"; for (auto i(0); i < K + IND*K; ++i)    W "["<<i<<"]\t";        W endl;
  65.         W "\t Prevs:\t"; for (auto i : arr)                     W " "<<i.second << '\t';W endl;
  66.         W "--------------------------------[ INSIDE ]--------------------------------" << endl;
  67.     }
  68.     void print () {                   W "PRINT" << endl;
  69.         for (int i(1); i <= IND; ++i)
  70.             W (*this)[i] << ' ';
  71.         W endl;
  72.     }
  73.     void norm () {                    W "NORM" << endl;
  74.         int old = IND * K + K;
  75.         IND += INS; INS = 0; K = getK(IND);
  76.         int cut(arr[0].second), paste(K * IND), prev(0);
  77.         arr.resize(IND * K + K);
  78.         for (int i(old); i < arr.size(); ++i)   arr[i] = {EMPTY, EMPTY};
  79.  
  80.         while (cut)
  81.         {   //W cut << ' ' << paste << ' ' << prev << endl;
  82.             assert(cut <= paste);
  83.             if (cut < paste)
  84.                 assert(arr[paste].second == EMPTY);
  85.             /*--------------------------------*/
  86.             swap(arr[cut], arr[paste]);
  87.             arr[prev].second = paste;
  88.             /*--------------------------------*/
  89.             cut = arr[paste].second;
  90.             prev = paste;
  91.             paste -= K;
  92.             /*--------------------------------*/
  93.         }
  94.     }
  95.  
  96.     void ins (int after, data X) {    W "INSERT after " << after << " " << X << endl;
  97.         assert(0 <= after && after <= IND);
  98.         int ind = after * K;
  99.         if (arr[ind + K - 1].second != EMPTY)   norm();
  100.  
  101.         for (int dx(1); dx < K; ++dx)
  102.         {
  103.             if (arr[ind + dx].second == EMPTY)
  104.             {
  105.                 int next( (ind + K) % (IND*K + K) );
  106.                 arr[ind + dx] = {X, arr[next].second};
  107.                 arr[next].second = ind + dx;
  108.                 W "INSERTED TO " << ind + dx << endl;
  109.             }
  110.         }       ++INS;
  111.     }
  112.  
  113.     void del (int index) {
  114.     }
  115. };
  116.  
  117. int main ()
  118. {   // Add resize
  119.     Lazy<int> L(0);
  120.     char c; int a, b;
  121.     while (cin >> c)
  122.     {
  123.         switch(c)
  124.         {
  125.             case 'p': L.print(); break;
  126.             case 's': L.inside(); break;
  127.             case 'i': cin >> a >> b; L.ins(a, b); break;
  128.             case 'n': L.norm();
  129.         }
  130.     }
  131.     return 0;
  132. }
Add Comment
Please, Sign In to add comment