// Eliminación en un campeonato sin empates: ¿puede un equipo todavía quedar primero, aunque sea empatado?
#pragma once

#include <cassert>
#include <cstddef>
#include <string>
#include <vector>

#include "flow.h"

struct Championship {
    std::vector<std::string> names;
    std::vector<int> wins;
    std::vector<std::vector<int>> games;  // games[i][j]: partidos que faltan entre i y j, simétrica
};

struct Elimination {
    bool eliminated = false;
    bool trivial = false;             // algún equipo ya tiene más victorias de las que x puede alcanzar
    long long best = 0;               // lo más que x puede alcanzar: W
    long long flow = 0;               // lo que pasó por la red
    long long games_left = 0;         // lo que debería pasar: los partidos que no juega x
    std::vector<int> certificate;     // equipos que, entre todos, no caben por debajo de W
};

inline int remaining_of(const Championship& league, int team) {
    int total = 0;
    for (int g : league.games[static_cast<std::size_t>(team)]) total += g;
    return total;
}

inline Elimination check_team(const Championship& league, int x) {
    auto at = [](int i) { return static_cast<std::size_t>(i); };
    int teams = static_cast<int>(league.wins.size());
    Elimination result;
    result.best = league.wins[at(x)] + remaining_of(league, x);
    for (int i = 0; i < teams; i++) {
        if (league.wins[at(i)] > result.best) {
            // Sin este caso, la capacidad W - w sería negativa.
            result.eliminated = true;
            result.trivial = true;
            result.certificate = {i};
            return result;
        }
    }
    int game_nodes = 0;
    for (int i = 0; i < teams; i++) {
        for (int j = i + 1; j < teams; j++) {
            if (i != x && j != x && league.games[at(i)][at(j)] > 0) game_nodes++;
        }
    }
    int source = teams;
    int sink = teams + 1;
    int next = teams + 2;
    MaxFlow flow(teams + 2 + game_nodes);
    for (int i = 0; i < teams; i++) {
        for (int j = i + 1; j < teams; j++) {
            if (i != x && j != x) result.games_left += league.games[at(i)][at(j)];
        }
    }
    long long no_limit = result.games_left + 1;  // ningún partido reparte más que eso
    for (int i = 0; i < teams; i++) {
        for (int j = i + 1; j < teams; j++) {
            if (i == x || j == x || league.games[at(i)][at(j)] == 0) continue;
            flow.add_edge(source, next, league.games[at(i)][at(j)]);
            flow.add_edge(next, i, no_limit);
            flow.add_edge(next, j, no_limit);
            next++;
        }
    }
    for (int i = 0; i < teams; i++) {
        if (i != x) flow.add_edge(i, sink, result.best - league.wins[at(i)]);
    }
    result.flow = flow.edmonds_karp(source, sink);
    result.eliminated = result.flow < result.games_left;
    if (result.eliminated) {
        std::vector<bool> reached = flow.reachable_from(source);
        for (int i = 0; i < teams; i++) {
            if (i != x && reached[at(i)]) result.certificate.push_back(i);
        }
    }
    return result;
}

// Lo que dice el certificado: las victorias de R, contando los partidos entre ellos, no caben debajo de W.
inline bool certificate_holds(const Championship& league, long long best, const std::vector<int>& group) {
    auto at = [](int i) { return static_cast<std::size_t>(i); };
    long long total = 0;
    for (std::size_t a = 0; a < group.size(); a++) {
        total += league.wins[at(group[a])];
        for (std::size_t b = a + 1; b < group.size(); b++) total += league.games[at(group[a])][at(group[b])];
    }
    return total > static_cast<long long>(group.size()) * best;
}

// Árbitro: prueba todos los resultados de todos los partidos.
inline bool brute_can_finish_first(const Championship& league, int x) {
    auto at = [](int i) { return static_cast<std::size_t>(i); };
    int teams = static_cast<int>(league.wins.size());
    std::vector<std::pair<int, int>> pending;
    for (int i = 0; i < teams; i++) {
        for (int j = i + 1; j < teams; j++) {
            for (int k = 0; k < league.games[at(i)][at(j)]; k++) pending.emplace_back(i, j);
        }
    }
    std::vector<int> final_wins = league.wins;
    auto search = [&](auto&& self, std::size_t next) -> bool {
        if (next == pending.size()) {
            for (int i = 0; i < teams; i++) {
                if (final_wins[at(i)] > final_wins[at(x)]) return false;
            }
            return true;
        }
        for (int winner : {pending[next].first, pending[next].second}) {
            final_wins[at(winner)]++;
            bool can = self(self, next + 1);
            final_wins[at(winner)]--;
            if (can) return true;
        }
        return false;
    };
    return search(search, 0);
}