#1172442 (C++23(gcc16)) No.3730 Jagged Minesweeper

• 問題: No.3730 Jagged Minesweeper
• ユーザー: 👑 kencho
• 提出日時: 2026-07-22 04:04:22
• 言語: C++23(gcc16) (gcc 16.1.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 813 ms / 2,500 ms
• コード長: 26,578 bytes
• コンパイル時間: 4,028 ms
• コンパイル使用メモリ: 379,340 KB
• 実行使用メモリ: 35,220 KB
• 最終ジャッジ日時: 2026-09-19 12:35:50
• 合計ジャッジ時間: 30,277 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge2_0

ファイルパターン	結果
sample	AC * 2
other	AC * 43

ソースコード

#include <bits/stdc++.h>
using namespace std;

/*
  Heuristic solver for

      bomb at v    => (# bombs in the clipped 3x3 centered at v) <= a[v]
      no bomb at v => (# bombs in the clipped 3x3 centered at v) >= a[v]

  Equivalently, with c[v] = bombs in the other at most eight cells,

      x[v] = 1  <=>  c[v] < a[v].

  This is intentionally a genuine heuristic benchmark:
  it does NOT use the guaranteed "flip any violated cell" algorithm,
  and it does NOT optimize the exact cut/potential function.

  Main ideas:
    * simulated annealing on an adaptive weighted violation objective;
    * focus most proposals on violated cells and their neighbourhoods;
    * breakout weights: persistent violations gradually become expensive;
    * occasional pair, rectangle, and whole-component flips;
    * several initialisation patterns / restarts.

  Output: 'o' = bomb, '.' = no bomb.

  The time budget can be changed at compile time, for example:
      g++ -O3 -std=c++17 -DSA_TIME_LIMIT=8.0 sa_solver_o_dot.cpp
*/

#ifndef SA_TIME_LIMIT
#define SA_TIME_LIMIT 4.8
#endif

namespace {

constexpr int DI[8] = {-1,-1,-1,0,0,1,1,1};
constexpr int DJ[8] = {-1,0,1,-1,1,-1,0,1};
constexpr int MAX_PENALTY = 4095;
constexpr int MAX_COMPONENT_MOVE = 30000;
constexpr int MAX_RECT_MOVE = 5000;

struct FastRng {
    uint64_t s;
    explicit FastRng(uint64_t seed) : s(seed ? seed : 0x9e3779b97f4a7c15ULL) {}

    uint64_t operator()() {
        // splitmix64
        uint64_t z = (s += 0x9e3779b97f4a7c15ULL);
        z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9ULL;
        z = (z ^ (z >> 27)) * 0x94d049bb133111ebULL;
        return z ^ (z >> 31);
    }

    uint32_t u32() { return static_cast<uint32_t>((*this)()); }

    int uniform_int(int bound) {
        if (bound <= 1) return 0;
        return static_cast<int>((__uint128_t((*this)()) * uint64_t(bound)) >> 64);
    }

    double unit() {
        return ((*this)() >> 11) * (1.0 / 9007199254740992.0);
    }
};

struct Delta {
    int bad = 0;
    long long weighted_bad = 0;
    int l1 = 0;
    int l2 = 0;
};

struct Solver {
    int n = 0;
    int V = 0;
    vector<unsigned char> a;

    // Current state.
    vector<unsigned char> x;       // 1 = bomb
    vector<unsigned char> cnt;     // bomb count among the other at most 8 cells
    vector<unsigned char> residual;

    // Dynamic weighted local-search data.
    vector<unsigned short> penalty;
    vector<int> bad_list;
    vector<int> bad_pos;
    long long weighted_bad = 0;
    long long l1 = 0;
    long long l2 = 0;

    // Cells with a in [1,8] are movable.  a=0 is forced '.', a=9 is forced 'o'.
    vector<int> movable;
    vector<unsigned char> is_movable;

    // Connected components of movable cells in the 8-neighbour graph.
    vector<int> comp_id;
    vector<int> comp_cells;
    vector<int> comp_start;
    vector<int> comp_min_i, comp_max_i, comp_min_j, comp_max_j;

    // Scratch buffers for macro moves.
    vector<int> mark;
    int mark_stamp = 1;
    vector<int> affected;
    vector<signed char> move_add;

    FastRng rng;

    explicit Solver(int n_, vector<unsigned char> digits, uint64_t seed)
        : n(n_), V(n_*n_), a(std::move(digits)), x(V), cnt(V), residual(V),
          penalty(V, 1), bad_pos(V, -1), is_movable(V, 0), comp_id(V, -1),
          mark(V, 0), rng(seed) {
        movable.reserve(V);
        for (int id = 0; id < V; ++id) {
            if (1 <= a[id] && a[id] <= 8) {
                is_movable[id] = 1;
                movable.push_back(id);
            }
        }
        build_components();
        affected.reserve(9 * 4096);
        move_add.reserve(4096);
    }

    inline int calc_residual(int id) const {
        // x=1 is valid iff cnt<a; x=0 is valid iff cnt>=a.
        if (x[id]) return max(0, int(cnt[id]) - int(a[id]) + 1);
        return max(0, int(a[id]) - int(cnt[id]));
    }

    inline long long energy_of(const Delta& d, double progress) const {
        // Early: let violation magnitude smooth the landscape.
        // Late: strongly prioritise removing the last violated cells.
        const double q = progress * progress;
        const long long w_bad = 24 + static_cast<long long>(232.0 * q);
        return w_bad * d.weighted_bad + 8LL * d.l1 + d.l2;
    }

    void build_components() {
        vector<int> q;
        q.reserve(V);
        comp_cells.reserve(movable.size());
        comp_start.clear();

        for (int root : movable) {
            if (comp_id[root] != -1) continue;
            const int cid = static_cast<int>(comp_start.size());
            comp_start.push_back(static_cast<int>(comp_cells.size()));

            q.clear();
            q.push_back(root);
            comp_id[root] = cid;
            int head = 0;
            int mn_i = root / n, mx_i = mn_i;
            int mn_j = root % n, mx_j = mn_j;

            while (head < static_cast<int>(q.size())) {
                int id = q[head++];
                comp_cells.push_back(id);
                int i = id / n, j = id % n;
                mn_i = min(mn_i, i); mx_i = max(mx_i, i);
                mn_j = min(mn_j, j); mx_j = max(mx_j, j);

                for (int k = 0; k < 8; ++k) {
                    int ni = i + DI[k], nj = j + DJ[k];
                    if (ni < 0 || ni >= n || nj < 0 || nj >= n) continue;
                    int nid = ni*n + nj;
                    if (!is_movable[nid] || comp_id[nid] != -1) continue;
                    comp_id[nid] = cid;
                    q.push_back(nid);
                }
            }
            comp_min_i.push_back(mn_i); comp_max_i.push_back(mx_i);
            comp_min_j.push_back(mn_j); comp_max_j.push_back(mx_j);
        }
        comp_start.push_back(static_cast<int>(comp_cells.size()));
    }

    void clear_bad_structure() {
        bad_list.clear();
        fill(bad_pos.begin(), bad_pos.end(), -1);
        weighted_bad = l1 = l2 = 0;
    }

    void add_bad(int id) {
        if (bad_pos[id] != -1) return;
        bad_pos[id] = static_cast<int>(bad_list.size());
        bad_list.push_back(id);
    }

    void remove_bad(int id) {
        int p = bad_pos[id];
        if (p == -1) return;
        int z = bad_list.back();
        bad_list[p] = z;
        bad_pos[z] = p;
        bad_list.pop_back();
        bad_pos[id] = -1;
    }

    void rebuild_counts_and_scores() {
        fill(cnt.begin(), cnt.end(), 0);
        for (int id = 0; id < V; ++id) {
            if (!x[id]) continue;
            int i = id / n, j = id % n;
            for (int k = 0; k < 8; ++k) {
                int ni = i + DI[k], nj = j + DJ[k];
                if (ni < 0 || ni >= n || nj < 0 || nj >= n) continue;
                ++cnt[ni*n + nj];
            }
        }

        clear_bad_structure();
        for (int id = 0; id < V; ++id) {
            int r = calc_residual(id);
            residual[id] = static_cast<unsigned char>(r);
            if (r) {
                add_bad(id);
                weighted_bad += penalty[id];
                l1 += r;
                l2 += 1LL*r*r;
            }
        }
    }

    void initialise(int kind) {
        fill(penalty.begin(), penalty.end(), 1);
        const int phase = rng.uniform_int(2);
        const int stripe = 2 + rng.uniform_int(6);

        for (int id = 0; id < V; ++id) {
            if (a[id] == 0) {
                x[id] = 0;
                continue;
            }
            if (a[id] == 9) {
                x[id] = 1;
                continue;
            }

            int i = id / n, j = id % n;
            switch (kind % 7) {
                case 0: // unbiased random
                    x[id] = rng.u32() & 1U;
                    break;
                case 1: // threshold-biased random
                    x[id] = rng.uniform_int(10) < a[id];
                    break;
                case 2: // checkerboard
                    x[id] = static_cast<unsigned char>((i + j + phase) & 1);
                    break;
                case 3: // vertical stripes
                    x[id] = static_cast<unsigned char>(((j / stripe) + phase) & 1);
                    break;
                case 4: // horizontal stripes
                    x[id] = static_cast<unsigned char>(((i / stripe) + phase) & 1);
                    break;
                case 5: // noisy checkerboard
                    x[id] = static_cast<unsigned char>(((i + j + phase) & 1) ^ (rng.uniform_int(7) == 0));
                    break;
                default: // blocky random field
                    x[id] = static_cast<unsigned char>((((i / stripe) * 11995408973635179863ULL
                                                      + (j / stripe) * 10150724397891781847ULL
                                                      + rng.s) >> 61) & 1ULL);
                    break;
            }
        }
        rebuild_counts_and_scores();
    }

    inline void collect_single_affected(int id, int ids[9], int& m) const {
        m = 0;
        ids[m++] = id;
        int i = id / n, j = id % n;
        for (int k = 0; k < 8; ++k) {
            int ni = i + DI[k], nj = j + DJ[k];
            if (ni < 0 || ni >= n || nj < 0 || nj >= n) continue;
            ids[m++] = ni*n + nj;
        }
    }

    Delta evaluate_single(int id) {
        Delta d;
        int ids[9], m;
        collect_single_affected(id, ids, m);

        long long old_w = 0;
        int old_l1 = 0, old_l2 = 0, old_bad = 0;
        for (int t = 0; t < m; ++t) {
            int z = ids[t], r = residual[z];
            if (r) {
                old_w += penalty[z];
                old_l1 += r;
                old_l2 += r*r;
                ++old_bad;
            }
        }

        int add = x[id] ? -1 : +1;
        x[id] ^= 1;
        for (int t = 1; t < m; ++t) cnt[ids[t]] += add;

        long long new_w = 0;
        int new_l1 = 0, new_l2 = 0, new_bad = 0;
        for (int t = 0; t < m; ++t) {
            int z = ids[t], r = calc_residual(z);
            if (r) {
                new_w += penalty[z];
                new_l1 += r;
                new_l2 += r*r;
                ++new_bad;
            }
        }

        for (int t = 1; t < m; ++t) cnt[ids[t]] -= add;
        x[id] ^= 1;

        d.bad = new_bad - old_bad;
        d.weighted_bad = new_w - old_w;
        d.l1 = new_l1 - old_l1;
        d.l2 = new_l2 - old_l2;
        return d;
    }

    void apply_single(int id, const Delta& d) {
        int ids[9], m;
        collect_single_affected(id, ids, m);
        int add = x[id] ? -1 : +1;
        x[id] ^= 1;
        for (int t = 1; t < m; ++t) cnt[ids[t]] += add;

        for (int t = 0; t < m; ++t) {
            int z = ids[t];
            int old_r = residual[z];
            int new_r = calc_residual(z);
            if (old_r == 0 && new_r != 0) add_bad(z);
            if (old_r != 0 && new_r == 0) remove_bad(z);
            residual[z] = static_cast<unsigned char>(new_r);
        }
        weighted_bad += d.weighted_bad;
        l1 += d.l1;
        l2 += d.l2;
    }

    void begin_macro() {
        affected.clear();
        move_add.clear();
        if (++mark_stamp == INT_MAX) {
            fill(mark.begin(), mark.end(), 0);
            mark_stamp = 1;
        }
    }

    inline void mark_affected(int id) {
        if (mark[id] == mark_stamp) return;
        mark[id] = mark_stamp;
        affected.push_back(id);
    }

    // Evaluates a set of distinct movable cells.  Leaves the move applied.
    // Caller either commit_macro() or rollback_macro().
    Delta apply_macro_tentatively(const vector<int>& flip_ids) {
        begin_macro();
        move_add.reserve(flip_ids.size());

        for (int id : flip_ids) {
            mark_affected(id);
            int i = id / n, j = id % n;
            for (int k = 0; k < 8; ++k) {
                int ni = i + DI[k], nj = j + DJ[k];
                if (ni < 0 || ni >= n || nj < 0 || nj >= n) continue;
                mark_affected(ni*n + nj);
            }
        }

        long long old_w = 0;
        int old_l1 = 0, old_l2 = 0, old_bad = 0;
        for (int z : affected) {
            int r = residual[z];
            if (r) {
                old_w += penalty[z];
                old_l1 += r;
                old_l2 += r*r;
                ++old_bad;
            }
        }

        for (int id : flip_ids) {
            int add = x[id] ? -1 : +1;
            move_add.push_back(static_cast<signed char>(add));
            x[id] ^= 1;
            int i = id / n, j = id % n;
            for (int k = 0; k < 8; ++k) {
                int ni = i + DI[k], nj = j + DJ[k];
                if (ni < 0 || ni >= n || nj < 0 || nj >= n) continue;
                cnt[ni*n + nj] += add;
            }
        }

        long long new_w = 0;
        int new_l1 = 0, new_l2 = 0, new_bad = 0;
        for (int z : affected) {
            int r = calc_residual(z);
            if (r) {
                new_w += penalty[z];
                new_l1 += r;
                new_l2 += r*r;
                ++new_bad;
            }
        }

        Delta d;
        d.bad = new_bad - old_bad;
        d.weighted_bad = new_w - old_w;
        d.l1 = new_l1 - old_l1;
        d.l2 = new_l2 - old_l2;
        return d;
    }

    void rollback_macro(const vector<int>& flip_ids) {
        for (int p = 0; p < static_cast<int>(flip_ids.size()); ++p) {
            int id = flip_ids[p];
            int add = move_add[p];
            x[id] ^= 1;
            int i = id / n, j = id % n;
            for (int k = 0; k < 8; ++k) {
                int ni = i + DI[k], nj = j + DJ[k];
                if (ni < 0 || ni >= n || nj < 0 || nj >= n) continue;
                cnt[ni*n + nj] -= add;
            }
        }
    }

    void commit_macro(const Delta& d) {
        for (int z : affected) {
            int old_r = residual[z];
            int new_r = calc_residual(z);
            if (old_r == 0 && new_r != 0) add_bad(z);
            if (old_r != 0 && new_r == 0) remove_bad(z);
            residual[z] = static_cast<unsigned char>(new_r);
        }
        weighted_bad += d.weighted_bad;
        l1 += d.l1;
        l2 += d.l2;
    }

    int random_movable() {
        return movable[rng.uniform_int(static_cast<int>(movable.size()))];
    }

    int random_bad() {
        return bad_list[rng.uniform_int(static_cast<int>(bad_list.size()))];
    }

    int local_candidate_around(int center, int radius = 1) {
        int ci = center / n, cj = center % n;
        for (int tries = 0; tries < 12; ++tries) {
            int ni = ci + rng.uniform_int(2*radius + 1) - radius;
            int nj = cj + rng.uniform_int(2*radius + 1) - radius;
            if (ni < 0 || ni >= n || nj < 0 || nj >= n) continue;
            int id = ni*n + nj;
            if (is_movable[id]) return id;
        }
        return is_movable[center] ? center : random_movable();
    }

    int propose_single(double /*progress*/) {
        if (bad_list.empty()) return random_movable();
        uint32_t r = rng.u32() % 100U;
        if (r < 48) {
            int z = random_bad();
            return is_movable[z] ? z : local_candidate_around(z, 1);
        }
        if (r < 82) return local_candidate_around(random_bad(), r < 70 ? 1 : 2);
        return random_movable();
    }

    double calibrate_temperature(double progress) {
        vector<long long> positive;
        positive.reserve(512);
        for (int s = 0; s < 1024 && !movable.empty(); ++s) {
            int id = propose_single(progress);
            Delta d = evaluate_single(id);
            long long e = energy_of(d, progress);
            if (e > 0) positive.push_back(e);
        }
        if (positive.empty()) return 16.0;
        nth_element(positive.begin(), positive.begin() + positive.size()/2, positive.end());
        double med = static_cast<double>(positive[positive.size()/2]);
        // A median uphill single flip is initially accepted with probability about 0.62.
        return max(2.0, med / -log(0.62));
    }

    void increase_breakout_weights(int sample_limit = 50000) {
        if (bad_list.empty()) return;
        int m = static_cast<int>(bad_list.size());
        if (m <= sample_limit) {
            for (int id : bad_list) {
                if (penalty[id] < MAX_PENALTY) {
                    ++penalty[id];
                    ++weighted_bad;
                }
            }
        } else {
            // Sampling keeps this O(sample_limit) even when almost the whole board is bad.
            for (int t = 0; t < sample_limit; ++t) {
                int id = bad_list[rng.uniform_int(m)];
                if (penalty[id] < MAX_PENALTY) {
                    ++penalty[id];
                    ++weighted_bad;
                }
            }
        }
    }

    bool metropolis(long long delta_energy, double temperature, double size_scale = 1.0) {
        if (delta_energy <= 0) return true;
        double denom = max(1e-9, temperature * size_scale);
        double z = static_cast<double>(delta_energy) / denom;
        if (z >= 50.0) return false;
        return rng.unit() < exp(-z);
    }

    vector<int> make_component_move(int anchor) {
        vector<int> ids;
        int cid = (0 <= anchor && anchor < V) ? comp_id[anchor] : -1;
        if (cid < 0) return ids;
        int l = comp_start[cid], r = comp_start[cid+1];
        int sz = r-l;
        if (sz <= 0 || sz > MAX_COMPONENT_MOVE) return ids;
        ids.insert(ids.end(), comp_cells.begin()+l, comp_cells.begin()+r);
        return ids;
    }

    vector<int> make_rectangle_move(int anchor, int max_side) {
        vector<int> ids;
        int ci = anchor / n, cj = anchor % n;
        int h = 2 + rng.uniform_int(max(1, max_side-1));
        int w = 2 + rng.uniform_int(max(1, max_side-1));

        // Sometimes use a thin stripe; sometimes a roughly square patch.
        int type = rng.uniform_int(4);
        if (type == 0) h = 1 + rng.uniform_int(3);
        if (type == 1) w = 1 + rng.uniform_int(3);

        int top = max(0, min(n-h, ci - rng.uniform_int(max(1, h))));
        int left = max(0, min(n-w, cj - rng.uniform_int(max(1, w))));
        int bottom = min(n, top+h), right = min(n, left+w);

        ids.reserve(min(MAX_RECT_MOVE, (bottom-top)*(right-left)));
        for (int i = top; i < bottom; ++i) {
            for (int j = left; j < right; ++j) {
                int id = i*n+j;
                if (is_movable[id]) ids.push_back(id);
                if (static_cast<int>(ids.size()) >= MAX_RECT_MOVE) return ids;
            }
        }
        return ids;
    }

    vector<int> make_pair_move(int anchor) {
        vector<int> ids;
        int first = is_movable[anchor] ? anchor : local_candidate_around(anchor, 1);
        int second = local_candidate_around(first, 2);
        ids.push_back(first);
        if (second != first) ids.push_back(second);
        return ids;
    }

    bool try_macro(double progress, double temperature, bool force_component = false) {
        if (movable.empty()) return false;
        int anchor = bad_list.empty() ? random_movable() : random_bad();
        vector<int> ids;
        int kind = force_component ? 0 : rng.uniform_int(100);

        if (kind < 38) {
            ids = make_component_move(anchor);
            if (ids.empty()) ids = make_rectangle_move(anchor, 48);
        } else if (kind < 76) {
            int side = 6 + static_cast<int>(42.0 * (1.0-progress));
            ids = make_rectangle_move(anchor, max(6, side));
        } else {
            ids = make_pair_move(anchor);
        }

        if (ids.empty()) return false;
        Delta d = apply_macro_tentatively(ids);
        long long e = energy_of(d, progress);
        // Large-neighbourhood proposals are tempered by sqrt(size), otherwise
        // almost every non-improving patch would have zero acceptance probability.
        double scale = max(1.0, sqrt(static_cast<double>(ids.size())));
        if (metropolis(e, temperature, scale)) {
            commit_macro(d);
            return true;
        }
        rollback_macro(ids);
        return false;
    }

    bool verify_current() const {
        for (int id = 0; id < V; ++id) {
            if (calc_residual(id) != 0) return false;
        }
        return true;
    }

    vector<unsigned char> run(double time_limit_seconds) {
        if (movable.empty()) {
            for (int id = 0; id < V; ++id) x[id] = (a[id] == 9);
            rebuild_counts_and_scores();
            return x;
        }

        const auto time_begin = chrono::steady_clock::now();
        auto elapsed = [&]() {
            return chrono::duration<double>(chrono::steady_clock::now()-time_begin).count();
        };

        vector<unsigned char> best_x(V, 0);
        int best_bad = INT_MAX;
        long long best_l1 = LLONG_MAX;
        long long last_snapshot_iter = -1000000;
        int restart = 0;

        auto snapshot_if_better = [&](long long iter, bool force = false) {
            int cur_bad = static_cast<int>(bad_list.size());
            if (cur_bad < best_bad || (cur_bad == best_bad && l1 < best_l1)) {
                bool substantial = force || best_bad == INT_MAX || cur_bad == 0
                                || cur_bad + max(1, best_bad/100) <= best_bad
                                || iter-last_snapshot_iter >= 200000;
                // best_bad / best_l1 always describe best_x.  Do not advance the
                // recorded metric unless the corresponding board is copied too.
                if (substantial) {
                    best_bad = cur_bad;
                    best_l1 = l1;
                    best_x = x;
                    last_snapshot_iter = iter;
                }
            }
        };

        while (elapsed() < time_limit_seconds) {
            initialise(restart++);
            long long iter = 0;
            long long last_bad_improvement_iter = 0;
            int local_best_bad = static_cast<int>(bad_list.size());
            int weight_bumps = 0;
            double global_progress = min(1.0, elapsed()/time_limit_seconds);
            double T0 = calibrate_temperature(global_progress);
            double reheat = 1.0;
            snapshot_if_better(iter, true);

            while (elapsed() < time_limit_seconds) {
                if (bad_list.empty()) {
                    if (verify_current()) return x;
                    rebuild_counts_and_scores();
                    if (bad_list.empty()) return x;
                }

                if ((iter & 1023LL) == 0) {
                    double now = elapsed();
                    if (now >= time_limit_seconds) break;
                    global_progress = min(1.0, now/time_limit_seconds);

                    int cur_bad = static_cast<int>(bad_list.size());
                    if (cur_bad < local_best_bad) {
                        local_best_bad = cur_bad;
                        last_bad_improvement_iter = iter;
                        reheat = max(1.0, reheat*0.92);
                        snapshot_if_better(iter);
                    }

                    long long stagnant = iter-last_bad_improvement_iter;
                    if (stagnant >= 60000LL + 10000LL*weight_bumps) {
                        increase_breakout_weights();
                        ++weight_bumps;
                        reheat = min(8.0, reheat*1.45);
                        last_bad_improvement_iter = iter;

                        // A persistent set of violations often indicates a wrong phase
                        // inside one weakly-coupled component.  Try a component inversion.
                        try_macro(global_progress, T0*reheat, true);
                        snapshot_if_better(iter);
                    }

                    // Restart after several unsuccessful breakout rounds.  Preserve more
                    // time for late restarts by lowering the threshold as the clock advances.
                    int max_bumps = global_progress < 0.65 ? 7 : 4;
                    if (weight_bumps >= max_bumps &&
                        iter-last_bad_improvement_iter >= 90000) {
                        break;
                    }
                }

                // Geometric cooling, with temporary reheating after stagnation.
                double p = global_progress;
                double base_T = T0 * pow(0.012, p);
                double T = max(0.08, base_T*reheat);

                // Roughly once per 512 micro moves, make a large-neighbourhood proposal.
                if ((iter & 511LL) == 0 && (rng.u32() & 3U) != 0U) {
                    try_macro(p, T, false);
                    ++iter;
                    continue;
                }

                // Best-of-k focused single-flip proposal.  k decreases near the start to
                // keep diversity, then increases near the end to sharpen the descent.
                int choices = (p < 0.25 ? 2 : (p < 0.75 ? 3 : 5));
                int chosen = -1;
                Delta chosen_d;
                long long chosen_e = LLONG_MAX;
                for (int z = 0; z < choices; ++z) {
                    int id = propose_single(p);
                    Delta d = evaluate_single(id);
                    long long e = energy_of(d, p);
                    if (e < chosen_e) {
                        chosen_e = e;
                        chosen = id;
                        chosen_d = d;
                    }
                }

                if (chosen >= 0 && metropolis(chosen_e, T)) {
                    apply_single(chosen, chosen_d);
                }
                ++iter;
            }

            snapshot_if_better(iter, true);
        }

        // The best observed state may still be invalid: this is a heuristic benchmark.
        x = best_x;
        rebuild_counts_and_scores();
        return x;
    }
};

} // namespace

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    if (!(cin >> N)) return 0;
    vector<unsigned char> digit(N*N);
    string s;
    for (int i = 0; i < N; ++i) {
        cin >> s;
        if (static_cast<int>(s.size()) != N) return 0;
        for (int j = 0; j < N; ++j) digit[i*N+j] = static_cast<unsigned char>(s[j]-'0');
    }

    uint64_t seed = chrono::high_resolution_clock::now().time_since_epoch().count();
    seed ^= uint64_t(reinterpret_cast<uintptr_t>(&seed));
    Solver solver(N, std::move(digit), seed);
    vector<unsigned char> answer = solver.run(SA_TIME_LIMIT);

    string out(N, '.');
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) out[j] = answer[i*N+j] ? 'o' : '.';
        cout << out << '\n';
    }
    return 0;
}