// Dos búsquedas binarias equivocadas: una no da el resultado y la otra no termina.
#include <iostream>
#include <vector>

#include "search.h"

int main() {
    std::vector<int> a = {2, 4, 6, 8, 10};
    std::cout << "buscar 10 en {2, 4, 6, 8, 10}\n";
    std::cout << "  correcta: " << first_at_least(a, 10) << '\n';
    std::cout << "  invariante débil: " << search_weak_invariant(a, 10) << '\n';

    std::vector<int> b = {2, 4};
    std::cout << "buscar 9 en {2, 4}\n";
    std::cout << "  correcta: " << first_at_least(b, 9) << '\n';
    std::cout << "  con lo = mid: " << search_lo_is_mid(b, 9, 1000) << " (cortada a las 1000 vueltas)\n";
}

// La idea parecida que falla: el asesor se queda con la primera oferta y nunca cambia.
#include <iostream>

#include "instances.h"

int main() {
    Preferences students = example_students();
    Preferences advisors = example_advisors();
    std::vector<int> partner = first_offer_matching(students);
    std::cout << "primera oferta:";
    for (int p = 0; p < static_cast<int>(partner.size()); p++) {
        std::cout << " t" << p << "-a" << partner[p];
    }
    std::cout << '\n';
    auto unstable = find_unstable_pair(partner, students, advisors);
    if (unstable) {
        std::cout << "par inestable: t" << unstable->first << " y a" << unstable->second << '\n';
    } else {
        std::cout << "sin pares inestables\n";
    }
}

// Las instancias que siguen los apuntes.
#ifndef INSTANCES_H
#define INSTANCES_H

#include "matching.h"

// El ejemplo con cuatro tesistas y cuatro asesores.
inline Preferences example_students() {
    return {{1, 0, 2, 3}, {1, 2, 0, 3}, {0, 1, 3, 2}, {0, 3, 2, 1}};
}
inline Preferences example_advisors() {
    return {{0, 3, 2, 1}, {1, 0, 2, 3}, {0, 1, 2, 3}, {3, 2, 0, 1}};
}

// Dos tesistas y dos asesores que no coinciden en nada: hay dos matchings estables.
inline Preferences crossed_students() {
    return {{0, 1}, {1, 0}};
}
inline Preferences crossed_advisors() {
    return {{1, 0}, {0, 1}};
}

// Todos los proponentes tienen la misma lista, y todos los receptores prefieren al último
// que llega. Obliga a hacer n(n + 1)/2 propuestas, cada una con una comparación cara.
inline Preferences same_list_proposers(int n) {
    std::vector<int> list(n);
    for (int i = 0; i < n; i++) list[i] = i;
    return Preferences(n, list);
}
inline Preferences latest_wins_receivers(int n) {
    std::vector<int> list(n);
    for (int i = 0; i < n; i++) list[i] = n - 1 - i;
    return Preferences(n, list);
}

// Listas al azar, con semilla fija. Usa std::mt19937 directamente: da lo mismo en toda máquina.
inline Preferences random_preferences(int n, std::mt19937& gen) {
    Preferences prefs(n, std::vector<int>(n));
    for (auto& list : prefs) {
        for (int i = 0; i < n; i++) list[i] = i;
        for (int i = n - 1; i > 0; i--) {
            int j = static_cast<int>(gen() % static_cast<unsigned>(i + 1));
            std::swap(list[i], list[j]);
        }
    }
    return prefs;
}

#endif

// Matching estable uno a uno: n proponentes y n receptores con listas completas y estrictas.
#ifndef MATCHING_H
#define MATCHING_H

#include <algorithm>
#include <numeric>
#include <optional>
#include <random>
#include <utility>
#include <vector>

// prefs[i] es la lista de i, de la opción que más quiere a la que menos quiere.
using Preferences = std::vector<std::vector<int>>;

struct Matching {
    std::vector<int> partner;  // partner[p]: el receptor que le toca al proponente p
    long long proposals = 0;
};

// rank[r][p]: la posición de p en la lista de r. Una posición menor significa que r lo prefiere.
inline std::vector<std::vector<int>> rank_table(const Preferences& prefs) {
    int n = static_cast<int>(prefs.size());
    std::vector<std::vector<int>> rank(n, std::vector<int>(n));
    for (int r = 0; r < n; r++) {
        for (int position = 0; position < n; position++) {
            rank[r][prefs[r][position]] = position;
        }
    }
    return rank;
}

