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

• 問題: No.5025 Forest Fire
• ユーザー: FplusFplusF
• 提出日時: 2026-10-24 16:19:42
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 1 ms / 2,000 ms
• コード長: 5,220 bytes
• コンパイル時間: 2,456 ms
• コンパイル使用メモリ: 344,424 KB
• 実行使用メモリ: 9,928 KB
• スコア: 155,234,569
• 最終ジャッジ日時: 2026-10-24 16:21:36
• 合計ジャッジ時間: 57,185 ms
• ジャッジサーバーID （参考情報）: judge6_0 / <nil>

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

ソースコード

//ライブラリへのリンク
//https://drive.google.com/drive/folders/1QDp2j94gwNBUf6lF2M-FTs9NVAKFpw5R

#include <bits/stdc++.h>
using namespace std;
using pii=pair<int,int>;
using tii=tuple<int,int,int>;
using qii=tuple<int,int,int,int>;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
constexpr int INF=1e9;
constexpr ll INF_ll=1e18;
#define rep(i,n) for (int i=0;i<(int)(n);i++)
#define replr(i,l,r) for (int i=(int)(l);i<(int)(r);i++)
#define all(v) v.begin(),v.end()
#define len(v) ((int)v.size())
template<class T> inline bool chmin(T &a,T b){
    if(a>b){
        a=b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T &a,T b){
    if(a<b){
        a=b;
        return true;
    }
    return false;
}

template<class T> inline bool chmin_ref(T &a,const T &b){
    if(a>b){
        a=b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax_ref(T &a,const T &b){
    if(a<b){
        a=b;
        return true;
    }
    return false;
}

namespace Timer{
    chrono::steady_clock::time_point program_start,start;
    void program_start_snap(){
        program_start=start=chrono::steady_clock::now();
    }
    void snap(){
        start=chrono::steady_clock::now();
    }
    int get_ms(){
        auto now=chrono::steady_clock::now();
        int ms=chrono::duration_cast<chrono::milliseconds>(now-start).count();
        return ms;
    }
    int get_ms_all_program(){
        auto now=chrono::steady_clock::now();
        int ms=chrono::duration_cast<chrono::milliseconds>(now-program_start).count();
        return ms;
    }
}

mt19937 mt;
uint32_t rand_int(uint32_t r){  //[0,r)
    assert(r!=0);
    return ((uint64_t)mt()*r)>>32;
}
int rand_int(int l,int r){  //[l,r)
    assert(l<r);
    return l+rand_int(r-l);
}
constexpr double one_div_mt_max=1.0/(double)mt19937::max();
double rand_double(){  //[0.0,1.0]
    return mt()*one_div_mt_max;
}
double rand_double(double l,double r){  //[l,r]
    return l+rand_double()*(r-l);
}
template<class T> T get_random_element(const vector<T> &v){
    assert(!v.empty());
    return v[rand_int(len(v))];
}

template<class T> void add(vector<T> &a,vector<T> b){
    for(auto i:b) a.push_back(i);
}

constexpr int N=50,K=100;

array<int,N*N> D;
array<array<int,4>,N*N> G;

int one(int i,int j){
    return i*N+j;
}
pii two(int x){
    return {x/N,x%N};
}

namespace Solver{
    
    const double P=0.6;
    
    double calc_score(const array<bool,N*N> &is_cut){
        
        array<double,N*N> prob;
        
        prob.fill(0);
        
        int cut_cnt=0;
        
        rep(i,N*N){
            if(D[i]==0) continue;
            
            if(is_cut[i]){
                cut_cnt++;
                continue;
            }
            
            double sum=(double)D[i]/10;
            
            /*for(auto j:G[i]){
                if(j==-1) continue;
                sum+=0.25*D[j]/10;
            }*/
            
            prob[i]=sum;
            
        }
        
        if(K<cut_cnt) return INF;
        
        array<int,N*N> root;
        
        root.fill(-1);
        
        rep(i,N*N){
            if(prob[i]<P) continue;
            if(root[i]!=-1) continue;
            
            queue<int> q;
            
            q.push(i);
            
            root[i]=i;
            
            while(!q.empty()){
                int x=q.front();
                q.pop();
                for(auto y:G[x]){
                    if(prob[y]<P) continue;
                    if(root[y]!=-1) continue;
                    root[y]=i;
                    q.push(y);
                }
            }
            
        }
        
        array<int,N*N> cnt;
        cnt.fill(0);
        
        
        rep(i,N*N){
            if(root[i]!=-1) cnt[root[i]]++;
        }
        
        double ret=0;
        
        rep(i,N*N){
            ret+=cnt[i]*cnt[i];
        }
        
        ret/=N*N;
        
        return ret;
    }
    
    void solve(){
        
        array<bool,N*N> is_cut;
        
        is_cut.fill(false);
        
        rep(i,N){
            is_cut[one(i,i)]=true;
            is_cut[one(i,N-1-i)]=true;
        }
        
        vector<int> ans;
        
        rep(i,N*N){
            if(D[i]==0) continue;
            if(is_cut[i]) ans.push_back(i);
        }
        
        assert(len(ans)<=K);
        
        cout << len(ans) << '\n';
        
        for(auto p:ans){
            auto [i,j]=two(p);
            cout << i << ' ' << j << '\n';
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    Timer::program_start_snap();
    
    int n,k;
    cin >> n >> k;
    
    
    rep(i,N){
        rep(j,N){
            char c;
            cin >> c;
            D[one(i,j)]=c-'0';
        }
    }
    
    rep(i,N*N) G[i].fill(-1);
    
    rep(i,N){
        rep(j,N){
            if(j+1<N){
                G[one(i,j)][3]=one(i,j+1);
                G[one(i,j+1)][2]=one(i,j);
            }
            if(i+1<N){
                G[one(i,j)][1]=one(i+1,j);
                G[one(i+1,j)][0]=one(i,j);
            }
        }
    }



    Solver::solve();
    exit(0);
}