cp-library-cpp

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

View the Project on GitHub suisen-cp/cp-library-cpp

:heavy_check_mark: test/src/util/step_sum/dummy.test.cpp

Depends on

Code

#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A"

#include <iostream>

#include "library/util/step_sum.hpp"

template <typename T>
struct StepSumNaive {
    template <typename Sequence>
    StepSumNaive(const Sequence& a, int step): _dat(a.begin(), a.end()), _step(step), _n(_dat.size()) {}
    T sum(int k, int l, int r) const {
        T ans = 0;
        for (int i = k; i < std::min(r, _n); i += _step) {
            if (i >= l) {
                ans += _dat[i];
            }
        }
        return ans;
    }
    T operator()(int k, int l, int r) const { return sum(k, l, r); }
private:
    std::vector<T> _dat;
    int _step, _n;
};
template <typename Sequence>
StepSumNaive(Sequence, int) -> StepSumNaive<typename Sequence::value_type>;

#include <cassert>
#include <random>

void test() {
    std::mt19937 rng{0};

    int n = 100, v = 10000000;
    std::vector<int> a(n);
    for (auto& e : a) e = rng() % v - v / 2;

    for (int step = 1; step <= n; ++step) {
        suisen::StepSum sum1(a, step);
        StepSumNaive sum2(a, step);
        for (int k = 0; k < step; ++k) {
            for (int l = -10; l <= n + 10; ++l) {
                for (int r = -10; r <= n + 10; ++r) {
                    if (sum1(k, l, r) != sum2(k, l, r)) {
                        for (int e : a) std::cerr << e << ",";
                        std::cerr << std::endl;
                        std::cerr << "step = " << step << std::endl;
                        std::cerr << "(k, l, r) = (" << k << ", " << l << ", " << r << ")" << std::endl;

                        std::cerr << "Actual  :" << sum1(k, l, r) << std::endl;
                        std::cerr << "Expected:" << sum2(k, l, r) << std::endl;
                        assert(false);
                    }
                }
            }
        }
    }
}

struct S {
    using value_type = int;
    std::vector<int> a;
    auto begin() const { return a.begin(); }
    auto end() const { return a.end(); }
};

int main() {
    suisen::StepSum sum(S{std::vector<int>{1}}, 2);
    suisen::StepSum sum2(std::vector<long long>{1}, 2);
    test();
    std::cout << "Hello World" << std::endl;
    return 0;
}
#line 1 "test/src/util/step_sum/dummy.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A"

#include <iostream>

#line 1 "library/util/step_sum.hpp"



#include <vector>

#line 1 "library/number/barrett_reduction.hpp"



#include <array>
#include <cassert>
#include <cstdint>
#include <utility>

namespace suisen {
    struct barrett {
        constexpr barrett() : M(1), L(0) {}
        constexpr explicit barrett(uint32_t M) : M(M), L(uint64_t(-1) / M + 1) { assert(M); }
        constexpr int32_t mod() { return M; }
        constexpr uint32_t umod() const { return M; }
        // floor(x/M) (correctly works for all 0<=x<2^64)
        template <bool care_M1 = true> constexpr uint64_t quo(uint64_t x) const { return quorem<care_M1>(x).first; }
        // x%M (correctly works for all 0<=x<2^64)
        template <bool care_M1 = true> constexpr uint32_t rem(uint64_t x) const { return quorem<care_M1>(x).second; }
        // { floor(x/M), x%M } (correctly works for all 0<=x<2^64)
        template <bool care_M1 = true> constexpr std::pair<uint64_t, uint32_t> quorem(uint64_t x) const {
            if constexpr (care_M1) if (M == 1) return { x, 0 };
            uint64_t q = (__uint128_t(x) * L) >> 64;
            int32_t r = x - q * M;
            if (r < 0) --q, r += M;
            return { q, uint32_t(r) };
        }
        // a*b mod M
        template <bool care_M1 = true> constexpr uint32_t mul(uint32_t a, uint32_t b) const { return rem<care_M1>(uint64_t(a) * b); }
    private:
        uint32_t M; // mod
        uint64_t L; // ceil(2^K / M), where K = 64 (if M != 1)
    };
} // namespace suisen