// El ciclo de Gale-Shapley. prefers(r, a, b) dice si r prefiere a a b, y
// on_proposal(p, r, held_before, accepted) se llama después de cada propuesta.
// Invariantes: holder y partner dicen lo mismo, y la pareja de un receptor solo mejora.
template <typename Prefers, typename OnProposal>
Matching propose_until_stable(const Preferences& proposer_prefs, Prefers prefers, OnProposal on_proposal) {
    int n = static_cast<int>(proposer_prefs.size());
    std::vector<int> next_choice(n, 0);
    std::vector<int> holder(n, -1);  // holder[r]: a quién tiene r por ahora, o -1
    std::vector<int> free_proposers;
    for (int p = n - 1; p >= 0; p--) {
        free_proposers.push_back(p);
    }
    long long proposals = 0;
    while (!free_proposers.empty()) {
        int p = free_proposers.back();
        free_proposers.pop_back();
        int r = proposer_prefs[p][next_choice[p]];
        next_choice[p]++;
        proposals++;
        int held = holder[r];
        if (held == -1) {
            holder[r] = p;
        } else if (prefers(r, p, held)) {
            holder[r] = p;
            free_proposers.push_back(held);
        } else {
            free_proposers.push_back(p);
        }
        on_proposal(p, r, held, holder[r] == p);
    }
    Matching result;
    result.partner.assign(n, -1);
    for (int r = 0; r < n; r++) {
        result.partner[holder[r]] = r;
    }
    result.proposals = proposals;
    return result;
}

// Con tabla de rangos: cada comparación cuesta O(1). Total O(n²).
inline Matching gale_shapley(const Preferences& proposer_prefs, const Preferences& receiver_prefs) {
    std::vector<std::vector<int>> rank = rank_table(receiver_prefs);
    return propose_until_stable(
        proposer_prefs,
        [&](int r, int a, int b) { return rank[r][a] < rank[r][b]; },
        [](int, int, int, bool) {});
}

// Sin tabla: cada comparación recorre la lista del receptor. En steps suma las casillas que miró.
inline Matching gale_shapley_scan(const Preferences& proposer_prefs, const Preferences& receiver_prefs,
                                  long long& steps) {
    auto prefers = [&](int r, int a, int b) {
        for (int candidate : receiver_prefs[r]) {
            steps++;
            if (candidate == a) return true;
            if (candidate == b) return false;
        }
        return false;
    };
    return propose_until_stable(proposer_prefs, prefers, [](int, int, int, bool) {});
}

// Un par inestable: p y r no están juntos, y cada uno prefiere al otro antes que a su pareja.
// Devuelve el primero, por p y luego en el orden de la lista de p, si hay alguno.
inline std::optional<std::pair<int, int>> find_unstable_pair(const std::vector<int>& partner,
                                                             const Preferences& proposer_prefs,
                                                             const Preferences& receiver_prefs) {
    int n = static_cast<int>(partner.size());
    std::vector<std::vector<int>> rank = rank_table(receiver_prefs);
    std::vector<int> holder(n);
    for (int p = 0; p < n; p++) {
        holder[partner[p]] = p;
    }
    for (int p = 0; p < n; p++) {
        for (int r : proposer_prefs[p]) {
            if (r == partner[p]) {
                break;  // de aquí en adelante, p prefiere a su pareja
            }
            if (rank[r][p] < rank[r][holder[r]]) {
                return std::pair{p, r};
            }
        }
    }
    return std::nullopt;
}

// Todos los matchings estables, probando las n! permutaciones. Solo sirve con n pequeño.
inline std::vector<std::vector<int>> all_stable_matchings(const Preferences& proposer_prefs,
                                                          const Preferences& receiver_prefs) {
    std::vector<int> partner(proposer_prefs.size());
    std::iota(partner.begin(), partner.end(), 0);
    std::vector<std::vector<int>> stable;
    do {
        if (!find_unstable_pair(partner, proposer_prefs, receiver_prefs)) {
            stable.push_back(partner);
        }
    } while (std::next_permutation(partner.begin(), partner.end()));
    return stable;
}

// Mal: el receptor se queda con la primera oferta que recibe y nunca cambia.
inline std::vector<int> first_offer_matching(const Preferences& proposer_prefs) {
    int n = static_cast<int>(proposer_prefs.size());
    std::vector<bool> taken(n, false);
    std::vector<int> partner(n, -1);
    for (int p = 0; p < n; p++) {
        for (int r : proposer_prefs[p]) {
            if (!taken[r]) {
                taken[r] = true;
                partner[p] = r;
                break;
            }
        }
    }
    return partner;
}

// Un paso de "arreglar el par inestable": p y r se juntan, y sus dos ex parejas también.
inline void repair_pair(std::vector<int>& partner, int p, int r) {
    int other = static_cast<int>(std::find(partner.begin(), partner.end(), r) - partner.begin());
    partner[other] = partner[p];
    partner[p] = r;
}

#endif

// Potencia rápida, recursiva.
#ifndef POWER_H
#define POWER_H

