SHOW:
|
|
- or go back to the newest paste.
| 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 | } |