#line 7 "library/util/step_sum.hpp"

namespace suisen {
    template <typename T>
    struct StepSum {
        using value_type = T;

        StepSum() : StepSum(std::vector<value_type>{}, 1) {}
        template <typename Sequence>
        StepSum(const Sequence &a, int step) : _sum(a.begin(), a.end()), _step(step), _n(_sum.size()), _br(_step) {
            for (int i = _step; i < _n; ++i) {
                _sum[i] += _sum[i - _step];
            }
        }
        // sum A_i for i = k (mod step) and i in [l, r)
        value_type sum(int k, int l, int r) const {
            if (r <= k or r <= l or l >= _n) return 0;
            const int t = _br.quo(std::min(_n, r) - 1 - k);
            T ans = _sum[t * _step + k];
            if (l > k) {
                const int s = _br.quo(l - 1 - k);
                ans -= _sum[s * _step + k];
            }
            return ans;
        }
        // sum A_i for i = k (mod step) and i in [l, r)
        value_type operator()(int k, int l, int r) const { return sum(k, l, r); }

        // sum[i] = a[i] + a[i - step] + a[i - 2 * step] + ...
        std::vector<value_type>& data() { return _sum; }
        // sum[i] = a[i] + a[i - step] + a[i - 2 * step] + ...
        const std::vector<value_type>& data() const { return _sum; }
    private:
        std::vector<value_type> _sum;
        int _step, _n;
        barrett _br;
    };
    template <typename Sequence>
    StepSum(Sequence, int) -> StepSum<std::decay_t<decltype(*std::declval<Sequence>().begin())>>;
} // namespace suisen



#line 6 "test/src/util/step_sum/dummy.test.cpp"

template <typename T>
struct StepSumNaive {
    template <typename Sequence>
    StepSumNaive(const Sequence& a, int step): _dat(a.begin(), a.end()), _step(step), _n(_dat.size()) {}
    T sum(int k, int l, int r) const {
        T ans = 0;
        for (int i = k; i < std::min(r, _n); i += _step) {
            if (i >= l) {
                ans += _dat[i];
            }
        }
        return ans;
    }
    T operator()(int k, int l, int r) const { return sum(k, l, r); }
private:
    std::vector<T> _dat;
    int _step, _n;
};
template <typename Sequence>
StepSumNaive(Sequence, int) -> StepSumNaive<typename Sequence::value_type>;

#line 29 "test/src/util/step_sum/dummy.test.cpp"
#include <random>

void test() {
    std::mt19937 rng{0};

    int n = 100, v = 10000000;
    std::vector<int> a(n);
    for (auto& e : a) e = rng() % v - v / 2;

    for (int step = 1; step <= n; ++step) {
        suisen::StepSum sum1(a, step);
        StepSumNaive sum2(a, step);
        for (int k = 0; k < step; ++k) {
            for (int l = -10; l <= n + 10; ++l) {
                for (int r = -10; r <= n + 10; ++r) {
                    if (sum1(k, l, r) != sum2(k, l, r)) {
                        for (int e : a) std::cerr << e << ",";
                        std::cerr << std::endl;
                        std::cerr << "step = " << step << std::endl;
                        std::cerr << "(k, l, r) = (" << k << ", " << l << ", " << r << ")" << std::endl;

                        std::cerr << "Actual  :" << sum1(k, l, r) << std::endl;
                        std::cerr << "Expected:" << sum2(k, l, r) << std::endl;
                        assert(false);
                    }
                }
            }
        }
    }
}

struct S {
    using value_type = int;
    std::vector<int> a;
    auto begin() const { return a.begin(); }
    auto end() const { return a.end(); }
};

int main() {
    suisen::StepSum sum(S{std::vector<int>{1}}, 2);
    suisen::StepSum sum2(std::vector<long long>{1}, 2);
    test();
    std::cout << "Hello World" << std::endl;
    return 0;
}
Back to top page