// Devuelve b^e mod m, con e >= 0, b >= 0 y 1 <= m <= 2^31.
// Como cada factor es menor que m, un producto es menor que 2^62 y cabe en long long.
// Si multiplications no es nulo, le suma cuántos productos se hicieron.
inline long long power_mod(long long b, long long e, long long m, long long* multiplications = nullptr) {
    if (e == 0) {
        return 1 % m;
    }
    long long half = power_mod(b, e / 2, m, multiplications);
    long long result = half * half % m;
    if (multiplications) (*multiplications)++;
    if (e % 2 == 1) {
        result = result * (b % m) % m;
        if (multiplications) (*multiplications)++;
    }
    return result;
}

#endif

// Mide Gale-Shapley con tabla de rangos y recorriendo la lista. Compilar con -O2 y sin sanitizers.
#include <algorithm>
#include <chrono>
#include <iomanip>
#include <iostream>
#include <vector>

#include "instances.h"

namespace {

// Corre fn `reps` veces y devuelve la mediana en segundos.
template <typename Fn>
double median_seconds(int reps, Fn fn) {
    std::vector<double> times;
    for (int i = 0; i < reps; i++) {
        auto start = std::chrono::steady_clock::now();
        fn();
        auto stop = std::chrono::steady_clock::now();
        times.push_back(std::chrono::duration<double>(stop - start).count());
    }
    std::sort(times.begin(), times.end());
    return times[times.size() / 2];
}

void print_ratio(double now, double before) {
    if (before > 0) {
        std::cout << std::setprecision(1) << std::setw(7) << now / before;
    } else {
        std::cout << std::setw(7) << "-";
    }
}

}  // namespace

int main() {
    std::cout << "    n   tabla (s)  razón  ns/propuesta   lista (s)  razón  ns/casilla  lista/tabla\n";
    double previous_table = 0;
    double previous_scan = 0;
    int total = 0;
    for (int n : {500, 1000, 2000, 4000}) {
        Preferences proposers = same_list_proposers(n);
        Preferences receivers = latest_wins_receivers(n);
        long long proposals = 0;
        double table = median_seconds(5, [&] {
            Matching result = gale_shapley(proposers, receivers);
            proposals = result.proposals;
            total += result.partner[0];
        });
        long long steps = 0;
        double scan = median_seconds(3, [&] {
            steps = 0;
            total += gale_shapley_scan(proposers, receivers, steps).partner[0];
        });
        std::cout << std::fixed << std::setw(5) << n << std::setprecision(4) << std::setw(12) << table;
        print_ratio(table, previous_table);
        std::cout << std::setprecision(1) << std::setw(14) << table * 1e9 / static_cast<double>(proposals)
                  << std::setprecision(4) << std::setw(12) << scan;
        print_ratio(scan, previous_scan);
        std::cout << std::setprecision(2) << std::setw(12) << scan * 1e9 / static_cast<double>(steps)
                  << std::setprecision(0) << std::setw(13) << scan / table << '\n';
        previous_table = table;
        previous_scan = scan;
    }
    // Se imprime para que el compilador no pueda borrar los cálculos.
    std::cerr << "control: " << total << '\n';
}

// Cuenta propuestas y casillas miradas, sin reloj: estos números no dependen de la máquina.
#include <iomanip>
#include <iostream>
#include <random>

#include "instances.h"

namespace {

void row(const char* name, int n, const Preferences& proposers, const Preferences& receivers) {
    long long steps = 0;
    Matching result = gale_shapley_scan(proposers, receivers, steps);
    std::cout << std::left << std::setw(11) << name << std::right << std::setw(6) << n
              << std::setw(11) << result.proposals << std::setw(14) << steps << '\n';
}

}  // namespace

int main() {
    std::cout << "instancia      n  propuestas  casillas\n";
    for (int n : {250, 500, 1000, 2000}) {
        row("adversa", n, same_list_proposers(n), latest_wins_receivers(n));
    }
    std::mt19937 gen(2026);
    for (int n : {250, 500, 1000, 2000}) {
        Preferences proposers = random_preferences(n, gen);
        Preferences receivers = random_preferences(n, gen);
        row("al azar", n, proposers, receivers);
    }
}

// Otra idea que falla: tomar el primer par inestable y juntarlo, hasta que no quede ninguno.
#include <iostream>
#include <vector>

#include "matching.h"

int main() {
    Preferences students = {{0, 1, 2, 3}, {2, 3, 1, 0}, {0, 3, 1, 2}, {2, 0, 1, 3}};
    Preferences advisors = {{1, 3, 2, 0}, {3, 1, 0, 2}, {0, 2, 3, 1}, {0, 2, 1, 3}};
    std::vector<int> partner = {0, 1, 2, 3};
    std::vector<std::vector<int>> seen;
    while (std::find(seen.begin(), seen.end(), partner) == seen.end()) {
        seen.push_back(partner);
        for (int r : partner) {
            std::cout << 'a' << r << ' ';
        }
        auto unstable = find_unstable_pair(partner, students, advisors);
        if (!unstable) {
            std::cout << "estable\n";
            return 0;
        }
        std::cout << "par inestable: t" << unstable->first << " y a" << unstable->second << '\n';
        repair_pair(partner, unstable->first, unstable->second);
    }
    std::cout << "volvimos a:";
    for (int r : partner) {
        std::cout << " a" << r;
    }
    std::cout << "\nmatchings estables de esta instancia: " << all_stable_matchings(students, advisors).size() << '\n';
}

