Submit Info #40622

Problem Lang User Status Time Memory
Persistent Queue cpp ebifly AC 648 ms 77.43 MiB

ケース詳細
Name Status Time Memory
ephemeral_00 AC 378 ms 57.66 MiB
example_00 AC 1 ms 0.67 MiB
half_rot_killer2_00 AC 230 ms 67.04 MiB
half_rot_killer_00 AC 480 ms 59.06 MiB
random_00 AC 547 ms 65.68 MiB
random_01 AC 648 ms 77.43 MiB
random_02 AC 65 ms 9.57 MiB
random_2_00 AC 495 ms 59.02 MiB
random_2_01 AC 586 ms 68.07 MiB
random_2_02 AC 55 ms 8.84 MiB
random_3_00 AC 326 ms 40.54 MiB
random_3_01 AC 384 ms 48.32 MiB
random_3_02 AC 45 ms 6.16 MiB
two_stacks_killer_00 AC 406 ms 52.82 MiB

#include <iostream> #include <iomanip> #include <limits> #include <vector> #include <variant> #include <functional> #include <memory> #include <utility> namespace ebi { template<class T> struct suspension : std::shared_ptr<std::variant<T, std::function<T()>>> { using value_type = T; using func_type = std::function<T()>; using node_type = std::variant<T, std::function<T()>>; using base_type = std::shared_ptr<node_type>; private: static T get(node_type &x) { if(x.index() != 0) { x = std::get<1>(x)(); } return std::get<0>(x); } public: suspension(T x) : base_type(std::make_shared<node_type>(std::in_place_index<0>, x)) { } suspension(std::function<T()> f) : base_type(std::make_shared<node_type>(std::in_place_index<1>, f)) { } T force() const { return get(**this); } }; } #include <optional> #include <cassert> namespace ebi { template<class T> struct stream : suspension<std::optional<std::pair<T, stream<T>>>> { private: using Self = stream<T>; using cell_type = std::optional<std::pair<T, Self>>; using base_type = suspension<cell_type>; using base_type::force; stream(T x, Self s) : base_type(cell_type(std::in_place, x, s)) { } public: stream() : base_type(cell_type(std::nullopt)) { } stream(std::function<cell_type()> f) : base_type(f) { } bool empty() const { return !force().has_value(); } T top() const { assert(!empty()); return force()->first; } Self push(T x) const { return stream(x, *this); } Self pop() const { assert(!empty()); return (*force()).second; } Self reverse() { return Self([x = *this]() mutable { Self ret; while(!x.empty()) { ret = ret.push(x.top()); x = x.pop(); } return ret.force(); }); } friend Self operator+(Self lhs, Self rhs) { return Self([lhs, rhs]() { if(lhs.empty()) { return rhs.force(); } else { return cell_type(std::in_place, lhs.top(), lhs.pop() + rhs); } }); } }; } #include <cassert> namespace ebi { template<class T> struct bankers_queue { private: using size_t = std::size_t; using Self = bankers_queue<T>; stream<T> f; size_t fsize; stream<T> r; size_t rsize; bankers_queue(stream<T> _f, size_t _fsize, stream<T> _r, size_t _rsize) : f(_f), fsize(_fsize), r(_r), rsize(_rsize) { } Self normalize() { if(fsize>=rsize) return *this; else { return Self(f+r.reverse(), fsize+rsize, stream<T>(), 0); } } public: bankers_queue() : f(), fsize(0), r(), rsize(0) { } bool empty() { return f.empty(); } T top() { assert(!empty()); return f.top(); } T front() { return top(); } Self push(T x) { return Self(f, fsize, r.push(x), rsize+1).normalize(); } Self pop() { assert(!empty()); return Self(f.pop(), fsize-1, r, rsize).normalize(); } }; } int main() { std::cout << std::fixed << std::setprecision(15); int q; std::cin >> q; std::vector<ebi::bankers_queue<int>> que(1); while(q--) { int flag; std::cin >> flag; if(flag == 0) { int t,x; std::cin >> t >> x; t++; que.emplace_back(que[t].push(x)); } else { int t; std::cin >> t; t++; std::cout << que[t].top() << '\n'; que.emplace_back(que[t].pop()); } } }