test/yosupo/ds/deque/dynamic_circular_deque.test.cpp

• View this file on GitHub
• Last update: 2025-09-20 17:47:50+07:00
• Problem: https://judge.yosupo.jp/problem/deque

Depends on

• Circular Deque (ds/circular_deque.hpp)

Code

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

#include <bits/stdc++.h>
using namespace std;

#include "ds/circular_deque.hpp"

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int q;
    cin >> q;

    DynamicCircularDeque<int> dq;
    dq.reserve(q);

    while (q--) {
        int t, x;
        cin >> t;
        if (t == 0) {
            cin >> x;
            dq.push_front(x);
        } else if (t == 1) {
            cin >> x;
            dq.push_back(x);
        } else if (t == 2) {
            dq.pop_front();
        } else if (t == 3) {
            dq.pop_back();
        } else {
            cin >> x;
            cout << dq[x] << "\n";
        }
    }
}

#line 1 "test/yosupo/ds/deque/dynamic_circular_deque.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/deque"

#include <bits/stdc++.h>
using namespace std;

#line 2 "ds/circular_deque.hpp"

template<class T, size_t N> struct CircularDeque {
    using value_type = T;
    using reference = T &;
    using const_reference = const T &;
    using size_type = size_t;

    size_t fr = 0, bk = 0;
    array<T, N> data;

    template<class... Ts> T &emplace_front(Ts &&...xs) {
        fr = (fr + N - 1) % N;
        return data[fr] = T(forward<Ts>(xs)...);
    }
    template<class... Ts> T &emplace_back(Ts &&...xs) {
        size_t tmp = exchange(bk, (bk + 1) % N);
        return data[tmp] = T(forward<Ts>(xs)...);
    }
    T &push_front(T x) { return emplace_front(move(x)); }
    T &push_back(T x) { return emplace_back(move(x)); }
    void pop_front() { fr = (fr + 1) % N; }
    void pop_back() { bk = (bk + N - 1) % N; }
    T &front() { return data[fr]; }
    T &back() { return data[(bk + N - 1) % N]; }
    const T &front() const { return data[fr]; }
    const T &back() const { return data[(bk + N - 1) % N]; }
    T &operator[](size_t i) { return data[(fr + i) % N]; }
    const T &operator[](size_t i) const { return data[(fr + i) % N]; }
    size_t size() const { return (bk - fr + N) % N; }
    bool empty() const { return bk == fr; }
    void clear() { fr = bk = 0, data[0] = T(); }
};