// Búsqueda binaria sobre un rango semiabierto [lo, hi), y dos versiones que fallan.
#ifndef SEARCH_H
#define SEARCH_H

#include <cassert>
#include <ostream>
#include <vector>

// Devuelve el primer índice i con a[i] >= x, o a.size() si no hay ninguno.
// Requiere que a esté ordenado de menor a mayor.
// Invariante: todo a[i] con i < lo es menor que x, y todo a[i] con i >= hi es mayor o igual que x.
inline int first_at_least(const std::vector<int>& a, int x) {
    int lo = 0;
    int hi = static_cast<int>(a.size());
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] < x) {
            lo = mid + 1;
        } else {
            hi = mid;
        }
    }
    return lo;
}

// La misma búsqueda, comprobando en cada vuelta la invariante entera y que hi - lo baja.
// Si recibe un flujo, escribe una línea por vuelta.
inline int first_at_least_checked(const std::vector<int>& a, int x, std::ostream* log) {
    const int n = static_cast<int>(a.size());
    int lo = 0;
    int hi = n;
    auto check = [&] {
        assert(0 <= lo && lo <= hi && hi <= n);
        for (int i = 0; i < lo; i++) assert(a[i] < x);
        for (int i = hi; i < n; i++) assert(a[i] >= x);
    };
    check();
    while (lo < hi) {
        int size_before = hi - lo;
        int mid = lo + (hi - lo) / 2;
        if (log) *log << lo << ' ' << hi << ' ' << mid << ' ' << a[mid] << '\n';
        if (a[mid] < x) {
            lo = mid + 1;
        } else {
            hi = mid;
        }
        check();
        assert(hi - lo < size_before);
    }
    assert(lo == hi);
    return lo;
}

// Mal: conserva "todo a[i] con i < lo es menor que x", termina, y aun así no da el resultado.
inline int search_weak_invariant(const std::vector<int>& a, int x) {
    int lo = 0;
    int hi = static_cast<int>(a.size());
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] < x) {
            lo = mid + 1;
        } else {
            hi = lo;
        }
    }
    return lo;
}

// Mal: con lo = mid, el rango puede dejar de achicarse. Devuelve -1 si se pasa de max_steps,
// para que el ejemplo no se quede colgado.
inline int search_lo_is_mid(const std::vector<int>& a, int x, int max_steps) {
    int lo = 0;
    int hi = static_cast<int>(a.size());
    for (int step = 0; lo < hi; step++) {
        if (step == max_steps) return -1;
        int mid = lo + (hi - lo) / 2;
        if (a[mid] < x) {
            lo = mid;
        } else {
            hi = mid;
        }
    }
    return lo;
}

#endif

// Un programa equivocado que pasa 1000 pruebas al azar.
#include <algorithm>
#include <iostream>
#include <random>
#include <vector>

// Mal: empieza en 0, así que nunca devuelve un máximo negativo.
int maximum_wrong(const std::vector<int>& a) {
    int best = 0;
    for (int value : a) {
        if (value > best) {
            best = value;
        }
    }
    return best;
}

int main() {
    std::mt19937 gen(2026);
    int passed = 0;
    for (int test = 0; test < 1000; test++) {
        std::vector<int> a(1 + gen() % 100);
        for (int& value : a) {
            value = static_cast<int>(1 + gen() % 1000000);
        }
        if (maximum_wrong(a) == *std::max_element(a.begin(), a.end())) {
            passed++;
        }
    }
    std::cout << "pruebas al azar con valores positivos: " << passed << " de 1000 correctas\n";

    std::vector<int> negatives = {-5, -2, -9};
    std::cout << "con {-5, -2, -9}: devuelve " << maximum_wrong(negatives)
              << ", y el máximo es " << *std::max_element(negatives.begin(), negatives.end()) << '\n';
}

// Sigue Gale-Shapley propuesta por propuesta sobre el ejemplo de los apuntes.
#include <iostream>

#include "instances.h"

int main() {
    Preferences students = example_students();
    Preferences advisors = example_advisors();
    std::vector<std::vector<int>> rank = rank_table(advisors);
    int step = 0;
    Matching result = propose_until_stable(
        students,
        [&](int r, int a, int b) { return rank[r][a] < rank[r][b]; },
        [&](int p, int r, int held, bool accepted) {
            std::cout << ++step << ": t" << p << " propone a a" << r;
            if (held == -1) {
                std::cout << ", que estaba libre: acepta\n";
            } else if (accepted) {
                std::cout << ", que cambia a t" << held << " por t" << p << '\n';
            } else {
                std::cout << ", que se queda con t" << held << '\n';
            }
        });
    std::cout << "resultado:";
    for (int p = 0; p < static_cast<int>(result.partner.size()); p++) {
        std::cout << " t" << p << "-a" << result.partner[p];
    }
    std::cout << "\npropuestas: " << result.proposals << '\n';
    std::cout << "pares inestables: "
              << (find_unstable_pair(result.partner, students, advisors) ? "hay" : "ninguno") << '\n';
}

