// 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