test/auto_memoize.test.cpp

View this file on GitHub
Last update: 2022-09-27 19:53:51+09:00
Problem: https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/all/ALDS1_10_A

Depends on

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/all/ALDS1_10_A"
#include "../utility/int_alias.cpp"
#include "../utility/auto_memoize.cpp"
#include <iostream>

int main() {
    u64 x;
    std::cin >> x;
    std::cout << auto_memoize([](auto&& fib, const u64 x) -> u64 {
        if (x <= 1) return 1;
        return fib(x - 1) + fib(x - 2);
    })(x) << '\n';
    return 0;
}

#line 1 "test/auto_memoize.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/all/ALDS1_10_A"
#line 2 "utility/int_alias.cpp"
#include <cstdint>

using i32 = std::int32_t;
using u32 = std::uint32_t;
using i64 = std::int64_t;
using u64 = std::uint64_t;
using i128 = __int128_t;
using u128 = __uint128_t;
#line 2 "utility/auto_memoize.cpp"
#include <map>
#include <tuple>
#include <type_traits>
#include <utility>

template <class F> class AutoMemoization {
    template <class> struct GetSig;
    template <class T, class R, class S, class... Args> struct GetSig<R (T::*)(S, Args...) const> {
        using Ret = R;
        using Tuple = std::tuple<std::decay_t<Args>...>;
    };

    using Sig = GetSig<decltype(&F::template operator()<AutoMemoization<F>&>)>;
    using R = typename Sig::Ret;
    using Tuple = typename Sig::Tuple;

    F func;
    mutable std::map<Tuple, R> data;

    template <std::size_t... I> R apply(const Tuple& args_tuple, std::index_sequence<I...>) const {
        return func(*this, std::get<I>(args_tuple)...);
    }

  public:
    explicit AutoMemoization(F&& f) : func(std::forward<F>(f)) {}

    template <class... Args> R operator()(Args&&... args) const {
        Tuple tup(std::forward<Args>(args)...);
        const auto itr = data.find(tup);
        if (itr != data.end()) return itr->second;
        R ret = apply(tup, std::make_index_sequence<std::tuple_size_v<Tuple>>());
        data.emplace(std::move(tup), ret);
        return ret;
    }
};

template <class F> decltype(auto) auto_memoize(F&& f) { return AutoMemoization<F>(std::forward<F>(f)); }
#line 4 "test/auto_memoize.test.cpp"
#include <iostream>

int main() {
    u64 x;
    std::cin >> x;
    std::cout << auto_memoize([](auto&& fib, const u64 x) -> u64 {
        if (x <= 1) return 1;
        return fib(x - 1) + fib(x - 2);
    })(x) << '\n';
    return 0;
}