// Sigue la potencia rápida, y cuenta productos contra el método de multiplicar e veces.
#include <iostream>

#include "power.h"

int main() {
    const long long b = 3;
    const long long m = 1000;
    std::cout << "e  3^e mod 1000  productos\n";
    for (long long e : {0, 1, 3, 6, 13}) {
        long long multiplications = 0;
        long long result = power_mod(b, e, m, &multiplications);
        std::cout << e << "  " << result << "  " << multiplications << '\n';
    }
    long long multiplications = 0;
    long long big = power_mod(2, 1000000000, 1000000007, &multiplications);
    std::cout << "2^1000000000 mod 1000000007 = " << big << " con " << multiplications << " productos\n";
}

// Sigue la búsqueda binaria vuelta por vuelta. La versión con comprobación revisa la invariante.
#include <iostream>
#include <vector>

#include "search.h"

int main() {
    std::vector<int> a = {3, 7, 7, 12, 15, 20, 28, 31};
    for (int x : {7, 16, 40, 1}) {
        std::cout << "x = " << x << " (lo hi mid a[mid])\n";
        int result = first_at_least_checked(a, x, &std::cout);
        std::cout << "resultado: " << result << '\n';
    }
}

// Dos matchings estables en la instancia cruzada: cuál sale depende de quién propone.
#include <iostream>

#include "instances.h"

namespace {

void print_pairs(const char* title, const std::vector<int>& partner) {
    std::cout << title;
    for (int t = 0; t < static_cast<int>(partner.size()); t++) {
        std::cout << " t" << t << "-a" << partner[t];
    }
    std::cout << '\n';
}

// Convierte "a qué tesista le toca cada asesor" en "a qué asesor le toca cada tesista".
std::vector<int> inverted(const std::vector<int>& partner) {
    std::vector<int> result(partner.size());
    for (int i = 0; i < static_cast<int>(partner.size()); i++) {
        result[partner[i]] = i;
    }
    return result;
}

void compare(const Preferences& students, const Preferences& advisors) {
    for (const std::vector<int>& stable : all_stable_matchings(students, advisors)) {
        print_pairs("  estable:", stable);
    }
    print_pairs("  proponen los tesistas:", gale_shapley(students, advisors).partner);
    print_pairs("  proponen los asesores:", inverted(gale_shapley(advisors, students).partner));
}

}  // namespace

int main() {
    std::cout << "instancia cruzada\n";
    compare(crossed_students(), crossed_advisors());
    std::cout << "ejemplo de cuatro\n";
    compare(example_students(), example_advisors());
}

// Comprueba lo que afirman los apuntes. Corre con ASan y UBSan.
#include <algorithm>
#include <cassert>
#include <iostream>
#include <random>
#include <vector>

#include "instances.h"
#include "power.h"
#include "search.h"

