// Verificadores de cinco problemas de NP. Cada función recibe una instancia w y un
// certificado c, y responde si c demuestra que w está en el lenguaje. Ninguna busca nada:
// solo comprueba, y por eso todas corren en tiempo polinomial en el tamaño de la instancia.
// Un certificado mal formado (un vértice repetido, un índice fuera de rango) se rechaza.
#ifndef VERIFIERS_H
#define VERIFIERS_H

#include <cstddef>
#include <cstdlib>
#include <set>
#include <utility>
#include <vector>

// Un grafo con los vértices 1..n. En un grafo dirigido, el par (u, v) es el arco de u a v.
// En uno no dirigido, la arista {u, v} se guarda una sola vez, en cualquier orden.
struct Graph {
    int n = 0;
    std::vector<std::pair<int, int>> edges;
};

// Una fórmula en CNF, como en el formato DIMACS: las variables son 1..variables, y un literal
// es i (la variable x_i) o -i (su negación). Una cláusula es una lista de literales.
struct Cnf {
    int variables = 0;
    std::vector<std::vector<int>> clauses;
};

// HAMPATH. Instancia: un grafo dirigido g y dos vértices s y t.
// Certificado: una lista de vértices. Es válido si tiene los n vértices, cada uno una vez,
// empieza en s, termina en t, y entre cada vértice y el siguiente hay un arco.
inline bool verify_hampath(const Graph& g, int s, int t, const std::vector<int>& path) {
    if (g.n < 1 || static_cast<int>(path.size()) != g.n) {
        return false;
    }
    std::vector<bool> seen(static_cast<std::size_t>(g.n) + 1, false);
    for (int v : path) {
        if (v < 1 || v > g.n || seen[static_cast<std::size_t>(v)]) {
            return false;
        }
        seen[static_cast<std::size_t>(v)] = true;
    }
    if (path.front() != s || path.back() != t) {
        return false;
    }
    std::set<std::pair<int, int>> arcs(g.edges.begin(), g.edges.end());
    for (std::size_t i = 0; i + 1 < path.size(); i++) {
        if (arcs.count({path[i], path[i + 1]}) == 0) {
            return false;
        }
    }
    return true;
}

// CLIQUE. Instancia: un grafo no dirigido g y un número k.
// Certificado: una lista de k vértices distintos, todos unidos entre sí.
inline bool verify_clique(const Graph& g, int k, const std::vector<int>& vertices) {
    if (static_cast<int>(vertices.size()) != k) {
        return false;
    }
    std::set<int> distinct;
    for (int v : vertices) {
        if (v < 1 || v > g.n || !distinct.insert(v).second) {
            return false;
        }
    }
    std::set<std::pair<int, int>> adjacent;
    for (const auto& [u, v] : g.edges) {
        adjacent.insert({u, v});
        adjacent.insert({v, u});
    }
    for (std::size_t i = 0; i < vertices.size(); i++) {
        for (std::size_t j = i + 1; j < vertices.size(); j++) {
            if (adjacent.count({vertices[i], vertices[j]}) == 0) {
                return false;
            }
        }
    }
    return true;
}

// SUBSET-SUM. Instancia: una lista de números positivos y un objetivo.
// Certificado: las posiciones (desde 1) de los números elegidos, sin repetir.
// additions, si no es nulo, recibe cuántas sumas se hicieron: es el costo de comprobar.
// Los números de los ejemplos son pequeños; el laboratorio discute el overflow.
inline bool verify_subset_sum(const std::vector<long long>& numbers, long long target,
                              const std::vector<int>& chosen, long long* additions = nullptr) {
    std::vector<bool> used(numbers.size() + 1, false);
    long long sum = 0;
    long long count = 0;
    for (int i : chosen) {
        if (i < 1 || i > static_cast<int>(numbers.size()) || used[static_cast<std::size_t>(i)]) {
            return false;
        }
        used[static_cast<std::size_t>(i)] = true;
        sum += numbers[static_cast<std::size_t>(i) - 1];
        count++;
    }
    if (additions != nullptr) {
        *additions = count;
    }
    return sum == target;
}

// SAT, para fórmulas en CNF. Certificado: una lista de literales, uno por variable, en
// cualquier orden: i dice que x_i es verdadera y -i que es falsa.
// Es válido si le da un valor a cada variable, exactamente una vez, y cada cláusula tiene
// algún literal verdadero.
inline bool verify_sat(const Cnf& f, const std::vector<int>& assignment) {
    std::vector<int> value(static_cast<std::size_t>(f.variables) + 1, 0);  // 0: sin valor; 1 o -1
    for (int literal : assignment) {
        int variable = std::abs(literal);
        if (variable < 1 || variable > f.variables || value[static_cast<std::size_t>(variable)] != 0) {
            return false;
        }
        value[static_cast<std::size_t>(variable)] = literal > 0 ? 1 : -1;
    }
    if (static_cast<int>(assignment.size()) != f.variables) {
        return false;
    }
    for (const std::vector<int>& clause : f.clauses) {
        bool satisfied = false;
        for (int literal : clause) {
            int sign = literal > 0 ? 1 : -1;
            satisfied = satisfied || value[static_cast<std::size_t>(std::abs(literal))] == sign;
        }
        if (!satisfied) {
            return false;
        }
    }
    return true;
}

// COMPOSITES. Instancia: un número x. Certificado: un divisor d con 1 < d < x.
inline bool verify_composite(unsigned long long x, unsigned long long d) {
    return d > 1 && d < x && x % d == 0;
}

#endif
