#1195060 (C++23) No.5025 Forest Fire

• 問題: No.5025 Forest Fire
• ユーザー: Jinapetto
• 提出日時: 2026-10-24 16:30:37
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 1,912 ms / 2,000 ms
• コード長: 10,778 bytes
• コンパイル時間: 5,187 ms
• コンパイル使用メモリ: 393,804 KB
• 実行使用メモリ: 9,928 KB
• スコア: 151,796,299
• 最終ジャッジ日時: 2026-10-24 16:33:19
• 合計ジャッジ時間: 162,305 ms
• ジャッジサーバーID （参考情報）: judge5_0 / <nil>

ファイルパターン	結果
other	AC * 50

ソースコード

#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC target("avx2")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using vi = vector<int>;
using vl = vector<long long>;
using vs = vector<string>;
using vc = vector<char>;
using vb = vector<bool>;
using vvi = vector<vector<int>>;
using vvvi = vector<vector<vector<int>>>;
using vvvvi = vector<vector<vector<vector<int>>>>;
using vvl = vector<vector<long long>>;
using vvvl = vector<vector<vector<long long>>>;
using vvvvl = vector<vector<vector<vector<long long>>>>;
using vvc = vector<vector<char>>;
using vvb = vector<vector<bool>>;
using vvvb = vector<vector<vector<bool>>>;
using vvvvb = vector<vector<vector<vector<bool>>>>;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ALL(obj) (obj).begin(),(obj).end()

struct Timer{
    chrono::steady_clock::time_point st;
    Timer(){
        st = chrono::steady_clock::now();
    }
    // 2sec -> 7e7 times
    inline double get(){
        return chrono::duration<double>(chrono::steady_clock::now() - st).count();
    }
} tim;

struct XorShift{
    using result_type = uint32_t;
    uint64_t x = 2003082720030827ull;
    inline uint32_t operator()(){
        x^=x<<7;
        x^=x>>9;
        return (uint32_t)x; 
    }
    // [0, m)
    inline uint32_t i(uint32_t m){
        return m ? (uint32_t)((uint64_t)(*this)()*m >> 32) : (*this)();
    }
    // [0.0, 1.0)
    inline double d(){
        return (double)((*this)() & 0xFFFFFF) / 16777216.0;
    }
    static constexpr uint32_t min() { return 0; }
    static constexpr uint32_t max() { return UINT32_MAX; }
} rnd;

// 2sec -> 1e9 times
inline bool ac(double start_time, double cur_time, double end_time, double score_dist, double start_temp, double end_temp){
    // double temp = start_temp + (end_temp - start_temp) * (cur_time - start_time) / (end_time - start_time);
    double temp = start_temp * pow(end_temp / start_temp, (cur_time - start_time) / (end_time - start_time)); // end_temp = 0 とすると常に temp = 0
    if(score_dist >= 0.0) return true;
    if(score_dist <= -8.0 * temp) return false;
    return rnd.d() < exp(score_dist/temp);
}

// 2sec -> 7e8 times
inline double mn_ac(double start_time, double cur_time, double end_time, double start_temp, double end_temp){
    double temp = start_temp + (end_temp - start_temp) * (cur_time - start_time) / (end_time - start_time);
    // double temp = start_temp * pow(end_temp / start_temp, (cur_time - start_time) / (end_time - start_time)); // end_temp = 0 とすると常に temp = 0
    return log(rnd.d()) * temp;
}

struct dsu {
    dsu(int sz) : n(sz), par(n, -1) {}

    int merge(int a, int b) {
        int x = leader(a), y = leader(b);
        if(x == y) return x;
        if(-par[x] < -par[y]) swap(x, y);
        par[x] += par[y];
        par[y] = x;
        return x;
    }

    bool same(int a, int b) { return leader(a) == leader(b); }

    int leader(int a) {
        if(par[a] < 0) return a;
        return par[a] = leader(par[a]);
    }

    int size(int a) { return -par[leader(a)]; }