namespace {

// Todas las búsquedas sobre arreglos ordenados, con repetidos y sin ellos.
void test_binary_search() {
    std::mt19937 gen(1);
    for (int n = 0; n <= 40; n++) {
        for (int round = 0; round < 30; round++) {
            std::vector<int> a(n);
            for (int& value : a) {
                value = static_cast<int>(gen() % 25);
            }
            std::sort(a.begin(), a.end());
            for (int x = -1; x <= 26; x++) {
                int expected = static_cast<int>(std::lower_bound(a.begin(), a.end(), x) - a.begin());
                assert(first_at_least(a, x) == expected);
                assert(first_at_least_checked(a, x, nullptr) == expected);
            }
        }
    }
}

void test_wrong_searches() {
    std::vector<int> a = {2, 4, 6, 8, 10};
    assert(first_at_least(a, 10) == 4);
    assert(search_weak_invariant(a, 10) == 3);
    // La invariante débil sí se cumple al salir: todo lo que está a la izquierda es menor.
    for (int i = 0; i < 3; i++) assert(a[i] < 10);
    // Y aun así a[3] no es mayor o igual que 10.
    assert(a[3] < 10);
    assert(search_lo_is_mid({2, 4}, 9, 1000) == -1);
    assert(first_at_least({2, 4}, 9) == 2);
}

long long slow_power(long long b, long long e, long long m) {
    long long result = 1 % m;
    for (long long i = 0; i < e; i++) {
        result = result * (b % m) % m;
    }
    return result;
}

int floor_log2(long long e) {
    int result = 0;
    while (e > 1) {
        e /= 2;
        result++;
    }
    return result;
}

int bits_on(long long e) {
    int result = 0;
    for (; e > 0; e /= 2) {
        result += static_cast<int>(e % 2);
    }
    return result;
}

void test_power() {
    for (long long m : {1LL, 2LL, 7LL, 1000LL, 1000000007LL, 2147483648LL}) {
        for (long long b : {0LL, 1LL, 2LL, 3LL, 10LL, 2147483647LL}) {
            for (long long e = 0; e <= 300; e++) {
                assert(power_mod(b, e, m) == slow_power(b, e, m));
            }
        }
    }
    // Exactamente ⌊log e⌋ + 1 cuadrados, más un producto por cada bit 1 de e.
    for (long long e = 1; e <= 5000; e++) {
        long long multiplications = 0;
        power_mod(3, e, 1000, &multiplications);
        assert(multiplications == floor_log2(e) + 1 + bits_on(e));
        assert(multiplications <= 2 * (floor_log2(e) + 1));
    }
}

bool prefers(const std::vector<int>& list, int a, int b) {
    return std::find(list.begin(), list.end(), a) < std::find(list.begin(), list.end(), b);
}

// Elige al proponente libre al azar: el resultado no debe cambiar.
std::vector<int> gale_shapley_any_order(const Preferences& proposers, const Preferences& receivers,
                                        std::mt19937& gen) {
    int n = static_cast<int>(proposers.size());
    std::vector<int> next_choice(n, 0);
    std::vector<int> holder(n, -1);
    std::vector<int> free_proposers(n);
    std::iota(free_proposers.begin(), free_proposers.end(), 0);
    while (!free_proposers.empty()) {
        std::swap(free_proposers[gen() % free_proposers.size()], free_proposers.back());
        int p = free_proposers.back();
        free_proposers.pop_back();
        int r = proposers[p][next_choice[p]++];
        if (holder[r] == -1) {
            holder[r] = p;
        } else if (prefers(receivers[r], p, holder[r])) {
            free_proposers.push_back(holder[r]);
            holder[r] = p;
        } else {
            free_proposers.push_back(p);
        }
    }
    std::vector<int> partner(n);
    for (int r = 0; r < n; r++) {
        partner[holder[r]] = r;
    }
    return partner;
}

// Los teoremas, contra la enumeración de todos los matchings.
void test_theorems_by_brute_force() {
    std::mt19937 gen(7);
    for (int n = 1; n <= 6; n++) {
        for (int round = 0; round < 400; round++) {
            Preferences proposers = random_preferences(n, gen);
            Preferences receivers = random_preferences(n, gen);
            Matching result = gale_shapley(proposers, receivers);

            // Es un matching perfecto y estable.
            std::vector<bool> used(n, false);
            for (int r : result.partner) {
                assert(!used[r]);
                used[r] = true;
            }
            assert(!find_unstable_pair(result.partner, proposers, receivers));

            // Cota de propuestas, y la cota más fina del ejercicio.
            assert(result.proposals <= static_cast<long long>(n) * n);
            assert(result.proposals <= static_cast<long long>(n) * n - n + 1);

            // Cada proponente hace tantas propuestas como la posición de su pareja, contando desde 1.
            long long positions = 0;
            for (int p = 0; p < n; p++) {
                positions += 1 + (std::find(proposers[p].begin(), proposers[p].end(), result.partner[p]) - proposers[p].begin());
            }
            assert(result.proposals == positions);

            // Da lo mismo con la lista y en cualquier orden.
            long long steps = 0;
            assert(gale_shapley_scan(proposers, receivers, steps).partner == result.partner);
            assert(gale_shapley_any_order(proposers, receivers, gen) == result.partner);

            std::vector<std::vector<int>> stable = all_stable_matchings(proposers, receivers);
            assert(!stable.empty());
            assert(std::find(stable.begin(), stable.end(), result.partner) != stable.end());

            std::vector<int> holder(n);
            for (int p = 0; p < n; p++) {
                holder[result.partner[p]] = p;
            }
            for (const std::vector<int>& other : stable) {
                for (int p = 0; p < n; p++) {
                    // Ningún proponente tiene algo mejor en otro matching estable.
                    assert(other[p] == result.partner[p] || prefers(proposers[p], result.partner[p], other[p]));
                    // Ningún receptor tiene algo peor en otro matching estable.
                    int r = other[p];
                    assert(p == holder[r] || prefers(receivers[r], p, holder[r]));
                }
            }
        }
    }
}

void test_examples_of_the_notes() {
    // La idea de la primera oferta da un par inestable en el ejemplo.
    Preferences students = example_students();
    Preferences advisors = example_advisors();
    assert(find_unstable_pair(first_offer_matching(students), students, advisors).has_value());
    assert(gale_shapley(students, advisors).proposals == 9);

    // La instancia cruzada tiene dos matchings estables.
    Preferences crossed_t = crossed_students();
    Preferences crossed_a = crossed_advisors();
    assert(all_stable_matchings(crossed_t, crossed_a).size() == 2);
    assert((gale_shapley(crossed_t, crossed_a).partner == std::vector<int>{0, 1}));
    assert((gale_shapley(crossed_a, crossed_t).partner == std::vector<int>{1, 0}));

    // Con las listas iguales hay exactamente n(n + 1)/2 propuestas.
    for (int n : {1, 2, 3, 10, 57, 200}) {
        Matching result = gale_shapley(same_list_proposers(n), latest_wins_receivers(n));
        assert(result.proposals == static_cast<long long>(n) * (n + 1) / 2);
    }
}

}  // namespace

