#include <iostream>
#include <vector>
#include <random>
#include <chrono>
#include <algorithm>

class Miner {
private:
    size_t n;
    size_t mines;
    std::vector<bool> line;
    std::vector<bool> click;
    size_t clicked = 0;
    bool lost = false;
    std::mt19937 rnd;


    int get_count(size_t i) {
        int ans = 0;
        if (i > 0) {
            ans += line[i - 1];
        }
        if (i + 1 < n) {
            ans += line[i + 1];
        }
        return ans;
    }

public:
    Miner(size_t n, size_t mines): n(n), mines(mines), line(n), click(n),
            rnd(std::chrono::high_resolution_clock::now().time_since_epoch().count())
    {
        for (size_t i = 0; i < mines; ++i) {
            line[i] = true;
        }
        std::shuffle(line.begin(), line.end(), rnd);
    }

    int click_square(size_t i) {
        if (line[i]) {
            lost = true;
            return -1;
        }
        if (!click[i]) {
            ++clicked;
        }
        click[i] = true;
        return get_count(i);
    }

    int game_result() {
        if (lost) {
            return -1;
        }
        if (clicked == n - mines) {
            return 1;
        }
        return 0;
    }
};

void middle_solver_helper(int l, int r, std::vector<int>& line, Miner& miner) {
    if (l > r) return;
    int m = (l + r) / 2;
    if (line[m] == -2) {
        line[m] = miner.click_square(m);
    }
    if (line[m] >= 0) {
        if (m >= 2 && line[m - 1] == 1) {
            line[m - 2] = -1;
        } else if (m + 2 < line.size() && line[m + 1] == 1) {
            line[m + 2] = -1;
        }
    }
    // std::cerr << l << ' ' << m << ' ' << r << ' ' << line[m] << std::endl;
    if (line[m] == 2) {
        line[m - 1] = line[m + 1] = -1;
        middle_solver_helper(l, m - 2, line, miner);
        middle_solver_helper(m + 2, r, line, miner);
        return;
    }
    if (line[m] == 0) {
        for (int j = m - 1; j >= l; --j) {
            line[j] = miner.click_square(j);
            if (line[j] == 1) {
                line[j - 1] = -1;
                middle_solver_helper(l, j - 2, line, miner);
                break;
            }
        }
        for (int j = m + 1; j <= r; ++j) {
            line[j] = miner.click_square(j);
            if (line[j] == 1) {
                line[j + 1] = -1;
                middle_solver_helper(j + 2, r, line, miner);
                break;
            }
        }
        return;
    }
    if (line[m] == 1) {
        if (m == 0 || line[m - 1] >= 0) {
            line[m + 1] = -1;
        } else if (m + 1 == line.size() || line[m + 1] >= 0) {
            line[m - 1] = -1;
        }
    }
    middle_solver_helper(l, m - 1, line, miner);
    middle_solver_helper(m + 1, r, line, miner);
}

void middle_solver(size_t n, size_t mines, Miner& miner) {
    std::vector<int> line(n, -2);
    middle_solver_helper(0, n - 1, line, miner);
}

void random_solver(size_t n, size_t mines, Miner& miner) {
    std::vector<int> line(n, -2);
    std::vector<size_t> order(n);
    std::iota(order.begin(), order.end(), 0);
    std::mt19937 rnd(std::chrono::high_resolution_clock::now().time_since_epoch().count());
    std::shuffle(order.begin(), order.end(), rnd);
    for (size_t i : order) {
        if (miner.game_result() == 1) {
            break;
        }
        if (line[i] != -2) {
            continue;
        }
        line[i] = miner.click_square(i);
        if (line[i] == -1) {
            return;
        }
        if (line[i] == 2) {
            line[i - 1] = line[i + 1] = -1;
        } else if (line[i] == 1) {
            if (i == 0 || line[i - 1] >= 0) {
                line[i + 1] = -1;
            } else if (i == n - 1 || line[i + 1] >= 0) {
                line[i - 1] = -1;
            }
        } else if (line[i] == 0) {
            for (int j = static_cast<int>(i) - 1; j >= 0; --j) {
                line[j] = miner.click_square(j);
                if (line[j] > 0) {
                    line[j - 1] = -1;
                    break;
                }
            }
            for (int j = i + 1; j < n; ++j) {
                line[j] = miner.click_square(j);
                if (line[j] > 0) {
                    line[j + 1] = -1;
                    break;
                }
            }
        }
    }
}

void simple_solver(size_t n, size_t mines, Miner& miner) {
    std::vector<int> line(n, -2);
    for (size_t i = 0; i < n; ++i) {
        if (line[i] != -2) {
            continue;
        }
        line[i] = miner.click_square(i);
        if (line[i] == -1) {
            return;
        }
        int next = line[i] - (i > 0 && line[i - 1] == -1);
        if (next) {
            line[i + 1] = -1;
        }
    }
}

int main() {
    size_t n = 10000, mines = 90, rep = 10000, won = 0;
    for (size_t i = 0; i < rep; ++i) {
        Miner miner(n, mines);
        middle_solver(n, mines, miner);
        won += miner.game_result() == 1;
    }
    std::cout << "won " << won << " out of " << rep << std::endl;
}