cp-documentation

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub zawa-tin/cp-documentation

:heavy_check_mark: Test/My/DataStructure/Heap/BinaryHeap.test.cpp

Depends on

Code

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

#include "../../../../Src/DataStructure/Heap/BinaryHeap.hpp"
using namespace zawa;

#include <queue>
#include <random>
#include <utility>
#include <vector>
#include <iostream>
#include <chrono>
using namespace std;

template <class T, class U>
ostream& operator<<(ostream& os, pair<T, U> p) {
    os << '(' << p.first << ',' << p.second << ')';
    return os;
}

template <class T>
ostream& operator<<(ostream& os, vector<T> a) {
    for (int i = 0 ; i < ssize(a) ; i++)
        os << a[i] << (i + 1 == ssize(a) ? "" : " ");
    return os;
}

template <class Queue>
vector<long long> test(const vector<pair<int, long long>>& query) {
    Queue q;
    vector<long long> res;
    res.reserve(q.size());
    chrono::system_clock::time_point start = chrono::system_clock::now();
    for (auto [t, v] : query) {
        if (t == 0) {
            q.push(v);
            res.push_back(v);
        }
        else if (t == 1) {
            if (q.empty())
                res.push_back(-1);
            else {
                res.push_back(q.top());
                q.pop();
            }
        }
    }
    chrono::system_clock::time_point end = chrono::system_clock::now();
    cerr << chrono::duration_cast<chrono::milliseconds>(end - start).count() << endl;
    return res;
}

int main() {
    const int Q = 4000000;
    vector<pair<int, long long>> q(Q);
    vector<long long> ins(Q/2);
    mt19937_64 mt{random_device{}()};
    for (int i = 0 ; i < Q / 2 ; i++) {
        q[i].first = 0;
        q[i].second = mt() % (long long)1e18;
        ins[i] = q[i].second;
    }
    for (int i = 0 ; i < Q / 2 ; i++) {
        q[Q/2 + i].first = mt() % 2;
        q[Q/2 + i].second = q[Q/2 + i].first ? -1LL : (mt() % (long long)1e18);
    }
    auto a = test<BinaryHeap<long long>>(q);
    auto b = test<priority_queue<long long, vector<long long>, greater<long long>>>(q);
    assert(a == b);
    {
        chrono::system_clock::time_point start = chrono::system_clock::now();
        vector<long long> c = ins;
        BinaryHeap<long long> heap(std::move(ins));
        c.reserve(Q);
        for (int i = Q / 2 ; i < Q ; i++) {
            auto [t, v] = q[i];
            if (t == 0) {
                heap.push(v);
                c.push_back(v);
            }
            else if (t == 1) {
                if (heap.empty())
                    c.push_back(-1);
                else {
                    c.push_back(heap.top());
                    heap.pop();
                }
            }
        }
        assert(a == c);
        chrono::system_clock::time_point end = chrono::system_clock::now();
        cerr << chrono::duration_cast<chrono::milliseconds>(end - start).count() << endl;
    }
    int A, B;
    cin >> A >> B;
    cout << A + B << '\n';
}
#line 1 "Test/My/DataStructure/Heap/BinaryHeap.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/aplusb"

#line 2 "Src/DataStructure/Heap/BinaryHeap.hpp"

#line 2 "Src/Template/TypeAlias.hpp"

#include <cstdint>
#include <cstddef>

namespace zawa {

using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using i128 = __int128_t;

using u8 = std::uint8_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;

using usize = std::size_t;

} // namespace zawa
#line 4 "Src/DataStructure/Heap/BinaryHeap.hpp"

#include <algorithm>
#include <cassert>
#include <concepts>
#include <utility>
#include <vector>
#include <functional>

namespace zawa {

template <class T, class Comp = std::less<T>>
requires std::strict_weak_order<Comp, const T&, const T&>
class BinaryHeap {
private:

    Comp m_comp;

    std::vector<T> m_dat;

public:

    inline usize size() const {
        return m_dat.size() - 1;
    }

    inline bool empty() const {
        return m_dat.size() == 1;
    }

    inline const Comp& comp() const {
        return m_comp;
    }

    using const_iterator = typename decltype(m_dat)::const_iterator;

    const_iterator begin() const {
        return m_dat.begin() + 1;
    }

    const_iterator end() const {
        return m_dat.end();
    }

    BinaryHeap(Comp comp = {}) 
        : m_comp{comp}, m_dat(1) {}

    template <std::forward_iterator It>
    requires std::same_as<std::iter_value_t<It>, T>
    BinaryHeap(It first, It last, Comp comp = {}) 
        : m_comp{comp}, m_dat(1) {
        m_dat.insert(m_dat.end(), first, last);
        build();
    }