template<class T> struct DynamicCircularDeque {
    using value_type = T;
    using reference = T &;
    using const_reference = const T &;
    using size_type = size_t;

    size_t fr = 0, bk = 0, cap = 8;
    vector<T> data;

    DynamicCircularDeque() : data(cap) {}

    template<class... Ts> T &emplace_front(Ts &&...xs) {
        if (size() + 1 == cap) realloc(cap + 1);
        fr = (fr + cap - 1) & (cap - 1);
        return data[fr] = T(forward<Ts>(xs)...);
    }
    template<class... Ts> T &emplace_back(Ts &&...xs) {
        if (size() + 1 == cap) realloc(cap + 1);
        size_t tmp = exchange(bk, (bk + 1) & (cap - 1));
        return data[tmp] = T(forward<Ts>(xs)...);
    }
    T &push_front(T x) { return emplace_front(move(x)); }
    T &push_back(T x) { return emplace_back(move(x)); }
    void pop_front() { fr = (fr + 1) & (cap - 1); }
    void pop_back() { bk = (bk + cap - 1) & (cap - 1); }
    T &front() { return data[fr]; }
    T &back() { return data[(bk + cap - 1) & (cap - 1)]; }
    const T &front() const { return data[fr]; }
    const T &back() const { return data[(bk + cap - 1) & (cap - 1)]; }
    T &operator[](size_t i) { return data[(fr + i) & (cap - 1)]; }
    const T &operator[](size_t i) const { return data[(fr + i) & (cap - 1)]; }
    size_t size() const { return (bk - fr + cap) & (cap - 1); }
    bool empty() const { return bk == fr; }
    void clear() { fr = bk = 0, data[0] = T(); }
    void reserve(int n) { realloc(n); }

  private:
    void realloc(size_t n) {
        while (cap < n) cap *= 2;
        vector<T> d(cap);
        size_t sz = size();
        for (size_t i = 0; i < sz; i++) d[i] = move(data[(fr + i) & (cap - 1)]);
        fr = 0, bk = sz, data.swap(d);
    }
};
#line 7 "test/yosupo/ds/deque/dynamic_circular_deque.test.cpp"

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int q;
    cin >> q;

    DynamicCircularDeque<int> dq;
    dq.reserve(q);

    while (q--) {
        int t, x;
        cin >> t;
        if (t == 0) {
            cin >> x;
            dq.push_front(x);
        } else if (t == 1) {
            cin >> x;
            dq.push_back(x);
        } else if (t == 2) {
            dq.pop_front();
        } else if (t == 3) {
            dq.pop_back();
        } else {
            cin >> x;
            cout << dq[x] << "\n";
        }
    }
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	example_00	AC	5 ms	4 MB
g++	max_random_00	AC	48 ms	5 MB
g++	max_random_01	AC	51 ms	5 MB
g++	max_random_02	AC	50 ms	5 MB
g++	max_random_03	AC	57 ms	5 MB
g++	max_random_04	AC	51 ms	5 MB
g++	max_random_05	AC	39 ms	5 MB
g++	max_random_06	AC	39 ms	5 MB
g++	max_random_07	AC	68 ms	5 MB
g++	max_random_08	AC	67 ms	5 MB
g++	max_random_09	AC	56 ms	5 MB
g++	max_random_10	AC	47 ms	5 MB
g++	max_random_11	AC	51 ms	5 MB
g++	max_random_12	AC	51 ms	5 MB
g++	max_random_13	AC	56 ms	5 MB
g++	max_random_14	AC	57 ms	5 MB
g++	max_random_15	AC	51 ms	5 MB
g++	max_random_16	AC	61 ms	5 MB
g++	max_random_17	AC	50 ms	5 MB
g++	max_random_18	AC	66 ms	5 MB
g++	max_random_19	AC	50 ms	5 MB
g++	random_00	AC	41 ms	5 MB
g++	random_01	AC	47 ms	5 MB
g++	random_02	AC	10 ms	4 MB
g++	random_03	AC	43 ms	5 MB
g++	random_04	AC	30 ms	5 MB
g++	small_00	AC	4 ms	4 MB
g++	small_01	AC	4 ms	4 MB
g++	small_02	AC	4 ms	4 MB
g++	small_03	AC	4 ms	4 MB
g++	small_04	AC	4 ms	4 MB
g++	small_05	AC	4 ms	4 MB
g++	small_06	AC	4 ms	4 MB
g++	small_07	AC	4 ms	4 MB
g++	small_08	AC	4 ms	4 MB
g++	small_09	AC	4 ms	4 MB
clang++	example_00	AC	5 ms	4 MB
clang++	max_random_00	AC	51 ms	5 MB
clang++	max_random_01	AC	52 ms	5 MB
clang++	max_random_02	AC	51 ms	5 MB
clang++	max_random_03	AC	56 ms	5 MB
clang++	max_random_04	AC	52 ms	5 MB
clang++	max_random_05	AC	39 ms	5 MB
clang++	max_random_06	AC	40 ms	5 MB
clang++	max_random_07	AC	71 ms	6 MB
clang++	max_random_08	AC	64 ms	5 MB
clang++	max_random_09	AC	54 ms	5 MB
clang++	max_random_10	AC	48 ms	5 MB
clang++	max_random_11	AC	53 ms	5 MB
clang++	max_random_12	AC	51 ms	5 MB
clang++	max_random_13	AC	58 ms	5 MB
clang++	max_random_14	AC	58 ms	5 MB
clang++	max_random_15	AC	54 ms	5 MB
clang++	max_random_16	AC	61 ms	5 MB
clang++	max_random_17	AC	47 ms	5 MB
clang++	max_random_18	AC	66 ms	6 MB
clang++	max_random_19	AC	47 ms	6 MB
clang++	random_00	AC	41 ms	5 MB
clang++	random_01	AC	46 ms	6 MB
clang++	random_02	AC	10 ms	4 MB
clang++	random_03	AC	43 ms	5 MB
clang++	random_04	AC	30 ms	5 MB
clang++	small_00	AC	4 ms	3 MB
clang++	small_01	AC	4 ms	3 MB
clang++	small_02	AC	4 ms	4 MB
clang++	small_03	AC	4 ms	3 MB
clang++	small_04	AC	4 ms	4 MB
clang++	small_05	AC	4 ms	3 MB
clang++	small_06	AC	4 ms	4 MB
clang++	small_07	AC	4 ms	4 MB
clang++	small_08	AC	4 ms	4 MB
clang++	small_09	AC	4 ms	4 MB

Back to top page