1-ShadowMaster-1

Untitled

Feb 20th, 2022
754
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 16.08 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. namespace std
  195. {
  196.         template<class T>
  197.         struct secondhash;
  198.  
  199.         template<>
  200.         struct secondhash<int>
  201.         {
  202.                 int operator()(int val, int capacity)
  203.                 {
  204.                         string s = to_string(val);
  205.                         int res = 0;
  206.                         int p = 1;
  207.                         int x = 17;
  208.                         for(int i = 0; i < (int)s.size(); i++){
  209.                                 res += s[i] * 1ll * p % (capacity * 1ll);
  210.                                 res %= capacity;
  211.                                 p = p * 1ll * x % (capacity * 1ll);
  212.                         }
  213.                         return res;
  214.                 }
  215.         };
  216.  
  217.         template<>
  218.         struct secondhash<string>
  219.         {
  220.                 int operator()(string s, int capacity)
  221.                 {
  222.                         int res = 0;
  223.                         int p = 1;
  224.                         int x = 17;
  225.                         for(int i = 0; i < (int)s.size(); i++){
  226.                                 res += s[i] * 1ll * p % (capacity * 1ll);
  227.                                 res %= capacity;
  228.                                 p = p * 1ll * x % (capacity * 1ll);
  229.                         }
  230.                         return res;
  231.                 }
  232.         };
  233. }
  234.  
  235. template <class T>
  236. class DoubleHasSet : public Iset<T>{
  237. public:
  238.         int* a;
  239.         T* b;
  240.         int length = 0;
  241.         int Capacity = 2;
  242.         DoubleHasSet()
  243.         {
  244.                 Capacity = 2;
  245.                 a = new int[2];
  246.                 b = new T[2];
  247.                 a[0] = a[1] = 0;
  248.                 length = 0;
  249.         }
  250.  
  251.         secondhash<T> has2;
  252.         int getHash(T key, int j)
  253.         {
  254.                 auto hashfunc = std::hash<T>();
  255.                 int val = hashfunc(key);
  256.                 val = abs(val);
  257.                 int res = val % capacity();
  258.                 res += j * 1ll * has2(key, capacity()) % (capacity() * 1ll);
  259.                 res %= capacity();
  260.                 if(res < 0)res += capacity();
  261.                 return res;
  262.         }
  263.  
  264.         void resize()
  265.         {
  266.                 int old_capacity = capacity();
  267.                 Capacity *= 2;
  268.                 auto x = b;
  269.                 auto y = a;
  270.                 b = new T[Capacity];
  271.                 a = new int[Capacity];
  272.                 for(int i = 0; i < Capacity; i++){
  273.                         a[i] = 0;
  274.                 }
  275.                 length = 0;
  276.                 for(int i = 0; i < old_capacity; i++){
  277.                         if(y[i] == 1){
  278.                                 add(x[i]);
  279.                         }
  280.                 }
  281.                 delete[] x;
  282.                 delete[] y;
  283.         }
  284.  
  285.         void add(T item) override
  286.         {
  287.                 if(contains(item))return;
  288.                 int j = 0;
  289.                 while(j <= capacity() && a[getHash(item, j)] == 1){
  290.                         j++;
  291.                 }
  292.                 if(a[getHash(item, j)] == 1){
  293.                         resize();
  294.                         add(item);
  295.                         return;
  296.                 }
  297.                 a[getHash(item, j)] = 1;
  298.                 b[getHash(item, j)] = item;
  299.                 length++;
  300.         }
  301.  
  302.         bool contains(T item)override
  303.         {
  304.                 int j = 0;
  305.                 while(j <= capacity() && a[getHash(item, j)] != 0){
  306.                         if(a[getHash(item, j)] == 1 && b[getHash(item, j)] == item){
  307.                                 return true;
  308.                         }
  309.                         j++;
  310.                 }
  311.                 return false;
  312.         }
  313.  
  314.         void remove(T item)override
  315.         {
  316.                 int j = 0;
  317.                 while(j <= capacity() && a[getHash(item, j)] != 0){
  318.                         if(a[getHash(item, j)] == 1 && b[getHash(item, j)] == item){
  319.                                 a[getHash(item, j)] = 2;
  320.                                 length--;
  321.                                 break;
  322.                         }
  323.                         j++;
  324.                 }
  325.         }
  326.  
  327.         int size()override
  328.         {
  329.                 return length;
  330.         }
  331.  
  332.         bool isEmpty()override
  333.         {
  334.                 return size() == 0;
  335.         }
  336.  
  337.         int capacity()
  338.         {
  339.                 return Capacity;
  340.         }
  341. };
  342.  
  343.  
  344.  
  345. int main()
  346. {
  347.         string A;
  348.         int n,k;
  349.         cin >> n >> k;
  350.         BoundedStack<pair<DoubleHasSet<string>, DoubleHasSet<string>>> st;
  351.         getline(cin, A);
  352.         st.init(k);
  353.         DoubleHasSet<string> a,b;
  354.         st.push({a, b});// empty set
  355.         while(n--){
  356.                 getline(cin, A);
  357.                 string s = "",t = "";
  358.                 for(int i = 0, j = 0; i < (int)A.size(); i++){
  359.                         if(A[i] == ' '){
  360.                                 if(j == 1){
  361.                                         s = "N";
  362.                                         break;
  363.                                 }
  364.                                 j = 1;
  365.                         }else if(j){
  366.                                 t += A[i];
  367.                         }else{
  368.                                 s += A[i];
  369.                         }
  370.                 }
  371.                 if(s == "NEW"){
  372.                         auto File = st.top().first;
  373.                         auto Directory = st.top().second;
  374.                         auto x = new int[File.capacity()];
  375.                         auto y = new string[File.capacity()];
  376.                         for(int i = 0; i < File.capacity(); i++){
  377.                                 x[i] = File.a[i];
  378.                                 y[i] = File.b[i];
  379.                         }
  380.                         auto xx = new int[Directory.capacity()];
  381.                         auto yy = new string[Directory.capacity()];
  382.                         for(int i = 0; i < Directory.capacity(); i++){
  383.                                 xx[i] = Directory.a[i];
  384.                                 yy[i] = Directory.b[i];
  385.                         }
  386.                         File.a = x;
  387.                         File.b = y;
  388.                         Directory.a = xx;
  389.                         Directory.b = yy;
  390.                         if(t.back() == '/'){
  391.                                 t.pop_back();
  392.                                 if(Directory.contains(t) || File.contains(t)){
  393.                                         cout << "ERROR: cannot execute " << A << endl;
  394.                                         continue;
  395.                                 }
  396.                                 Directory.add(t);
  397.                         }else{
  398.                                if(Directory.contains(t) || File.contains(t)){
  399.                                         cout << "ERROR: cannot execute " << A << endl;
  400.                                         continue;
  401.                                 }
  402.                                 File.add(t);
  403.                         }
  404.                         st.push({File, Directory});
  405.                 }else if(s == "REMOVE"){
  406.                         auto File = st.top().first;
  407.                         auto Directory = st.top().second;
  408.                         auto x = new int[File.capacity()];
  409.                         auto y = new string[File.capacity()];
  410.                         for(int i = 0; i < File.capacity(); i++){
  411.                                 x[i] = File.a[i];
  412.                                 y[i] = File.b[i];
  413.                         }
  414.                         auto xx = new int[Directory.capacity()];
  415.                         auto yy = new string[Directory.capacity()];
  416.                         for(int i = 0; i < Directory.capacity(); i++){
  417.                                 xx[i] = Directory.a[i];
  418.                                 yy[i] = Directory.b[i];
  419.                         }
  420.                         File.a = x;
  421.                         File.b = y;
  422.                         Directory.a = xx;
  423.                         Directory.b = yy;
  424.                         if(t.back() == '/'){
  425.                                 t.pop_back();
  426.                                 if(!Directory.contains(t)){
  427.                                         cout << "ERROR: cannot execute " << A << endl;
  428.                                         continue;
  429.                                 }
  430.                                 Directory.remove(t);
  431.                         }else{
  432.                                if(!File.contains(t)){
  433.                                         cout << "ERROR: cannot execute " << A << endl;
  434.                                         continue;
  435.                                 }
  436.                                 File.remove(t);
  437.                         }
  438.                         st.push({File, Directory});
  439.                 }else if(s == "UNDO"){
  440.                         int n1 = 1;
  441.                         bool f = false;
  442.                         if((int)t.size() > 0){
  443.                                 n1 = 0;
  444.                                 for(int i = 0; i < (int)t.size(); i++){
  445.                                         if(!('0' <= t[i] && t[i] <= '9')){
  446.                                                 cout << "ERROR: cannot execute " << A << endl;
  447.                                                 f = true;
  448.                                                 break;
  449.                                         }
  450.                                         n1 *= 10;
  451.                                         n1 += t[i] - '0';
  452.                                 }
  453.                         }
  454.                         if(f)continue;
  455.                         if(n1 >= st.size()){
  456.                                 cout << "ERROR: cannot execute " << A << endl;
  457.                                 continue;
  458.                         }
  459.                         for(int i = 1; i <= n1; i++){
  460.                                 delete[] st.top().first.a;
  461.                                 delete[] st.top().first.b;
  462.                                 delete[] st.top().second.a;
  463.                                 delete[] st.top().second.b;
  464.                                 st.pop();
  465.                         }
  466.                 }else if(s == "LIST"){
  467.                         auto File = st.top().first;
  468.                         auto Directory = st.top().second;
  469.                         for(int i = 0; i < File.capacity(); i++){
  470.                                 if(File.a[i] == 1){
  471.                                         cout << File.b[i] << " ";
  472.                                 }
  473.                         }
  474.                         for(int i = 0; i < Directory.capacity(); i++){
  475.                                 if(Directory.a[i] == 1){
  476.                                         cout << Directory.b[i] << "/ ";
  477.                                 }
  478.                         }
  479.                         cout << endl;
  480.                 }else{
  481.                         cout << "ERROR: cannot execute " << A << endl;
  482.                 }
  483.         }
  484. }
Advertisement
Add Comment
Please, Sign In to add comment