int main() {
    test_binary_search();
    test_wrong_searches();
    test_power();
    test_theorems_by_brute_force();
    test_examples_of_the_notes();
    std::cout << "test_examples: todo correcto\n";
}

"""Vuelve a correr los comandos que aparecen en los apuntes y en las diapositivas, y comprueba
que el código citado existe de verdad en esta carpeta. Las mediciones no se comparan."""
import pathlib
import re
import subprocess
import unittest

HERE = pathlib.Path(__file__).parent
ROOT = HERE.parent.parent
NOTES = ROOT / "notes" / "week-01.md"
SLIDES = ROOT / "slides" / "week-01.tex"
# Antes de un bloque que depende de la máquina o que tarda: no se corre.
SYSTEM_DEPENDENT = "<!-- depende del sistema -->"


def run_shell(command):
    done = subprocess.run(
        ["bash", "-c", command], cwd=HERE, text=True, encoding="utf-8",
        stdin=subprocess.DEVNULL, stdout=subprocess.PIPE, stderr=subprocess.STDOUT, timeout=120,
    )
    return [line.rstrip() for line in done.stdout.splitlines()]


def split_commands(lines):
    """Parte un bloque de terminal en pares (comando, líneas de salida)."""
    pairs = []
    for line in lines:
        if line.startswith("$ "):
            pairs.append((line[2:], []))
        elif pairs:
            pairs[-1][1].append(line.rstrip())
    return pairs


def note_blocks(language):
    """Devuelve (líneas, marca) de cada bloque de los apuntes."""
    blocks, current, mark, previous = [], None, "", ""
    for raw in NOTES.read_text(encoding="utf-8").splitlines():
        line = re.sub(r"^> ?", "", raw)
        if current is None:
            if line.strip() == "```" + language:
                current, mark = [], previous.strip()
            elif line.strip():
                previous = line
        elif line.strip() == "```":
            blocks.append((current, mark))
            current = None
        else:
            current.append(line)
    return blocks


def slide_blocks(environments):
    text = SLIDES.read_text(encoding="utf-8")
    pattern = r"\\begin\{(?:%s)\}[^\n]*\n(.*?)\\end\{(?:%s)\}" % (environments, environments)
    return [match.group(1).splitlines() for match in re.finditer(pattern, text, re.S)]


def known_code_lines():
    lines = set()
    for source in list(HERE.glob("*.cpp")) + list(HERE.glob("*.h")):
        lines.update(line.strip() for line in source.read_text(encoding="utf-8").splitlines())
    return lines


class NotesAreTrue(unittest.TestCase):
    @unittest.skipUnless(NOTES.exists(), "faltan los apuntes")
    def test_terminal_blocks_in_notes(self):
        checked = 0
        for lines, mark in note_blocks("text"):
            if not lines or not lines[0].startswith("$ ") or mark == SYSTEM_DEPENDENT:
                continue
            for command, expected in split_commands(lines):
                checked += 1
                with self.subTest(command=command):
                    self.assertEqual(run_shell(command), expected)
        self.assertGreater(checked, 5)

    @unittest.skipUnless(NOTES.exists(), "faltan los apuntes")
    def test_code_blocks_in_notes_exist(self):
        known = known_code_lines()
        for lines, _ in note_blocks("cpp"):
            for line in lines:
                if line.strip() and line.strip() != "...":
                    with self.subTest(line=line):
                        self.assertIn(line.strip(), known)


class SlidesAreTrue(unittest.TestCase):
    @unittest.skipUnless(SLIDES.exists(), "faltan las diapositivas")
    def test_program_output_in_slides(self):
        for block in slide_blocks("terminal|salida"):
            for command, expected in split_commands(block):
                actual = run_shell(command)
                with self.subTest(command=command):
                    self.assertEqual(actual, expected)

    @unittest.skipUnless(NOTES.exists() and SLIDES.exists(), "faltan los apuntes o las diapositivas")
    def test_measurements_in_slides_come_from_notes(self):
        notes = NOTES.read_text(encoding="utf-8").splitlines()
        for block in slide_blocks("medicion"):
            for line in block:
                with self.subTest(line=line):
                    self.assertIn(line, notes)

    @unittest.skipUnless(SLIDES.exists(), "faltan las diapositivas")
    def test_code_blocks_in_slides_exist(self):
        known = known_code_lines()
        for block in slide_blocks("codigo|codigochico|codigomini"):
            for line in block:
                if line.strip() and line.strip() != "...":
                    with self.subTest(line=line):
                        self.assertIn(line.strip(), known)