    BinaryHeap(std::vector<T>&& a, Comp comp = {}) 
        : m_comp{comp}, m_dat(a.size() + 1) {
        std::ranges::copy(std::make_move_iterator(a.begin()), std::make_move_iterator(a.end()), m_dat.begin() + 1);
        build();
    }

    BinaryHeap(const std::vector<T>& a, Comp comp = {}) 
        : m_comp{comp}, m_dat(a.size() + 1) {
        std::ranges::copy(a.begin(), a.end(), m_dat.begin() + 1);
        build();
    }

    const T& top() const {
        assert(size() and "HeapUnderFlow");
        return m_dat[1];
    }

    void push(T&& v) {
        m_dat.push_back(std::move(v));
        upHeap(size());
    }

    void push(const T& v) {
        m_dat.push_back(v);
        upHeap(size());
    }

    void pop() {
        assert(size() and "HeapUnderFlow");
        if (size() > 1)
            std::swap(m_dat[1], m_dat.back());
        m_dat.pop_back();
        if (size() > 1)
            downHeap(1, size());
    }

private:

    void build() {
        const usize n = size();
        for (usize i = (n >> 1) ; i ; i--) 
            downHeap(i, n);
    }

    void upHeap(usize i) {
        while (i >> 1 and m_comp(m_dat[i], m_dat[i >> 1])) {
            std::swap(m_dat[i], m_dat[i >> 1]);
            i >>= 1;
        }
    }

    void downHeap(usize i, usize n) {
        while ((i << 1) <= n) {
            usize j = i << 1;
            if (j + 1 <= n and m_comp(m_dat[j + 1], m_dat[j]))
                j++;
            if (!m_comp(m_dat[j], m_dat[i]))
                break;
            std::swap(m_dat[i], m_dat[j]);
            i = j;
        }
    }
};

} // namespace zawa
#line 4 "Test/My/DataStructure/Heap/BinaryHeap.test.cpp"
using namespace zawa;

#include <queue>
#include <random>
#line 10 "Test/My/DataStructure/Heap/BinaryHeap.test.cpp"
#include <iostream>
#include <chrono>
using namespace std;

template <class T, class U>
ostream& operator<<(ostream& os, pair<T, U> p) {
    os << '(' << p.first << ',' << p.second << ')';
    return os;
}

template <class T>
ostream& operator<<(ostream& os, vector<T> a) {
    for (int i = 0 ; i < ssize(a) ; i++)
        os << a[i] << (i + 1 == ssize(a) ? "" : " ");
    return os;
}

template <class Queue>
vector<long long> test(const vector<pair<int, long long>>& query) {
    Queue q;
    vector<long long> res;
    res.reserve(q.size());
    chrono::system_clock::time_point start = chrono::system_clock::now();
    for (auto [t, v] : query) {
        if (t == 0) {
            q.push(v);
            res.push_back(v);
        }
        else if (t == 1) {
            if (q.empty())
                res.push_back(-1);
            else {
                res.push_back(q.top());
                q.pop();
            }
        }
    }
    chrono::system_clock::time_point end = chrono::system_clock::now();
    cerr << chrono::duration_cast<chrono::milliseconds>(end - start).count() << endl;
    return res;
}

int main() {
    const int Q = 4000000;
    vector<pair<int, long long>> q(Q);
    vector<long long> ins(Q/2);
    mt19937_64 mt{random_device{}()};
    for (int i = 0 ; i < Q / 2 ; i++) {
        q[i].first = 0;
        q[i].second = mt() % (long long)1e18;
        ins[i] = q[i].second;
    }
    for (int i = 0 ; i < Q / 2 ; i++) {
        q[Q/2 + i].first = mt() % 2;
        q[Q/2 + i].second = q[Q/2 + i].first ? -1LL : (mt() % (long long)1e18);
    }
    auto a = test<BinaryHeap<long long>>(q);
    auto b = test<priority_queue<long long, vector<long long>, greater<long long>>>(q);
    assert(a == b);
    {
        chrono::system_clock::time_point start = chrono::system_clock::now();
        vector<long long> c = ins;
        BinaryHeap<long long> heap(std::move(ins));
        c.reserve(Q);
        for (int i = Q / 2 ; i < Q ; i++) {
            auto [t, v] = q[i];
            if (t == 0) {
                heap.push(v);
                c.push_back(v);
            }
            else if (t == 1) {
                if (heap.empty())
                    c.push_back(-1);
                else {
                    c.push_back(heap.top());
                    heap.pop();
                }
            }
        }
        assert(a == c);
        chrono::system_clock::time_point end = chrono::system_clock::now();
        cerr << chrono::duration_cast<chrono::milliseconds>(end - start).count() << endl;
    }
    int A, B;
    cin >> A >> B;
    cout << A + B << '\n';
}
Back to top page