1-ShadowMaster-1

Untitled

Feb 20th, 2022
672
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 14.69 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. template<class T>
  6. class ICircularBoundedQueue
  7. {
  8.         public:
  9.         virtual void offer(T value) = 0;
  10.         virtual T poll() = 0;
  11.         virtual T peek() = 0;
  12.         virtual void flush() = 0;
  13.         virtual bool isEmpty() const = 0;
  14.         virtual bool isFull() const = 0;
  15.         virtual int size() const = 0;
  16.         virtual int capacity() const = 0;
  17. };
  18.  
  19. template <class T>
  20. class ArrayCircularBoundedQueue : public ICircularBoundedQueue<T>{
  21.  
  22.         T* a;
  23.         int Capacity;
  24.         int l = 0, r = -1;
  25. public:
  26.         void init(int C)
  27.         {
  28.                 Capacity = C;
  29.                 delete a;
  30.                 a = new T[C];
  31.         }
  32.  
  33.          void add(int &x, int val){
  34.                 x += val;
  35.                 x %= Capacity;
  36.                 x += Capacity;
  37.                 x %= Capacity;
  38.         }
  39.  
  40.         virtual void offer(T new_variable)override
  41.         {
  42.                 if(r != -1 && (r + 1) % Capacity == l){
  43.                         add(l, 1);
  44.                 }
  45.                 add(r, 1);
  46.                 a[r] = new_variable;
  47.         }
  48.  
  49.         virtual T poll()override
  50.         {
  51.                 T x = a[l];
  52.                 if(l == r){
  53.                         r = -1;
  54.                         l = 0;
  55.                 }else add(l, 1);
  56.                 return x;
  57.         }
  58.  
  59.         virtual T peek()override
  60.         {
  61.                 return a[l];
  62.         }
  63.  
  64.         virtual void flush()override
  65.         {
  66.                 l = 0, r = -1;
  67.         }
  68.  
  69.         virtual bool isFull() const override
  70.         {
  71.                 return (r + 1) % Capacity == l;
  72.         }
  73.  
  74.         virtual bool isEmpty() const override
  75.         {
  76.                 return (r == -1);
  77.         }
  78.  
  79.         virtual int size() const override
  80.         {
  81.                 if(r == -1)return 0;
  82.                 if(l <= r)return r - l + 1;
  83.                 return Capacity - l + r + 1;
  84.         }
  85.  
  86.         virtual int capacity() const override
  87.         {
  88.                 return Capacity;
  89.         }
  90.  
  91. };
  92.  
  93. template<class T>
  94. class Stack{
  95.         virtual void push(T value) = 0;// push an element onto the stack
  96.                                         // remove the oldest element
  97.                                         // when if stack is full
  98.         virtual T pop() = 0;    // remove an element from the top of the stack
  99.         virtual T top() = 0;    // look at the element at the top of the stack
  100.                                 // (without removing it)
  101.         virtual void flush() = 0;// remove all elements from the stack
  102.         virtual bool isEmpty() = 0;// is the stack empty?
  103.         virtual bool isFull() = 0;// is the stack full?
  104.         virtual int size() = 0; // number of elements
  105.         virtual int capacity() = 0; // maximum capacity
  106. };
  107.  
  108. template<class T>
  109. class BoundedStack : public Stack<T>{
  110.         ArrayCircularBoundedQueue<T> q1;
  111.         ArrayCircularBoundedQueue<T> q2;
  112.         int Capacity;
  113. public:
  114.         void init(int val){
  115.                 Capacity = val;
  116.                 q1.init(val);
  117.                 q2.init(val);
  118.         }
  119.  
  120.         void push(T value) override
  121.         {
  122.                 if(q1.isEmpty()){
  123.                         q1.offer(value);
  124.                 }else{
  125.                         if(q1.size() == capacity()){
  126.                                 while(!q1.isEmpty()){
  127.                                         if(q1.size() == 1){
  128.                                                 auto x = q1.peek();
  129.                                                 q1.poll();
  130.                                                 break;
  131.                                         }
  132.                                         q2.offer(q1.poll());
  133.                                 }
  134.                         }else{
  135.                                 while(!q1.isEmpty()){
  136.                                         q2.offer(q1.poll());
  137.                                 }
  138.                         }
  139.                         q1.offer(value);
  140.                         while(!q2.isEmpty()){
  141.                                 q1.offer(q2.poll());
  142.                         }
  143.                 }
  144.         }
  145.  
  146.         int capacity()override
  147.         {
  148.             return Capacity;
  149.         }
  150.  
  151.         T pop()override
  152.         {
  153.                 return q1.poll();
  154.         }
  155.  
  156.         T top()override
  157.         {
  158.                 assert(!q1.isEmpty());
  159.                 return q1.peek();
  160.         }
  161.  
  162.         void flush()override
  163.         {
  164.                 while(!q1.isEmpty()){
  165.                         q1.poll();
  166.                 }
  167.         }
  168.  
  169.         int size()override
  170.         {
  171.                 return q1.size();
  172.         }
  173.  
  174.         bool isEmpty()override
  175.         {
  176.                 return (q1.size() == 0);
  177.         }
  178.  
  179.         bool isFull() override
  180.         {
  181.                 return (q1.size() == capacity());
  182.         }
  183. };
  184.  
  185. template<class T>
  186. class Iset{
  187.         virtual void add(T item) = 0; // add item in the set
  188.         virtual void remove(T item) = 0; // remove an item from a set
  189.         virtual bool contains(T item) = 0; // check if a item belongs to a set
  190.         virtual int size() = 0; // number of elements in a set
  191.         virtual bool isEmpty() = 0; // check if the set is empty
  192. };
  193.  
  194. template <class T>
  195. class DoubleHasSet : public Iset<T>{
  196. public:
  197.         int* a;
  198.         T* b;
  199.         int length = 0;
  200.         int Capacity = 2;
  201.         DoubleHasSet()
  202.         {
  203.                 Capacity = 2;
  204.                 a = new int[2];
  205.                 b = new T[2];
  206.                 a[0] = a[1] = 0;
  207.                 length = 0;
  208.         }
  209.  
  210.         int getHash(T key, int j)
  211.         {
  212.                 auto hashfunc = std::hash<T>();
  213.                 int val = hashfunc(key);
  214.                 val = abs(val);
  215.                 int res = val % capacity();
  216.                 res += j;
  217.                 res %= capacity();
  218.                 if(res < 0)res += capacity();
  219.                 return res;
  220.         }
  221.  
  222.         void resize()
  223.         {
  224.                 int old_capacity = capacity();
  225.                 Capacity *= 2;
  226.                 auto x = b;
  227.                 auto y = a;
  228.                 b = new T[Capacity];
  229.                 a = new int[Capacity];
  230.                 for(int i = 0; i < Capacity; i++){
  231.                         a[i] = 0;
  232.                 }
  233.                 length = 0;
  234.                 for(int i = 0; i < old_capacity; i++){
  235.                         if(y[i] == 1){
  236.                                 add(x[i]);
  237.                         }
  238.                 }
  239.                 delete[] x;
  240.                 delete[] y;
  241.         }
  242.  
  243.         void add(T item) override
  244.         {
  245.                 if(contains(item))return;
  246.                 int j = 0;
  247.                 while(j <= capacity() && a[getHash(item, j)] == 1){
  248.                         j++;
  249.                 }
  250.                 if(a[getHash(item, j)] == 1){
  251.                         resize();
  252.                         add(item);
  253.                         return;
  254.                 }
  255.                 a[getHash(item, j)] = 1;
  256.                 b[getHash(item, j)] = item;
  257.                 length++;
  258.         }
  259.  
  260.         bool contains(T item)override
  261.         {
  262.                 int j = 0;
  263.                 while(j <= capacity() && a[getHash(item, j)] != 0){
  264.                         if(a[getHash(item, j)] == 1 && b[getHash(item, j)] == item){
  265.                                 return true;
  266.                         }
  267.                         j++;
  268.                 }
  269.                 return false;
  270.         }
  271.  
  272.         void remove(T item)override
  273.         {
  274.                 int j = 0;
  275.                 while(j <= capacity() && a[getHash(item, j)] != 0){
  276.                         if(a[getHash(item, j)] == 1 && b[getHash(item, j)] == item){
  277.                                 a[getHash(item, j)] = 2;
  278.                                 length--;
  279.                                 break;
  280.                         }
  281.                         j++;
  282.                 }
  283.         }
  284.  
  285.         int size()override
  286.         {
  287.                 return length;
  288.         }
  289.  
  290.         bool isEmpty()override
  291.         {
  292.                 return size() == 0;
  293.         }
  294.  
  295.         int capacity()
  296.         {
  297.                 return Capacity;
  298.         }
  299. };
  300.  
  301.  
  302.  
  303. int main()
  304. {
  305.         string A;
  306.         int n,k;
  307.         cin >> n >> k;
  308.         BoundedStack<pair<DoubleHasSet<string>, DoubleHasSet<string>>> st;
  309.         getline(cin, A);
  310.         st.init(k);
  311.         DoubleHasSet<string> a,b;
  312.         st.push({a, b});// empty set
  313.         while(n--){
  314.                 getline(cin, A);
  315.                 string s = "",t = "";
  316.                 for(int i = 0, j = 0; i < (int)A.size(); i++){
  317.                         if(A[i] == ' '){
  318.                                 if(j == 1){
  319.                                         s = "N";
  320.                                         break;
  321.                                 }
  322.                                 j = 1;
  323.                         }else if(j){
  324.                                 t += A[i];
  325.                         }else{
  326.                                 s += A[i];
  327.                         }
  328.                 }
  329.                 if(s == "NEW"){
  330.                         auto File = st.top().first;
  331.                         auto Directory = st.top().second;
  332.                         auto x = new int[File.capacity()];
  333.                         auto y = new string[File.capacity()];
  334.                         for(int i = 0; i < File.capacity(); i++){
  335.                                 x[i] = File.a[i];
  336.                                 y[i] = File.b[i];
  337.                         }
  338.                         auto xx = new int[Directory.capacity()];
  339.                         auto yy = new string[Directory.capacity()];
  340.                         for(int i = 0; i < Directory.capacity(); i++){
  341.                                 xx[i] = Directory.a[i];
  342.                                 yy[i] = Directory.b[i];
  343.                         }
  344.                         File.a = x;
  345.                         File.b = y;
  346.                         Directory.a = xx;
  347.                         Directory.b = yy;
  348.                         if(t.back() == '/'){
  349.                                 t.pop_back();
  350.                                 if(Directory.contains(t) || File.contains(t)){
  351.                                         cout << "ERROR: cannot execute " << A << endl;
  352.                                         continue;
  353.                                 }
  354.                                 Directory.add(t);
  355.                         }else{
  356.                                if(Directory.contains(t) || File.contains(t)){
  357.                                         cout << "ERROR: cannot execute " << A << endl;
  358.                                         continue;
  359.                                 }
  360.                                 File.add(t);
  361.                         }
  362.                         st.push({File, Directory});
  363.                 }else if(s == "REMOVE"){
  364.                         auto File = st.top().first;
  365.                         auto Directory = st.top().second;
  366.                         auto x = new int[File.capacity()];
  367.                         auto y = new string[File.capacity()];
  368.                         for(int i = 0; i < File.capacity(); i++){
  369.                                 x[i] = File.a[i];
  370.                                 y[i] = File.b[i];
  371.                         }
  372.                         auto xx = new int[Directory.capacity()];
  373.                         auto yy = new string[Directory.capacity()];
  374.                         for(int i = 0; i < Directory.capacity(); i++){
  375.                                 xx[i] = Directory.a[i];
  376.                                 yy[i] = Directory.b[i];
  377.                         }
  378.                         File.a = x;
  379.                         File.b = y;
  380.                         Directory.a = xx;
  381.                         Directory.b = yy;
  382.                         if(t.back() == '/'){
  383.                                 t.pop_back();
  384.                                 if(!Directory.contains(t)){
  385.                                         cout << "ERROR: cannot execute " << A << endl;
  386.                                         continue;
  387.                                 }
  388.                                 Directory.remove(t);
  389.                         }else{
  390.                                if(!File.contains(t)){
  391.                                         cout << "ERROR: cannot execute " << A << endl;
  392.                                         continue;
  393.                                 }
  394.                                 File.remove(t);
  395.                         }
  396.                         st.push({File, Directory});
  397.                 }else if(s == "UNDO"){
  398.                         int n1 = 1;
  399.                         bool f = false;
  400.                         if((int)t.size() > 0){
  401.                                 n1 = 0;
  402.                                 for(int i = 0; i < (int)t.size(); i++){
  403.                                         if(!('0' <= t[i] && t[i] <= '9')){
  404.                                                 cout << "ERROR: cannot execute " << A << endl;
  405.                                                 f = true;
  406.                                                 break;
  407.                                         }
  408.                                         n1 *= 10;
  409.                                         n1 += t[i] - '0';
  410.                                 }
  411.                         }
  412.                         if(f)continue;
  413.                         if(n1 >= st.size()){
  414.                                 cout << "ERROR: cannot execute " << A << endl;
  415.                                 continue;
  416.                         }
  417.                         for(int i = 1; i <= n1; i++){
  418.                                 delete[] st.top().first.a;
  419.                                 delete[] st.top().first.b;
  420.                                 delete[] st.top().second.a;
  421.                                 delete[] st.top().second.b;
  422.                                 st.pop();
  423.                         }
  424.                 }else if(s == "LIST"){
  425.                         auto File = st.top().first;
  426.                         auto Directory = st.top().second;
  427.                         for(int i = 0; i < File.capacity(); i++){
  428.                                 if(File.a[i] == 1){
  429.                                         cout << File.b[i] << " ";
  430.                                 }
  431.                         }
  432.                         for(int i = 0; i < Directory.capacity(); i++){
  433.                                 if(Directory.a[i] == 1){
  434.                                         cout << Directory.b[i] << "/ ";
  435.                                 }
  436.                         }
  437.                         cout << endl;
  438.                 }else{
  439.                         cout << "ERROR: cannot execute " << A << endl;
  440.                 }
  441.         }
  442. }
Advertisement
Add Comment
Please, Sign In to add comment