if __name__ == "__main__":
    unittest.main()

TIEMPO = 2
include ../../../lab.mk

# Asignar postulantes a carreras

Una universidad ficticia reparte a sus postulantes entre sus carreras. Cada postulante ordena todas las carreras, de la
que más quiere a la que menos quiere. Cada carrera tiene una cantidad de vacantes, y ordena a todos los postulantes
según sus propios criterios. No hay empates en ninguna lista.

Una **asignación** le da a cada postulante una carrera o ninguna, sin pasarse de las vacantes de ninguna carrera.

Un postulante p y una carrera c **tienen un reclamo** si p no está en c, p preferiría estar en c antes que donde está
(estar sin carrera es lo peor para cualquiera), y además se cumple una de estas dos cosas:

- c tiene una vacante libre;
- c prefiere a p antes que a alguno de los que admitió.

Una asignación es **estable** si nadie tiene un reclamo. Puede haber varias asignaciones estables. Para cada postulante,
llamemos **mejor carrera posible** a la que más quiere entre todas las que le tocan en alguna asignación estable (o ninguna, si en ninguna asignación estable le toca carrera).

Calculen la asignación en la que cada postulante recibe su mejor carrera posible. Esa asignación siempre existe, es estable
y es única.

## Entrada

La primera línea tiene A y C: la cantidad de postulantes y de carreras. Los postulantes se numeran desde 0 hasta A − 1,
y las carreras desde 0 hasta C − 1.

La segunda línea tiene C enteros: las vacantes de cada carrera.

Las A líneas siguientes tienen, cada una, las C carreras en el orden del postulante, de la que más quiere a la que
menos quiere.

Las C líneas siguientes tienen, cada una, los A postulantes en el orden de la carrera, del que más quiere al que menos
quiere.

## Salida

A líneas. La línea i tiene la carrera que le toca al postulante i, o -1 si se queda sin carrera.

## Límites

- 1 ≤ A, C
- A · C ≤ 2 000 000
- 0 ≤ vacantes de una carrera ≤ A. Una carrera puede tener 0 vacantes.
- La suma de las vacantes puede ser menor, igual o mayor que A.

La entrada del caso más grande tiene 4 millones de números. Lean con `std::cin` después de
`std::ios::sync_with_stdio(false)`, como en el esqueleto.

## Ejemplo

Entrada:

```text
5 3
2 1 1
0 1 2
0 2 1
1 0 2
0 1 2
2 1 0
3 1 0 4 2
2 3 4 1 0
4 0 1 2 3
```

Salida:

```text
-1
0
1
0
2
```

Comprueben a mano que es estable. El postulante 0 se queda sin carrera y aun así no tiene reclamo: las dos vacantes de la
carrera 0 están ocupadas por los postulantes 3 y 1, y ella prefiere a los dos antes que a él; las carreras 1 y 2 también
prefieren a quienes admitieron. Nadie más tiene reclamo: cada uno de los otros cuatro ya está en su primera opción.

## Tiempo

2 segundos por caso.

## Para pensar

Cuando el juez acepte su programa, respondan esta pregunta por escrito, y justifiquen su respuesta con una demostración
o con una ejecución.

Imaginen que el proceso se hace al revés: en vez de buscar lo mejor para cada postulante, se busca lo mejor para las
carreras, con las carreras ofreciendo sus vacantes. ¿Quién gana y quién pierde con ese cambio? ¿Puede un postulante
quedar mejor que en su respuesta? ¿Puede una carrera quedar peor? Prueben con un caso en el que los dos resultados sean
distintos.

// Asignación de postulantes a carreras. Ya lee la entrada: falta calcular la asignación.
#include <iostream>
#include <vector>

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int applicants, careers;
    std::cin >> applicants >> careers;

    std::vector<int> vacancies(careers);
    for (int& v : vacancies) {
        std::cin >> v;
    }

    // applicant_prefs[p]: las carreras en el orden de p, de la que más quiere a la que menos quiere.
    std::vector<std::vector<int>> applicant_prefs(applicants, std::vector<int>(careers));
    for (auto& list : applicant_prefs) {
        for (int& career : list) {
            std::cin >> career;
        }
    }

    // career_prefs[c]: los postulantes en el orden de c, del que más quiere al que menos quiere.
    std::vector<std::vector<int>> career_prefs(careers, std::vector<int>(applicants));
    for (auto& list : career_prefs) {
        for (int& applicant : list) {
            std::cin >> applicant;
        }
    }

    // Por ahora nadie entra a ninguna carrera. Esto es incorrecto.
    for (int p = 0; p < applicants; p++) {
        std::cout << -1 << '\n';
    }
}