結果
| 問題 | No.5025 Forest Fire |
| コンテスト | |
| ユーザー |
 FplusFplusF
|
| 提出日時 | 2026-10-24 16:57:42 |
| 言語 | C++23 (gcc 15.3.0 + boost 1.92.0 + ACL) |
| 結果 |
AC
不安定
|
| 実行時間 | 18 ms / 2,000 ms |
| + 495µs | |
| コード長 | 8,944 bytes |
| 記録 | |
| コンパイル時間 | 2,929 ms |
| コンパイル使用メモリ | 354,972 KB |
| 実行使用メモリ | 9,924 KB |
| スコア | 157,097,958 |
| 最終ジャッジ日時 | 2026-10-24 16:58:41 |
| 合計ジャッジ時間 | 59,048 ms |
|
ジャッジサーバーID （参考情報） |
judge3_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.5;
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);
while(Timer::get_ms()<1500){
array<double,N*N> prob;
prob.fill(0);
rep(i,N*N){
if(D[i]==0) continue;
if(is_cut[i]) continue;
double sum=(double)D[i]/10;
prob[i]=sum;
}
array<int,N*N> root;
root.fill(-1);
int comp_cnt=0;
rep(i,N*N){
if(prob[i]<P) continue;
if(root[i]!=-1) continue;
queue<int> q;
q.push(i);
root[i]=comp_cnt;
comp_cnt++;
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]=root[i];
q.push(y);
}
}
}
array<int,N*N> cnt;
cnt.fill(0);
rep(i,N*N){
if(root[i]!=-1) cnt[root[i]]++;
}
vector<int> ord(comp_cnt);
rep(i,comp_cnt) ord[i]=i;
sort(all(ord),[&](int i,int j){return cnt[i]>cnt[j];});
//if(20<len(ord)) ord.resize(20);
int pre_score=calc_score(is_cut);
double best_score=0;
auto best_is_cut=is_cut;
for(auto r:ord){
cerr <<r << " " << cnt[r] << endl;
int max_i=-INF,max_j=-INF,min_i=INF,min_j=INF;
rep(i,N){
rep(j,N){
if(root[one(i,j)]==r){
chmax(max_i,i);
chmax(max_j,j);
chmin(min_i,i);
chmin(min_j,j);
}
}
}
rep(d,2){
auto new_is_cut=is_cut;
int new_cnt=0;
if(d==0){
replr(i,min_i,max_i+1){
int p=one(i,(min_j+max_j)/2);
if(root[p]!=r) continue;
if(D[p]!=0&&!is_cut[p]) new_cnt++;
new_is_cut[p]=true;
}
}
if(d==1){
replr(j,min_j,max_j+1){
int p=one((min_i+max_i)/2,j);
if(root[p]!=r) continue;
if(D[p]!=0&&!is_cut[p]) new_cnt++;
new_is_cut[p]=true;
}
}
int new_score=calc_score(new_is_cut);
double good_score=(double)(pre_score-new_score)/new_cnt;
//cerr << new_score << " " << best_score << endl;
if(chmax(best_score,good_score)){
best_is_cut=new_is_cut;
}
}
}
if(is_cut==best_is_cut) break;
is_cut=best_is_cut;
}
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);
}