Задача 2. Захват королевства.

#include <iostream>
#include <vector>
#include <random>
#include <functional>


// Задача 2. Захват королевства.

// функция потерь
int f(const std::vector<int>& figures, std::vector<std::vector<int>>& w, int p) {
    int ans = 0;
    std::vector<int> v(figures.size());

    for (auto i = 0; i < figures.size(); ++i) {
        if (figures[i] == 1) {
            v[i] = 1;
            for (auto j = 0; j < figures.size(); ++j) {
                if (w[i][j] == p) {
                    v[j] = 1;
                }
            }
        }
    }
    for (auto i = 0; i < v.size(); ++i) {
        ans += v[i];
    }

    return ans;
}

int main() {
    int n, k, type;
    std::cin >> n >> k;
    std::vector<std::vector<int>> w(n, std::vector<int> (n, 0));
    int num_wis = 0;
    for (auto i = 0; i < n; ++i) {
        for (auto j = 0; j < n; ++j) {
            std::cin >> type;
            w[i][j] = type;
        }
    }

    // Изначальная расстановка
    std::vector<int> figures(n);
    for (auto i = 0; i < k; ++i) {
        figures[i] = 1;
    }

    std::random_device rd;
    std::mt19937 rnd(1783461065);


    std::shuffle(figures.begin(), figures.end(), rnd);
    for (auto p = 1; p < 3; p++) {
        int current = f(figures, w, p);

        double t = 1.0;

        for (size_t j = 0; j < 2000000 && current < n; ++j) {
            t = t * 0.995;

            std::vector<int> u = figures;
            std::swap(u[rnd() % n], u[rnd() % n]);
            int next = f(u, w, p);
            if (next > current || double(rnd()) / RAND_MAX < exp((next - current) / t)) {
                figures = u;
                current = next;
            }
        }
        if (current != n) {
            if (p == 2) {
                std::cout << 0 << std::endl;
            }
        } else {
            std::cout << p << std::endl;
            for (auto i = 0; i < figures.size(); i++) {
                num_wis += figures[i];
            }
            std::cout << num_wis << std::endl;
            for (auto i = 0; i < figures.size(); i++) {
                if (figures[i] == 1) {
                    std::cout << i + 1 << " ";
                }
            }
            break;
        }
    }

    return 0;
}