library

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

View the Project on GitHub gyouzasushi/library

:heavy_check_mark: test/unit/top_k_sum.test.cpp

Depends on

Code

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A"
#include <algorithm>
#include <cassert>
#include <chrono>
#include <functional>
#include <iostream>
#include <random>
#include <vector>

#include "datastructure/top_k_sum.hpp"
template <class Compare>
void check(std::mt19937_64& rng, int iters, int ops, int vals) {
    for (int iter = 0; iter < iters; iter++) {
        int k = rng() % 6;
        top_k_sum<long long, Compare> s(k);
        std::vector<long long> v;
        for (int t = 0; t < ops; t++) {
            int c = rng() % 4;
            if (c == 0 || v.empty()) {
                long long x = rng() % vals;
                s.insert(x);
                v.push_back(x);
            } else if (c == 1) {
                int i = rng() % v.size();
                s.erase(v[i]);
                v.erase(v.begin() + i);
            } else if (c == 2) {
                k = rng() % 6;
                s.set_k(k);
            }
            std::vector<long long> w = v;
            std::sort(w.begin(), w.end(), Compare());
            long long expect = 0;
            for (int i = 0; i < std::min<int>(k, w.size()); i++) expect += w[i];
            assert(s.size() == int(v.size()));
            assert(s.k() == k);
            assert(s.sum() == expect);
        }
    }
}
int main() {
    std::mt19937_64 rng(20261027);
    check<std::greater<long long>>(rng, 300, 60, 5);
    check<std::greater<long long>>(rng, 300, 60, 1000);
    check<std::less<long long>>(rng, 300, 60, 5);
    check<std::less<long long>>(rng, 300, 60, 1000);
    {
        // k = 0 と k > size
        top_k_sum<int> s(0);
        s.insert(5);
        assert(s.sum() == 0);
        s.set_k(10);
        assert(s.sum() == 5);
        s.erase(5);
        assert(s.sum() == 0 && s.size() == 0);
    }
    {
        int n = 200000;
        auto start = std::chrono::steady_clock::now();
        top_k_sum<long long> s(n / 2);
        std::vector<long long> v(n);
        for (int i = 0; i < n; i++) {
            v[i] = rng() % 1000000000;
            s.insert(v[i]);
        }
        long long acc = 0;
        for (int i = 0; i < n; i++) {
            s.erase(v[i]);
            v[i] = rng() % 1000000000;
            s.insert(v[i]);
            s.set_k(s.k() + (i % 2 ? 1 : -1));
            acc = (acc + s.sum()) % 1000000007;
        }
        std::vector<long long> w = v;
        std::sort(w.begin(), w.end(), std::greater<long long>());
        long long expect = 0;
        for (int i = 0; i < s.k(); i++) expect += w[i];
        assert(s.sum() == expect);
        auto ms = std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::steady_clock::now() - start).count();
        std::cerr << "perf " << n << " ops: " << ms << " ms (" << acc % 1000 << ")\n";
    }
    std::cout << "Hello World\n";
}
#line 1 "test/unit/top_k_sum.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A"
#include <algorithm>
#include <cassert>
#include <chrono>
#include <functional>
#include <iostream>
#include <random>
#include <vector>

