// Cuántos elementos deja a cada lado el pivote de la mediana de medianas, con varios tipos de entrada.
#include <algorithm>
#include <cstdio>
#include <random>
#include <string>
#include <utility>
#include <vector>

#include "select.h"

static void report(const std::string& name, const std::vector<int>& a) {
    long long comparisons = 0;
    int pivot = median_of_medians(a, comparisons);
    auto at_most = std::count_if(a.begin(), a.end(), [&](int x) { return x <= pivot; });
    auto at_least = std::count_if(a.begin(), a.end(), [&](int x) { return x >= pivot; });
    std::printf("%-20s %8ld %8ld\n", name.c_str(), static_cast<long>(at_most), static_cast<long>(at_least));
}

int main() {
    const int n = 1000;
    std::mt19937 rng(2026);
    std::vector<std::pair<std::string, std::vector<int>>> inputs;

    std::vector<int> random_values(n);
    for (int& x : random_values) {
        x = static_cast<int>(rng() % 1000000);
    }
    inputs.push_back({"al azar", random_values});

    std::vector<int> sorted(n);
    for (int i = 0; i < n; i++) {
        sorted[i] = i;
    }
    inputs.push_back({"ordenado", sorted});

    inputs.push_back({"todos iguales", std::vector<int>(n, 7)});

    std::vector<int> few(n);
    for (int& x : few) {
        x = static_cast<int>(rng() % 3);
    }
    inputs.push_back({"tres valores", few});

    inputs.push_back({"construida", tight_input(n)});

    std::printf("n = %d, cota 3n/10 - 3 = %d\n", n, 3 * n / 10 - 3);
    std::printf("%-20s %8s %8s\n", "entrada", "<= piv", ">= piv");
    for (const auto& [name, values] : inputs) {
        report(name, values);
    }
}