    vector<vector<int>> groups() {
        vector<int> leader_buf(n), group_size(n);
        for(int i = 0; i < n; i++) {
            leader_buf[i] = leader(i);
            group_size[leader_buf[i]]++;
        }
        vector<vector<int>> result(n);
        for(int i = 0; i < n; i++) { result[i].reserve(group_size[i]); }
        for(int i = 0; i < n; i++) { result[leader_buf[i]].push_back(i); }
        result.erase(remove_if(result.begin(), result.end(), [&](const vector<int>& v) { return v.empty(); }),
                     result.end());
        return result;
    }

private:
    int n;
    vector<int> par;
};


const int n = 50, k = 100;
uint8_t d[n][n];

void input(){
    int tmp;
    cin >> tmp >> tmp;
    rep(i,n){
        string s;
        cin >> s;
        rep(j,n) d[i][j] = s[j] - '0';
    }
}

vector<pair<int,int>> greedy(){
    vector<pair<int,int>> ans;
    rep(x,n)if(d[x][25] != 0) ans.push_back({x, 25});
    rep(y,n)if(y != 25 && d[25][y] != 0) ans.push_back({25, y});
    return ans;
}

vector<pair<int,int>> yaki(){
    const int sz = 10;
    bool dry[sz][n][n];
    rep(i,sz)rep(x,n)rep(y,n) dry[i][x][y] = (rnd.d() <= d[x][y] / 10.0);
    vector<vector<pair<int,int>>> ren[sz];
    rep(i,sz){
        dsu uf(n * n);
        rep(x,n)rep(y,n)if(dry[x][y]){
            if(x != n - 1 && dry[x + 1][y]) uf.merge(x * n + y, (x + 1) * n + y);
            if(y != n - 1 && dry[x][y + 1]) uf.merge(x * n + y, x * n + y + 1);
        }
        vvi grs = uf.groups();
        for(vi gr : grs){
            int x0 = gr[0] / n;
            int y0 = gr[0] % n;
            if(!dry[x0][y0]) continue;
            ren[i].push_back({});
            for(int j : gr){
                ren[i].back().push_back({j / n, j % n});
            }
        }
    }

    int vis[n][n] = {};
    int vis_idx = 0;

    int horizontal[n], vertical[n];
    rep(i,n) horizontal[i] = 25;
    rep(i,n) vertical[i] = 25;

    const int pena = 20000 * sz;
    // const int start_pena = 100;
    // const int end_pena;

    auto calc_score = [&]() -> int {
        int cnt = 0;
        vis_idx++;
        rep(y,n){
            if(vis[horizontal[y]][y] != vis_idx && d[horizontal[y]][y] != 0) cnt++;
            vis[horizontal[y]][y] = vis_idx;
            if(y != 0){
                if(horizontal[y - 1] + 1 < horizontal[y]){
                    for(int x = horizontal[y - 1] + 1;x < horizontal[y];x++){
                        if(vis[x][y] != vis_idx && d[x][y] != 0) cnt++;
                        vis[x][y] = vis_idx;
                    }
                }else if(horizontal[y - 1] - 1 > horizontal[y]){
                    for(int x = horizontal[y - 1] - 1;x > horizontal[y];x--){
                        if(vis[x][y] != vis_idx && d[x][y] != 0) cnt++;
                        vis[x][y] = vis_idx;
                    }
                }
            }
        }
        rep(x,n){
            if(vis[x][vertical[x]] != vis_idx && d[x][vertical[x]] != 0) cnt++;
            vis[x][vertical[x]] = vis_idx;
            if(x != 0){
                if(vertical[x - 1] + 1 < vertical[x]){
                    for(int y = vertical[x - 1] + 1;y < vertical[x];y++){
                        if(vis[x][y] != vis_idx && d[x][y] != 0) cnt++;
                        vis[x][y] = vis_idx;
                    }
                }else if(vertical[x - 1] - 1 > vertical[x]){
                    for(int y = vertical[x - 1] - 1;y > vertical[x];y--){
                        if(vis[x][y] != vis_idx && d[x][y] != 0) cnt++;
                        vis[x][y] = vis_idx;
                    }
                }
            }
        }

        if(k < cnt) return (int)1e9;

        int score = pena * max(cnt - k, 0);
        // int score = 0;

        rep(i,sz){
            rep(j,ren[i].size()){
                int cnt[4] = {};
                for(auto [x, y] : ren[i][j])if(vis[x][y] != vis_idx){
                    int idx = 0;
                    if(horizontal[y] < x) idx |= 1;
                    if(vertical[x] < y) idx |= 2;
                    cnt[idx]++;
                }
                rep(l,4) score += cnt[l] * cnt[l];
            }
        }

        return score;
    };

    int score = calc_score();

    double start_time = tim.get();
    double cur_time = start_time;
    double end_time = 1.95;
    double start_temp = 1000 * sz;
    double end_temp = 10 * sz;
    cerr << "score = " << score << endl;
    cerr << "start_temp = " << start_temp << endl;

    const int op_sz = 2;
    int pr[op_sz] = {100, 100};
    rep(i,op_sz - 1) pr[i + 1] += pr[i];

    for(int yaki_cnt = 0;;yaki_cnt++){
        if((yaki_cnt & 15) == 0){
            cur_time = tim.get();
            if(cur_time > end_time){
                cerr << "yaki_cnt = " << yaki_cnt << endl;
                break;
            }
        }

        int op = rnd.i(pr[op_sz - 1]);
        if(op < pr[0]){
            int y = rnd.i(n);
            int i = rnd.i(5) - 1;
            if(i == 0 || horizontal[y] + i < 0 || n <= horizontal[y] + i) continue;

            horizontal[y] += i;
            int nscore = calc_score();
            if(ac(start_time, cur_time, end_time, score - nscore, start_temp, end_temp)){
                score = nscore;
            }else{
                horizontal[y] -= i;
            }
        }else if(op < pr[1]){
            int x = rnd.i(n);
            int i = rnd.i(5) - 1;
            if(i == 0 || vertical[x] + i < 0 || n <= vertical[x] + i) continue;

            vertical[x] += i;
            int nscore = calc_score();
            if(ac(start_time, cur_time, end_time, score - nscore, start_temp, end_temp)){
                score = nscore;
            }else{
                vertical[x] -= i;
            }
        }
    }

    // 復元
    vector<pair<int,int>> ans;
    vis_idx++;
    rep(y,n){
        if(vis[horizontal[y]][y] != vis_idx && d[horizontal[y]][y] != 0) ans.push_back({horizontal[y], y});
        vis[horizontal[y]][y] = vis_idx;
        if(y != 0){
            if(horizontal[y - 1] + 1 < horizontal[y]){
                for(int x = horizontal[y - 1] + 1;x < horizontal[y];x++){
                    if(vis[x][y] != vis_idx && d[x][y] != 0) ans.push_back({x, y});
                    vis[x][y] = vis_idx;
                }
            }else if(horizontal[y - 1] - 1 > horizontal[y]){
                for(int x = horizontal[y - 1] - 1;x > horizontal[y];x--){
                    if(vis[x][y] != vis_idx && d[x][y] != 0) ans.push_back({x, y});
                    vis[x][y] = vis_idx;
                }
            }
        }
    }
    rep(x,n){
        if(vis[x][vertical[x]] != vis_idx && d[x][vertical[x]] != 0) ans.push_back({x, vertical[x]});
        vis[x][vertical[x]] = vis_idx;
        if(x != 0){
            if(vertical[x - 1] + 1 < vertical[x]){
                for(int y = vertical[x - 1] + 1;y < vertical[x];y++){
                    if(vis[x][y] != vis_idx && d[x][y] != 0) ans.push_back({x, y});
                    vis[x][y] = vis_idx;
                }
            }else if(vertical[x - 1] - 1 > vertical[x]){
                for(int y = vertical[x - 1] - 1;y > vertical[x];y--){
                    if(vis[x][y] != vis_idx && d[x][y] != 0) ans.push_back({x, y});
                    vis[x][y] = vis_idx;
                }
            }
        }
    }

    assert(ans.size() <= k);
    return ans;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    input();
    vector<pair<int,int>> ans = yaki();
    // vector<pair<int,int>> ans = greedy();
    
    cout << ans.size() << '\n';
    for(auto [x, y] : ans) cout << x << ' ' << y << '\n';
    return 0;
}