// Mide las dos versiones de la subsecuencia creciente más larga. Menor de 3 intentos, con -O2.
#include <chrono>
#include <cstdio>
#include <random>
#include <vector>

#include "lis.h"

namespace {

std::vector<int> random_values(std::size_t n, unsigned seed) {
    std::mt19937 rng(seed);
    std::vector<int> a(n);
    for (int& x : a) x = static_cast<int>(rng() >> 2);
    return a;
}

template <typename Function>
double best_ms(Function run) {
    double best = 1e18;
    for (int attempt = 0; attempt < 3; attempt++) {
        const auto start = std::chrono::steady_clock::now();
        run();
        const auto stop = std::chrono::steady_clock::now();
        best = std::min(best, std::chrono::duration<double, std::milli>(stop - start).count());
    }
    return best;
}

}  // namespace

int main() {
    std::puts("Subsecuencia creciente más larga, valores al azar, menor de 3 intentos");
    std::puts("        n   largo   tabla ms   finales ms");
    for (std::size_t n : {10000u, 20000u, 40000u, 80000u, 1000000u, 2000000u, 4000000u}) {
        const std::vector<int> a = random_values(n, 9);
        std::size_t length = 0;
        const double fast = best_ms([&] { length = lis_length_tails(a); });
        if (n <= 80000u) {
            int slow_length = 0;
            const double slow = best_ms([&] { slow_length = lis_length_quadratic(a); });
            if (slow_length != static_cast<int>(length)) return 1;
            std::printf("%9zu %7zu %10.1f %12.1f\n", n, length, slow, fast);
        } else {
            std::printf("%9zu %7zu %10s %12.1f\n", n, length, "-", fast);
        }
    }
}