1-ShadowMaster-1

Untitled

Feb 20th, 2022
690
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 21.94 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. template <class T>
  6. class LinkedList{
  7. public:
  8.         virtual void push_back(T val) = 0;
  9.         virtual void push_front(T val) = 0;
  10.         virtual int size() = 0;
  11.         virtual bool isempty() = 0;
  12.         virtual void clear() = 0;
  13.         virtual T back() = 0;
  14.         virtual T front() = 0;
  15.         virtual T pop_front() = 0;
  16.         virtual void pop_back() = 0;
  17.         virtual T get(int index) = 0;
  18. };
  19.  
  20. template<class K>
  21. class Node{
  22. public:
  23.         K value;
  24.         Node* next = nullptr;
  25.         Node* previus = nullptr;
  26.         Node(K value){
  27.                 this->value = value;
  28.         }
  29. };
  30.  
  31. template<class T>
  32. class DoubleLinkedList : public LinkedList<T>{
  33.  
  34. int length = 0;
  35. Node<T>* head = nullptr;
  36. Node<T>* tail = nullptr;
  37.  
  38. public:
  39.         void push_back(T val) override
  40.         {
  41.                 Node<T>* new_val = (new Node<T>(val));
  42.                 if(length == 0){
  43.                         head = new_val;
  44.                         tail = new_val;
  45.                 }else{
  46.                         auto x = head;
  47.                         head = new_val;
  48.                         new_val = x;
  49.                         new_val->next = head;
  50.                         head->previus = new_val;
  51.                 }
  52.                 length++;
  53.         }
  54.  
  55.         void push_front(T val)override
  56.         {
  57.                 auto new_val = new Node<T>(val);
  58.                 if(length == 0){
  59.                         head = new_val;
  60.                         tail = new_val;
  61.                 }else{
  62.                         auto x = tail;
  63.                         tail = new_val;
  64.                         new_val = x;
  65.                         new_val->previus = tail;
  66.                         tail->next = new_val;
  67.                 }
  68.                 length++;
  69.         }
  70.  
  71.         int size() override
  72.         {
  73.                 return length;
  74.         }
  75.  
  76.         bool isempty()override
  77.         {
  78.                 return (length == 0);
  79.         }
  80.  
  81.         void clear()override
  82.         {
  83.                 length = 0;
  84.                 delete tail->next;
  85.                 delete tail->previus;
  86.                 delete head->next;
  87.                 delete head->previus;
  88.                 head = nullptr;
  89.                 tail = nullptr;
  90.         }
  91.  
  92.         T front()override
  93.         {
  94.                 assert(tail != nullptr);
  95.                 return tail->value;
  96.         }
  97.  
  98.         T back()override
  99.         {
  100.                 assert(head != nullptr);
  101.                 return head->value;
  102.         }
  103.  
  104.         T pop_front()override
  105.         {
  106.                 if(isempty()){
  107.                         throw std::runtime_error("eee be ota list kholihay, kjo pop_front() mekni");
  108.                 }
  109.                 T res = tail->value;
  110.                 if(tail->next != nullptr){
  111.                         assert(tail->next != nullptr);
  112.                         auto x = tail;
  113.                         tail = tail->next;
  114.                         tail->previus = nullptr;
  115.                         delete x;
  116.                 }else{
  117.                         delete tail->next;
  118.                         delete tail->previus;
  119.                         delete head->next;
  120.                         delete head->previus;
  121.                         tail = nullptr;
  122.                         head = nullptr;
  123.                 }
  124.                 length--;
  125.                 return res;
  126.         }
  127.  
  128.         void pop_back()override
  129.         {
  130.                 if(length == 0){
  131.                         throw std::runtime_error("eee be ota list kholihay, kjo pop_back() mekni");
  132.                 }
  133.                 else if(head->previus == nullptr){
  134.                         delete tail->next;
  135.                         delete tail->previus;
  136.                         delete head->next;
  137.                         delete head->previus;
  138.                         tail = nullptr;
  139.                         head = nullptr;
  140.                 }else{
  141.                         assert(head->previus != nullptr);
  142.                         auto x = head;
  143.                         head = head->previus;
  144.                         head->next = nullptr;
  145.                         delete x;
  146.                 }
  147.                 length--;
  148.         }
  149.         virtual T get(int index){
  150.                 if(index < 0 || index >= length){
  151.                     throw std::runtime_error("out of bounded array index");
  152.                 }else{
  153.                     Node<T>* current_node = tail;
  154.                     for(int i = 0; i < index; i ++){
  155.                         current_node = current_node->next;
  156.                     }
  157.                     return current_node->value;
  158.                 }
  159.             }
  160. };
  161. /*
  162. template<class T>
  163. class ICircularBoundedQueue
  164. {
  165.         public:
  166.         virtual void offer(T value) = 0;
  167.         // insert an element to the rear of the queue
  168.         // overwrite the oldest elements
  169.         // when the queue is full
  170.         virtual T poll() = 0;// remove an element from the front of the queue and return removed element
  171.         virtual T peek() = 0;// look at the element at the front of the queue
  172.         // (without removing it)
  173.         virtual void flush() = 0;// remove all elements from the queue
  174.         virtual bool isEmpty() = 0;// is the queue empty?
  175.         virtual bool isFull() = 0;// is the queue full?
  176.         virtual int size() = 0;// number of elements
  177.         virtual int capacity() = 0;// maximum capacity
  178. };
  179.  
  180. template <class T>
  181. class CircularBoundedQueue : public ICircularBoundedQueue<T>{
  182.  
  183.         DoubleLinkedList <T> q;
  184.         int Capacity;
  185. public:
  186.         CircularBoundedQueue(int C=100) : Capacity(C){}
  187.         void init(int C)
  188.         {
  189.                 Capacity = C;
  190.         }
  191.         virtual void offer(T new_variable)override
  192.         {
  193.                 if(q.size() >= capacity()){
  194.                         auto x = q.front();
  195.                         q.pop_front();
  196.                         delete[] x.first.a;
  197.                         delete[] x.first.b;
  198.                         delete[] x.second.a;
  199.                         delete[] x.second.b;
  200.                 }
  201.                 q.push_back(new_variable);
  202.         }
  203.  
  204.         virtual T poll()override
  205.         {
  206.                 T x = q.front();
  207.                 q.pop_front();
  208.                 return x;
  209.         }
  210.  
  211.         virtual T peek()override
  212.         {
  213.                 return q.front();
  214.         }
  215.  
  216.         virtual void flush()override
  217.         {
  218.                 q.clear();
  219.         }
  220.  
  221.         virtual bool isFull() override
  222.         {
  223.                 return (q.size() == capacity());
  224.         }
  225.  
  226.         virtual bool isEmpty() override
  227.         {
  228.                 return q.isempty();
  229.         }
  230.  
  231.         virtual int size() override
  232.         {
  233.                 return q.size();
  234.         }
  235.  
  236.         virtual int capacity() override
  237.         {
  238.                 return Capacity;
  239.         }
  240.  
  241. };
  242. */
  243. template<class T>
  244. class ICircularBoundedQueue
  245. {
  246.         public:
  247.         virtual void offer(T value) = 0;
  248.         virtual T poll() = 0;
  249.         virtual T peek() = 0;
  250.         virtual void flush() = 0;
  251.         virtual bool isEmpty() const = 0;
  252.         virtual bool isFull() const = 0;
  253.         virtual int size() const = 0;
  254.         virtual int capacity() const = 0;
  255.         virtual ~ICircularBoundedQueue() = default;
  256. };
  257.  
  258. template <class T>
  259. class CircularBoundedQueue : public ICircularBoundedQueue<T>{
  260.  
  261.         T* a;
  262.         int Capacity;
  263.         int l = 0, r = -1;
  264. public:
  265.         void init(int C)
  266.         {
  267.                 Capacity = C;
  268.                 delete a;
  269.                 a = new T[C];
  270.         }
  271.  
  272.          void add(int &x, int val){
  273.                 x += val;
  274.                 x %= Capacity;
  275.                 x += Capacity;
  276.                 x %= Capacity;
  277.         }
  278.  
  279.         virtual void offer(T new_variable)override
  280.         {
  281.                 if(r != -1 && (r + 1) % Capacity == l){
  282.                         add(l, 1);
  283.                 }
  284.                 add(r, 1);
  285.                 a[r] = new_variable;
  286.         }
  287.  
  288.         virtual T poll()override
  289.         {
  290.                 T x = a[l];
  291.                 if(l == r){
  292.                         r = -1;
  293.                         l = 0;
  294.                 }else add(l, 1);
  295.                 return x;
  296.         }
  297.  
  298.         virtual T peek()override
  299.         {
  300.                 return a[l];
  301.         }
  302.  
  303.         virtual void flush()override
  304.         {
  305.                 l = 0, r = -1;
  306.         }
  307.  
  308.         virtual bool isFull() const override
  309.         {
  310.                 return (r + 1) % Capacity == l;
  311.         }
  312.  
  313.         virtual bool isEmpty() const override
  314.         {
  315.                 return (r == -1);
  316.         }
  317.  
  318.         virtual int size() const override
  319.         {
  320.                 if(r == -1)return 0;
  321.                 if(l <= r)return r - l + 1;
  322.                 return Capacity - l + r + 1;
  323.         }
  324.  
  325.         virtual int capacity() const override
  326.         {
  327.                 return Capacity;
  328.         }
  329.  
  330. };
  331.  
  332. template<class T>
  333. class Stack{
  334.         virtual void push(T value) = 0;// push an element onto the stack
  335.                                         // remove the oldest element
  336.                                         // when if stack is full
  337.         virtual T pop() = 0;    // remove an element from the top of the stack
  338.         virtual T top() = 0;    // look at the element at the top of the stack
  339.                                 // (without removing it)
  340.         virtual void flush() = 0;// remove all elements from the stack
  341.         virtual bool isEmpty() = 0;// is the stack empty?
  342.         virtual bool isFull() = 0;// is the stack full?
  343.         virtual int size() = 0; // number of elements
  344.         virtual int capacity() = 0; // maximum capacity
  345. };
  346.  
  347. template<class T>
  348. class BoundedStack : public Stack<T>{
  349.         CircularBoundedQueue<T> q1;
  350.         CircularBoundedQueue<T> q2;
  351.         int Capacity;
  352. public:
  353.         void init(int val){
  354.                 Capacity = val;
  355.                 q1.init(val);
  356.                 q2.init(val);
  357.         }
  358.  
  359.         void push(T value) override
  360.         {
  361.                 if(q1.isEmpty()){
  362.                         q1.offer(value);
  363.                 }else{
  364.                         if(q1.size() == capacity()){
  365.                                 while(!q1.isEmpty()){
  366.                                         if(q1.size() == 1){
  367.                                                 auto x = q1.peek();
  368.                                                 q1.poll();
  369.                                                 delete[] x.first.a;
  370.                                                 delete[] x.first.b;
  371.                                                 delete[] x.second.a;
  372.                                                 delete[] x.second.b;
  373.                                                 break;
  374.                                         }
  375.                                         q2.offer(q1.poll());
  376.                                 }
  377.                         }else{
  378.                                 while(!q1.isEmpty()){
  379.                                         q2.offer(q1.poll());
  380.                                 }
  381.                         }
  382.                         q1.offer(value);
  383.                         while(!q2.isEmpty()){
  384.                                 q1.offer(q2.poll());
  385.                         }
  386.                 }
  387.         }
  388.  
  389.         int capacity()override
  390.         {
  391.             return Capacity;
  392.         }
  393.  
  394.         T pop()override
  395.         {
  396.                 return q1.poll();
  397.         }
  398.  
  399.         T top()override
  400.         {
  401.                 assert(!q1.isEmpty());
  402.                 return q1.peek();
  403.         }
  404.  
  405.         void flush()override
  406.         {
  407.                 while(!q1.isEmpty()){
  408.                         q1.poll();
  409.                 }
  410.         }
  411.  
  412.         int size()override
  413.         {
  414.                 return q1.size();
  415.         }
  416.  
  417.         bool isEmpty()override
  418.         {
  419.                 return (q1.size() == 0);
  420.         }
  421.  
  422.         bool isFull() override
  423.         {
  424.                 return (q1.size() == capacity());
  425.         }
  426. };
  427.  
  428. template<class T>
  429. class Iset{
  430.         virtual void add(T item) = 0; // add item in the set
  431.         virtual void remove(T item) = 0; // remove an item from a set
  432.         virtual bool contains(T item) = 0; // check if a item belongs to a set
  433.         virtual int size() = 0; // number of elements in a set
  434.         virtual bool isEmpty() = 0; // check if the set is empty
  435. };
  436.  
  437. template <class T>
  438. class DoubleHasSet : public Iset<T>{
  439. public:
  440.         int* a;
  441.         T* b;
  442.         int length = 0;
  443.         int Capacity = 2;
  444.         DoubleHasSet()
  445.         {
  446.                 Capacity = 2;
  447.                 a = new int[2];
  448.                 b = new T[2];
  449.                 a[0] = a[1] = 0;
  450.                 length = 0;
  451.         }
  452.  
  453.         int getHash(T key, int j)
  454.         {
  455.                 auto hashfunc = std::hash<T>();
  456.                 int val = hashfunc(key);
  457.                 val = abs(val);
  458.                 int res = val % capacity();
  459.                 res += j;
  460.                 res %= capacity();
  461.                 if(res < 0)res += capacity();
  462.                 return res;
  463.         }
  464.  
  465.         void resize()
  466.         {
  467.                 int old_capacity = capacity();
  468.                 Capacity *= 2;
  469.                 auto x = b;
  470.                 auto y = a;
  471.                 b = new T[Capacity];
  472.                 a = new int[Capacity];
  473.                 for(int i = 0; i < Capacity; i++){
  474.                         a[i] = 0;
  475.                 }
  476.                 length = 0;
  477.                 for(int i = 0; i < old_capacity; i++){
  478.                         if(y[i] == 1){
  479.                                 add(x[i]);
  480.                         }
  481.                 }
  482.                 delete[] x;
  483.                 delete[] y;
  484.         }
  485.  
  486.         void add(T item) override
  487.         {
  488.                 if(capacity() == size()){
  489.                         resize();
  490.                 }
  491.                 if(contains(item))return;
  492.                 int j = 0;
  493.                 while(j <= capacity() && a[getHash(item, j)] == 1){
  494.                         j++;
  495.                 }
  496.                 if(a[getHash(item, j)] == 1){
  497.                         throw runtime_error("You can not add new element, because of capacity");
  498.                 }
  499.                 a[getHash(item, j)] = 1;
  500.                 b[getHash(item, j)] = item;
  501.                 length++;
  502.         }
  503.  
  504.         bool contains(T item)override
  505.         {
  506.                 int j = 0;
  507.                 while(j <= capacity() && a[getHash(item, j)] != 0){
  508.                         if(a[getHash(item, j)] == 1 && b[getHash(item, j)] == item){
  509.                                 return true;
  510.                         }
  511.                         j++;
  512.                 }
  513.                 return false;
  514.         }
  515.  
  516.         void remove(T item)override
  517.         {
  518.                 int j = 0;
  519.                 while(j <= capacity() && a[getHash(item, j)] != 0){
  520.                         if(a[getHash(item, j)] == 1 && b[getHash(item, j)] == item){
  521.                                 a[getHash(item, j)] = 2;
  522.                                 length--;
  523.                                 break;
  524.                         }
  525.                         j++;
  526.                 }
  527.         }
  528.  
  529.         int size()override
  530.         {
  531.                 return length;
  532.         }
  533.  
  534.         bool isEmpty()override
  535.         {
  536.                 return size() == 0;
  537.         }
  538.  
  539.         int capacity()
  540.         {
  541.                 return Capacity;
  542.         }
  543. };
  544.  
  545.  
  546.  
  547. int main()
  548. {
  549.         //freopen("input.txt", "r", stdin);
  550.         string A;
  551.         int n,k;
  552.         cin >> n >> k;
  553.         BoundedStack<pair<DoubleHasSet<string>, DoubleHasSet<string>>> st;
  554.         getline(cin, A);
  555.         st.init(k);
  556.         DoubleHasSet<string> a,b;
  557.         st.push({a, b});// empty set
  558.         while(n--){
  559.                 getline(cin, A);
  560.                 string s = "",t = "";
  561.                 for(int i = 0, j = 0; i < (int)A.size(); i++){
  562.                         if(A[i] == ' '){
  563.                                 if(j == 1){
  564.                                         s = "N";
  565.                                         break;
  566.                                 }
  567.                                 j = 1;
  568.                         }else if(j){
  569.                                 t += A[i];
  570.                         }else{
  571.                                 s += A[i];
  572.                         }
  573.                 }
  574.                 if(s == "NEW"){
  575.                         auto File = st.top().first;
  576.                         auto Directory = st.top().second;
  577.                         auto x = new int[File.capacity()];
  578.                         auto y = new string[File.capacity()];
  579.                         for(int i = 0; i < File.capacity(); i++){
  580.                                 x[i] = File.a[i];
  581.                                 y[i] = File.b[i];
  582.                         }
  583.                         auto xx = new int[Directory.capacity()];
  584.                         auto yy = new string[Directory.capacity()];
  585.                         for(int i = 0; i < Directory.capacity(); i++){
  586.                                 xx[i] = Directory.a[i];
  587.                                 yy[i] = Directory.b[i];
  588.                         }
  589.                         File.a = x;
  590.                         File.b = y;
  591.                         Directory.a = xx;
  592.                         Directory.b = yy;
  593.                         if(t.back() == '/'){
  594.                                 t.pop_back();
  595.                                 if(Directory.contains(t) || File.contains(t)){
  596.                                         cout << "ERROR: cannot execute " << A << endl;
  597.                                         continue;
  598.                                 }
  599.                                 Directory.add(t);
  600.                         }else{
  601.                                if(Directory.contains(t) || File.contains(t)){
  602.                                         cout << "ERROR: cannot execute " << A << endl;
  603.                                         continue;
  604.                                 }
  605.                                 File.add(t);
  606.                         }
  607.                         st.push({File, Directory});
  608.                 }else if(s == "REMOVE"){
  609.                         auto File = st.top().first;
  610.                         auto Directory = st.top().second;
  611.                         auto x = new int[File.capacity()];
  612.                         auto y = new string[File.capacity()];
  613.                         for(int i = 0; i < File.capacity(); i++){
  614.                                 x[i] = File.a[i];
  615.                                 y[i] = File.b[i];
  616.                         }
  617.                         auto xx = new int[Directory.capacity()];
  618.                         auto yy = new string[Directory.capacity()];
  619.                         for(int i = 0; i < Directory.capacity(); i++){
  620.                                 xx[i] = Directory.a[i];
  621.                                 yy[i] = Directory.b[i];
  622.                         }
  623.                         File.a = x;
  624.                         File.b = y;
  625.                         Directory.a = xx;
  626.                         Directory.b = yy;
  627.                         if(t.back() == '/'){
  628.                                 t.pop_back();
  629.                                 if(!Directory.contains(t)){
  630.                                         cout << "ERROR: cannot execute " << A << endl;
  631.                                         continue;
  632.                                 }
  633.                                 Directory.remove(t);
  634.                         }else{
  635.                                if(!File.contains(t)){
  636.                                         cout << "ERROR: cannot execute " << A << endl;
  637.                                         continue;
  638.                                 }
  639.                                 File.remove(t);
  640.                         }
  641.                         st.push({File, Directory});
  642.                 }else if(s == "UNDO"){
  643.                         int n1 = 1;
  644.                         bool f = false;
  645.                         if((int)t.size() > 0){
  646.                                 n1 = 0;
  647.                                 for(int i = 0; i < (int)t.size(); i++){
  648.                                         if(!('0' <= t[i] && t[i] <= '9')){
  649.                                                 cout << "ERROR: cannot execute " << A << endl;
  650.                                                 f = true;
  651.                                                 break;
  652.                                         }
  653.                                         n1 *= 10;
  654.                                         n1 += t[i] - '0';
  655.                                 }
  656.                         }
  657.                         if(f)continue;
  658.                         if(n1 >= st.size()){
  659.                                 cout << "ERROR: cannot execute " << A << endl;
  660.                                 continue;
  661.                         }
  662.                         for(int i = 1; i <= n1; i++){
  663.                                 delete[] st.top().first.a;
  664.                                 delete[] st.top().first.b;
  665.                                 delete[] st.top().second.a;
  666.                                 delete[] st.top().second.b;
  667.                                 st.pop();
  668.                         }
  669.                 }else if(s == "LIST"){
  670.                         auto File = st.top().first;
  671.                         auto Directory = st.top().second;
  672.                         for(int i = 0; i < File.capacity(); i++){
  673.                                 if(File.a[i] == 1){
  674.                                         cout << File.b[i] << " ";
  675.                                 }
  676.                         }
  677.                         for(int i = 0; i < Directory.capacity(); i++){
  678.                                 if(Directory.a[i] == 1){
  679.                                         cout << Directory.b[i] << "/ ";
  680.                                 }
  681.                         }
  682.                         cout << endl;
  683.                 }else{
  684.                         cout << "ERROR: cannot execute " << A << endl;
  685.                 }
  686.         }
  687. }
  688.  
Advertisement
Add Comment
Please, Sign In to add comment