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/Number/EnumerateQuotients/ceilBuild.test.cpp

Depends on

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A"

#include "../../../../Src/Template/TypeAlias.hpp"
#include "../../../../Src/Number/EnumerateQuotients.hpp"

#include <cassert>
#include <iostream>
#include <random>

using namespace zawa;

void test(u32 n) {
    EnumerateQuotients q(n, false);
    bool ok{true};
    for (const auto& dat : q) {
        for (u32 i{dat.l()} ; i < dat.r() ; i++) {
            ok &= i * dat.quotient() >= q.n();
            ok &= i * (dat.quotient() - 1) < q.n();
        }
    }
    if (not ok) {
        std::cerr << n << " failed!!!" << std::endl;
        assert(false);
    }
    else {
        std::cerr << n << " ok!!!" << std::endl;
    }
}

int main() {
    std::mt19937 mt{ std::random_device{}() };
    test(0);
    test(1);
    test(2);
    for (u32 i{} ; i < 100 ; i++) {
        test(mt() % (u32)1e6);
    }
    std::cout << "Hello World" << std::endl;
}
#line 1 "Test/My/Number/EnumerateQuotients/ceilBuild.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A"

#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 2 "Src/Number/EnumerateQuotients.hpp"

#line 2 "Src/Number/IntegerDivision.hpp"

#include <type_traits>
#include <cassert>

namespace zawa {

template <class T>
constexpr T DivFloor(T a, T b) {
    static_assert(std::is_integral_v<T>, "DivFloor argument must be Integer");
    assert(b != T{});
    if constexpr (std::is_unsigned_v<T>) {
        return a / b;
    }
    else {
        if (b < 0) {
            a *= -1;
            b *= -1;
        }
        return (a >= 0 ? a / b : (a - b + 1) / b);
    }
}

template <class T>
constexpr T DivCeil(T a, T b) {
    static_assert(std::is_integral_v<T>, "DivCeil argument must be Integer");
    assert(b != T{});
    if constexpr (std::is_unsigned_v<T>) {
        return (a + b - 1) / b;
    }
    else {
        if (b < 0) {
            a *= -1;
            b *= -1;
        }
        return (a >= 0 ? (a + b - 1) / b : a / b);
    }
}

} // namespace zawa
#line 5 "Src/Number/EnumerateQuotients.hpp"

#line 7 "Src/Number/EnumerateQuotients.hpp"
#include <vector>
#include <utility>
#line 10 "Src/Number/EnumerateQuotients.hpp"

namespace zawa {

template <class Value>
class EnumerateQuotients {
public:
    class Data {
    private:
        Value quotient_;
        Value l_, r_;
    public:
        Data() = default;
        constexpr Data(Value quotient, Value l, Value r) : quotient_{ quotient }, l_{ l }, r_{ r } {
            assert(l < r);
        }
        
        constexpr Value quotient() const noexcept {
            return quotient_;
        }

        constexpr Value l() const noexcept {
            return l_;
        }

        constexpr Value r() const noexcept {
            return r_;
        }

        constexpr std::pair<Value, Value> range() const noexcept {
            return std::pair{ l_, r_ };
        }

        constexpr Value len() const noexcept {
            return r_ - l_;
        }
    };

private:
    std::vector<Data> seq_;
    Value n_;

    constexpr void templateTypeAssert() const noexcept {
        static_assert(std::is_integral_v<Value>, "Template argument must be unsigned integer type.");
        static_assert(std::is_unsigned_v<Value>, "Template argument must be unsigned integer type.");
    }

    constexpr void floorBuild() noexcept {
        Value l{1U};
        while (l <= n_) {
            Value quotient{ DivFloor(n_, l) };
            Value r{ DivFloor(n_, quotient) + 1 };
            seq_.emplace_back(quotient, l, r);
            l = r;
        } 
    }

    constexpr void ceilBuild() noexcept {
        Value l{1U};
        while (l < n_) {
            Value quotient{ DivCeil(n_, l) };
            Value r{ DivCeil(n_, quotient - 1) };
            seq_.emplace_back(quotient, l, r);
            l = r;
        }
        if (n_) {
            seq_.emplace_back(1U, n_, n_ + 1);
        }
    }

public:
    constexpr EnumerateQuotients() : seq_{}, n_{} {
        templateTypeAssert();
    }

    constexpr EnumerateQuotients(Value n, bool floor = true) : seq_{}, n_{ n } {
        templateTypeAssert();
        floor ? floorBuild() : ceilBuild();
        seq_.shrink_to_fit();
    }

    constexpr Value n() const noexcept {
        return n_;
    }

    constexpr Data operator[](u32 i) const noexcept {
        return seq_[i];
    }

    constexpr Value quotient(u32 i) const noexcept {
        assert(i < seq_.size()); 
        return seq_[i].quotient();
    }

    constexpr Value l(u32 i) const noexcept {
        assert(i < seq_.size()); 
        return seq_[i].l();
    }

    constexpr Value r(u32 i) const noexcept {
        assert(i < seq_.size()); 
        return seq_[i].r();
    }

    constexpr std::pair<Value, Value> range(u32 i) const noexcept {
        assert(i < seq_.size());
        return std::move(seq_[i].range());
    }

    constexpr Value len(u32 i) const noexcept {
        assert(i < seq_.size());
        return seq_[i].len();
    }

    constexpr usize size() const noexcept {
        return seq_.size();
    }

    constexpr typename decltype(seq_)::const_iterator begin() const noexcept {
        return seq_.begin();
    }

    constexpr typename decltype(seq_)::const_iterator end() const noexcept {
        return seq_.end();
    }

};

} // namespace zawa
#line 5 "Test/My/Number/EnumerateQuotients/ceilBuild.test.cpp"

#line 7 "Test/My/Number/EnumerateQuotients/ceilBuild.test.cpp"
#include <iostream>
#include <random>

using namespace zawa;

void test(u32 n) {
    EnumerateQuotients q(n, false);
    bool ok{true};
    for (const auto& dat : q) {
        for (u32 i{dat.l()} ; i < dat.r() ; i++) {
            ok &= i * dat.quotient() >= q.n();
            ok &= i * (dat.quotient() - 1) < q.n();
        }
    }
    if (not ok) {
        std::cerr << n << " failed!!!" << std::endl;
        assert(false);
    }
    else {
        std::cerr << n << " ok!!!" << std::endl;
    }
}

int main() {
    std::mt19937 mt{ std::random_device{}() };
    test(0);
    test(1);
    test(2);
    for (u32 i{} ; i < 100 ; i++) {
        test(mt() % (u32)1e6);
    }
    std::cout << "Hello World" << std::endl;
}
Back to top page