#line 4 "datastructure/top_k_sum.hpp"
#include <queue>
#line 6 "datastructure/top_k_sum.hpp"
template <class T, class Compare = std::greater<T>>
struct top_k_sum {
public:
    explicit top_k_sum(int k) : _k(k), _sum(T()) {
        assert(k >= 0);
    }
    void insert(const T& x) {
        in.push(x);
        _sum += x;
        modify();
    }
    void erase(const T& x) {
        assert(size() > 0);
        if (!in.empty() && in.top() == x) {
            _sum -= x;
            in.pop();
        } else if (!in.empty() && Compare()(x, in.top())) {
            _sum -= x;
            d_in.push(x);
        } else {
            d_out.push(x);
        }
        modify();
    }
    void set_k(int k) {
        assert(k >= 0);
        _k = k;
        modify();
    }
    int k() const {
        return _k;
    }
    T sum() const {
        return _sum;
    }
    int size() const {
        return int(in.size() + out.size() - d_in.size() - d_out.size());
    }

private:
    struct reverse_compare {
        bool operator()(const T& a, const T& b) const {
            return Compare()(b, a);
        }
    };
    std::priority_queue<T, std::vector<T>, Compare> in, d_in;
    std::priority_queue<T, std::vector<T>, reverse_compare> out, d_out;
    int _k;
    T _sum;
    int in_size() const {
        return int(in.size() - d_in.size());
    }
    void modify() {
        while (in_size() < _k && !out.empty()) {
            T p = out.top();
            out.pop();
            if (!d_out.empty() && p == d_out.top()) {
                d_out.pop();
            } else {
                _sum += p;
                in.push(p);
            }
        }
        while (in_size() > _k) {
            T p = in.top();
            in.pop();
            if (!d_in.empty() && p == d_in.top()) {
                d_in.pop();
            } else {
                _sum -= p;
                out.push(p);
            }
        }
        while (!d_in.empty() && in.top() == d_in.top()) {
            in.pop();
            d_in.pop();
        }
    }
};
#line 11 "test/unit/top_k_sum.test.cpp"
template <class Compare>
void check(std::mt19937_64& rng, int iters, int ops, int vals) {
    for (int iter = 0; iter < iters; iter++) {
        int k = rng() % 6;
        top_k_sum<long long, Compare> s(k);
        std::vector<long long> v;
        for (int t = 0; t < ops; t++) {
            int c = rng() % 4;
            if (c == 0 || v.empty()) {
                long long x = rng() % vals;
                s.insert(x);
                v.push_back(x);
            } else if (c == 1) {
                int i = rng() % v.size();
                s.erase(v[i]);
                v.erase(v.begin() + i);
            } else if (c == 2) {
                k = rng() % 6;
                s.set_k(k);
            }
            std::vector<long long> w = v;
            std::sort(w.begin(), w.end(), Compare());
            long long expect = 0;
            for (int i = 0; i < std::min<int>(k, w.size()); i++) expect += w[i];
            assert(s.size() == int(v.size()));
            assert(s.k() == k);
            assert(s.sum() == expect);
        }
    }
}
int main() {
    std::mt19937_64 rng(20261027);
    check<std::greater<long long>>(rng, 300, 60, 5);
    check<std::greater<long long>>(rng, 300, 60, 1000);
    check<std::less<long long>>(rng, 300, 60, 5);
    check<std::less<long long>>(rng, 300, 60, 1000);
    {
        // k = 0 と k > size
        top_k_sum<int> s(0);
        s.insert(5);
        assert(s.sum() == 0);
        s.set_k(10);
        assert(s.sum() == 5);
        s.erase(5);
        assert(s.sum() == 0 && s.size() == 0);
    }
    {
        int n = 200000;
        auto start = std::chrono::steady_clock::now();
        top_k_sum<long long> s(n / 2);
        std::vector<long long> v(n);
        for (int i = 0; i < n; i++) {
            v[i] = rng() % 1000000000;
            s.insert(v[i]);
        }
        long long acc = 0;
        for (int i = 0; i < n; i++) {
            s.erase(v[i]);
            v[i] = rng() % 1000000000;
            s.insert(v[i]);
            s.set_k(s.k() + (i % 2 ? 1 : -1));
            acc = (acc + s.sum()) % 1000000007;
        }
        std::vector<long long> w = v;
        std::sort(w.begin(), w.end(), std::greater<long long>());
        long long expect = 0;
        for (int i = 0; i < s.k(); i++) expect += w[i];
        assert(s.sum() == expect);
        auto ms = std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::steady_clock::now() - start).count();
        std::cerr << "perf " << n << " ops: " << ms << " ms (" << acc % 1000 << ")\n";
    }
    std::cout << "Hello World\n";
}
Back to top page