test/yosupo-judge/persistent_queue/main.test.cpp

• View this file on GitHub
• Last update: 2021-04-23 23:44:44+09:00
• Problem: https://judge.yosupo.jp/problem/persistent_queue
• Link: View error logs on GitHub Actions

Depends on

• Persistent queue (Mylib/DataStructure/Queue/persistent_queue.cpp)
• Input tuple (Mylib/IO/input_tuple.cpp)
• Input tuples (Mylib/IO/input_tuples.cpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/persistent_queue"

#include <iostream>
#include <vector>
#include "Mylib/DataStructure/Queue/persistent_queue.cpp"
#include "Mylib/IO/input_tuples.cpp"

namespace hl = haar_lib;

int main() {
  int Q;
  std::cin >> Q;

  std::vector<hl::persistent_queue<int>> S;

  for (auto [type, t] : hl::input_tuples<int, int>(Q)) {
    if (type == 0) {
      int x;
      std::cin >> x;
      if (t == -1) {
        hl::persistent_queue<int> a(x);
        S.push_back(a);
      } else {
        auto res = S[t].push(x);
        S.push_back(res);
      }
    } else {
      std::cout << S[t].front() << std::endl;
      auto res = S[t].pop();
      S.push_back(res);
    }
  }

  return 0;
}

#line 1 "test/yosupo-judge/persistent_queue/main.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/persistent_queue"

#include <iostream>
#include <vector>
#line 2 "Mylib/DataStructure/Queue/persistent_queue.cpp"
#include <algorithm>
#include <array>
#line 6 "Mylib/DataStructure/Queue/persistent_queue.cpp"

namespace haar_lib {
  template <typename T>
  class persistent_queue {
  public:
    using value_type = T;

  private:
    constexpr static int MAX_SIZE_2 = 20;  // size <= 2 ^ MAX_SIZE_2

    struct node {
      T value;
      std::array<node *, MAX_SIZE_2> ancestors;
      int depth = 0;
    };

    node *front_node_ = nullptr, *back_node_ = nullptr;

    persistent_queue(node *front_node, node *back_node) : front_node_(front_node), back_node_(back_node) {}

  public:
    persistent_queue() {}
    persistent_queue(const T &value) {
      node *t    = new node();
      t->value   = value;
      back_node_ = front_node_ = t;
    }

    persistent_queue push(const T &value) const {
      node *t = new node();

      t->value = value;

      t->ancestors[0] = back_node_;
      for (int i = 1; i < MAX_SIZE_2; ++i) {
        node *s = t->ancestors[i - 1];
        if (s)
          t->ancestors[i] = s->ancestors[i - 1];
        else
          break;
      }

      t->depth = back_node_ ? back_node_->depth + 1 : 0;

      return persistent_queue(front_node_ ? front_node_ : t, t);
    }

    persistent_queue pop() const {
      if (back_node_->depth == front_node_->depth) {
        return persistent_queue(nullptr, nullptr);
      }

      int d = back_node_->depth - front_node_->depth - 1;

      node *t = back_node_;

      for (int i = MAX_SIZE_2 - 1; i >= 0; --i) {
        if (d >= (1 << i)) {
          d -= (1 << i);
          t = t->ancestors[i];
        }
        if (d == 0) break;
      }

      return persistent_queue(t, back_node_);
    }

    T front() const {
      return front_node_->value;
    }

    T back() const {
      return back_node_->value;
    }

    bool empty() const {
      return not front_node_;
    }

    int size() const {
      return front_node_ ? back_node_->depth - front_node_->depth + 1 : 0;
    }

    std::vector<T> data() const {
      std::vector<T> ret;
      node *t = back_node_;
      while (t) {
        if (t == front_node_) {
          ret.push_back(t->value);
          break;
        }
        ret.push_back(t->value);
        t = t->ancestors[0];
      }

      std::reverse(ret.begin(), ret.end());

      return ret;
    }
  };
}  // namespace haar_lib
#line 2 "Mylib/IO/input_tuples.cpp"
#include <initializer_list>
#line 4 "Mylib/IO/input_tuples.cpp"
#include <tuple>
#include <utility>
#line 6 "Mylib/IO/input_tuple.cpp"

namespace haar_lib {
  template <typename T, size_t... I>
  static void input_tuple_helper(std::istream &s, T &val, std::index_sequence<I...>) {
    (void) std::initializer_list<int>{(void(s >> std::get<I>(val)), 0)...};
  }

  template <typename T, typename U>
  std::istream &operator>>(std::istream &s, std::pair<T, U> &value) {
    s >> value.first >> value.second;
    return s;
  }

  template <typename... Args>
  std::istream &operator>>(std::istream &s, std::tuple<Args...> &value) {
    input_tuple_helper(s, value, std::make_index_sequence<sizeof...(Args)>());
    return s;
  }
}  // namespace haar_lib
#line 8 "Mylib/IO/input_tuples.cpp"

namespace haar_lib {
  template <typename... Args>
  class InputTuples {
    struct iter {
      using value_type = std::tuple<Args...>;
      value_type value;
      bool fetched = false;
      int N, c = 0;

      value_type operator*() {
        if (not fetched) {
          std::cin >> value;
        }
        return value;
      }

      void operator++() {
        ++c;
        fetched = false;
      }

      bool operator!=(iter &) const {
        return c < N;
      }

      iter(int N) : N(N) {}
    };

    int N;

  public:
    InputTuples(int N) : N(N) {}

    iter begin() const { return iter(N); }
    iter end() const { return iter(N); }
  };

  template <typename... Args>
  auto input_tuples(int N) {
    return InputTuples<Args...>(N);
  }
}  // namespace haar_lib
#line 7 "test/yosupo-judge/persistent_queue/main.test.cpp"

namespace hl = haar_lib;

int main() {
  int Q;
  std::cin >> Q;

  std::vector<hl::persistent_queue<int>> S;

  for (auto [type, t] : hl::input_tuples<int, int>(Q)) {
    if (type == 0) {
      int x;
      std::cin >> x;
      if (t == -1) {
        hl::persistent_queue<int> a(x);
        S.push_back(a);
      } else {
        auto res = S[t].push(x);
        S.push_back(res);
      }
    } else {
      std::cout << S[t].front() << std::endl;
      auto res = S[t].pop();
      S.push_back(res);
    }
  }

  return 0;
}

Back to top page