結果
問題 | No.5019 Hakai Project |
ユーザー | FplusFplusF |
提出日時 | 2023-11-19 19:44:46 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 15,106 bytes |
コンパイル時間 | 5,008 ms |
コンパイル使用メモリ | 311,748 KB |
実行使用メモリ | 6,676 KB |
スコア | 2,573,546,361 |
最終ジャッジ日時 | 2023-11-19 19:49:10 |
合計ジャッジ時間 | 92,006 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2,951 ms
6,676 KB |
testcase_01 | TLE | - |
testcase_02 | AC | 2,955 ms
6,676 KB |
testcase_03 | AC | 2,881 ms
6,676 KB |
testcase_04 | AC | 2,809 ms
6,676 KB |
testcase_05 | AC | 2,786 ms
6,676 KB |
testcase_06 | AC | 2,897 ms
6,676 KB |
testcase_07 | AC | 2,978 ms
6,676 KB |
testcase_08 | AC | 2,877 ms
6,676 KB |
testcase_09 | TLE | - |
testcase_10 | AC | 2,806 ms
6,676 KB |
testcase_11 | AC | 2,865 ms
6,676 KB |
testcase_12 | AC | 2,884 ms
6,676 KB |
testcase_13 | AC | 2,842 ms
6,676 KB |
testcase_14 | AC | 2,866 ms
6,676 KB |
testcase_15 | AC | 2,804 ms
6,676 KB |
testcase_16 | AC | 2,782 ms
6,676 KB |
testcase_17 | AC | 2,795 ms
6,676 KB |
testcase_18 | AC | 2,985 ms
6,676 KB |
testcase_19 | AC | 2,858 ms
6,676 KB |
testcase_20 | AC | 2,932 ms
6,676 KB |
testcase_21 | AC | 2,892 ms
6,676 KB |
testcase_22 | AC | 2,825 ms
6,676 KB |
testcase_23 | AC | 2,907 ms
6,676 KB |
testcase_24 | AC | 2,899 ms
6,676 KB |
testcase_25 | AC | 2,902 ms
6,676 KB |
testcase_26 | AC | 2,871 ms
6,676 KB |
testcase_27 | AC | 2,838 ms
6,676 KB |
testcase_28 | AC | 2,797 ms
6,676 KB |
testcase_29 | AC | 2,810 ms
6,676 KB |
testcase_30 | AC | 2,907 ms
6,676 KB |
testcase_31 | AC | 2,848 ms
6,676 KB |
testcase_32 | AC | 2,923 ms
6,676 KB |
testcase_33 | AC | 2,825 ms
6,676 KB |
testcase_34 | AC | 2,974 ms
6,676 KB |
testcase_35 | AC | 2,954 ms
6,676 KB |
testcase_36 | AC | 2,823 ms
6,676 KB |
testcase_37 | AC | 2,933 ms
6,676 KB |
testcase_38 | AC | 2,870 ms
6,676 KB |
testcase_39 | AC | 2,925 ms
6,676 KB |
testcase_40 | AC | 2,979 ms
6,676 KB |
testcase_41 | AC | 2,951 ms
6,676 KB |
testcase_42 | AC | 2,827 ms
6,676 KB |
testcase_43 | AC | 2,810 ms
6,676 KB |
testcase_44 | AC | 2,909 ms
6,676 KB |
testcase_45 | AC | 2,907 ms
6,676 KB |
testcase_46 | TLE | - |
testcase_47 | AC | 2,852 ms
6,676 KB |
testcase_48 | AC | 2,992 ms
6,676 KB |
testcase_49 | TLE | - |
ソースコード
#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 ld=long double;const int INF=1e9;#define rep(i,n) for (int i=0;i<(int)(n);i++)#define all(v) v.begin(),v.end()template<class T> void chmin(T &a,T b){if(a>b){a=b;}}template<class T> void chmax(T &a,T b){if(a<b){a=b;}}auto start=chrono::system_clock::now();mt19937 mt;int N,M;vector<string> A;struct bomb_info{int C,L;vector<int> a,b;};vector<bomb_info> bomb;int to(int i,int j){return i*N+j;}int to(pii x){return to(x.first,x.second);}pii back(int x){int i=x/N;return {i,x-i*N};}bool outside(int i,int j){if(i<0||N<=i||j<0||N<=j) return true;return false;}void output_answer(vector<pii> &ans){cout << (int)ans.size() << '\n';for(auto &[s,t]:ans){if(s==1) cout << s << ' ' << char(t) << '\n';else cout << s << ' ' << t+1 << '\n';}}struct Solver{vector<int> bomb_v;vector<int> shop_idx;int can_bomb=13;vector<vector<double>> near_shop_dist(int k_th){vector<vector<double>> ave(N,vector<double>(N));rep(si,N){rep(sj,N){vector<int> v;for(auto &ij:bomb_v){int i,j;tie(i,j)=back(ij);v.push_back(abs(i-si)+abs(j-sj));}sort(all(v));int sum=0;rep(i,k_th) sum+=v[i];ave[si][sj]=double(sum)/double(k_th);}}return ave;}vector<int> ok_bomb;vector<pii> bomb_cover(vector<vector<double>> ave){vector<pair<double,int>> bomb_sort(M);rep(i,M){bomb_sort[i]={double(bomb[i].C)/double(bomb[i].L),i};}sort(all(bomb_sort));ok_bomb.resize(M,0);rep(i,can_bomb) ok_bomb[bomb_sort[i].second]=1;vector<string> now_grid=A;vector<pii> ret;while(true){double min_score=INF;pii max_cover={-1,-1};rep(i,N){rep(j,N){rep(bomb_idx,M){if(ok_bomb[bomb_idx]==0) continue;int cnt=0;rep(k,bomb[bomb_idx].L){int ti=i+bomb[bomb_idx].a[k],tj=j+bomb[bomb_idx].b[k];if(outside(ti,tj)) continue;if(now_grid[ti][tj]!='.') cnt++;}double now_score=INF;if(0<cnt) now_score=double(bomb[bomb_idx].C+ave[i][j]*5.0)/double(cnt);if(now_score<min_score){min_score=now_score;max_cover={to(i,j),bomb_idx};}}}}if(max_cover.first==-1) break;ret.push_back(max_cover);int ni,nj;tie(ni,nj)=back(max_cover.first);rep(k,bomb[max_cover.second].L){int ti=ni+bomb[max_cover.second].a[k],tj=nj+bomb[max_cover.second].b[k];if(outside(ti,tj)) continue;now_grid[ti][tj]='.';}}return ret;}vector<int> pi={0,1,0,-1},pj={1,0,-1,0};int root_cost(int a,int b,vector<string> &grid,int bomb_cnt){int ai,aj,bi,bj;tie(ai,aj)=back(a);tie(bi,bj)=back(b);vector<vector<int>> dist(N,vector<int>(N,INF));dist[ai][aj]=0;priority_queue<pair<int,pii>,vector<pair<int,pii>>,greater<pair<int,pii>>> pq;pq.push({0,{ai,aj}});while(!pq.empty()){int d;pii ij;tie(d,ij)=pq.top();pq.pop();int i,j;tie(i,j)=ij;if(dist[i][j]<d) continue;if(i==bi&&j==bj) break;rep(k,4){int ti=i+pi[k],tj=j+pj[k];if(outside(ti,tj)) continue;int cost=(bomb_cnt+1)*(bomb_cnt+1);if(grid[ti][tj]!='.') cost*=2;if(dist[i][j]+cost<dist[ti][tj]){dist[ti][tj]=d+cost;pq.push({dist[ti][tj],{ti,tj}});}}}return dist[bi][bj];}string root(int a,int b,vector<string> &grid,int bomb_cnt){int ai,aj,bi,bj;tie(ai,aj)=back(a);tie(bi,bj)=back(b);vector<vector<int>> dist(N,vector<int>(N,INF));dist[ai][aj]=0;vector<vector<pii>> prev(N,vector<pii>(N));priority_queue<pair<int,pii>,vector<pair<int,pii>>,greater<pair<int,pii>>> pq;pq.push({0,{ai,aj}});while(!pq.empty()){int d;pii ij;tie(d,ij)=pq.top();pq.pop();int i,j;tie(i,j)=ij;if(dist[i][j]<d) continue;if(i==bi&&j==bj) break;rep(k,4){int ti=i+pi[k],tj=j+pj[k];if(outside(ti,tj)) continue;int cost=(bomb_cnt+1)*(bomb_cnt+1);if(grid[ti][tj]!='.') cost*=2;if(dist[i][j]+cost<dist[ti][tj]){dist[ti][tj]=d+cost;prev[ti][tj]={i,j};pq.push({dist[ti][tj],{ti,tj}});}}}string ret;int ni=bi,nj=bj;while(!(ni==ai&&nj==aj)){int ti,tj;tie(ti,tj)=prev[ni][nj];if(ti==ni&&tj<nj) ret.push_back('R');if(ti==ni&&nj<tj) ret.push_back('L');if(tj==nj&&ti<ni) ret.push_back('D');if(tj==nj&&ni<ti) ret.push_back('U');ni=ti;nj=tj;}reverse(all(ret));return ret;}int calc_score(vector<pii> &ans){int ni=0,nj=0;vector<int> bomb_cnt(M,0);int b=0;vector<string> now_grid=A;int c=0;for(auto &[s,t]:ans){if(s==1){if(char(t)=='L') nj--;else if(char(t)=='R') nj++;else if(char(t)=='U') ni--;else if(char(t)=='D') ni++;else assert(0);assert(!outside(ni,nj));if(now_grid[ni][nj]=='.') c+=(b+1)*(b+1);else c+=2*(b+1)*(b+1);}else if(s==2){assert(now_grid[ni][nj]=='@');int y=t;assert(0<=y&&y<=M-1);bomb_cnt[y]++;b++;c+=bomb[y].C;}else if(s==3){int z=t;assert(0<=z&&z<=M-1);assert(1<=bomb_cnt[z]);bomb_cnt[z]--;b--;rep(k,bomb[z].L){int ti=ni+bomb[z].a[k],tj=nj+bomb[z].b[k];if(outside(ti,tj)) continue;now_grid[ti][tj]='.';}}else{assert(0);}}rep(i,N){rep(j,N){if(now_grid[i][j]!='.'){return 1;}}}return max(10ll,1000000000000ll/(10000+c));}vector<pii> cover_to_ans(vector<pii> &cover_v){vector<string> now_grid=A;vector<pii> now_ans;int now=0;int shop_cnt=0;rep(i,N){rep(j,N){if(A[i][j]=='@') shop_cnt++;}}int bomb_cnt=0;set<pii> last_shop_set;rep(t,int(cover_v.size())){int idx,now_bomb_idx;tie(idx,now_bomb_idx)=cover_v[t];int idx_i,idx_j;tie(idx_i,idx_j)=back(idx);int before_shop_cnt=shop_cnt;rep(k,bomb[now_bomb_idx].L){int ti=idx_i+bomb[now_bomb_idx].a[k],tj=idx_j+bomb[now_bomb_idx].b[k];if(outside(ti,tj)) continue;if(now_grid[ti][tj]=='@') shop_cnt--;}if(shop_cnt==0&&!last_shop_set.count(cover_v[t])){last_shop_set.insert(cover_v[t]);shop_cnt=before_shop_cnt;cover_v.push_back(cover_v[t]);cover_v.erase(cover_v.begin()+t);t--;continue;}pii mn={INF,INF};for(auto &x:bomb_v){int i,j;tie(i,j)=back(x);if(now_grid[i][j]=='@') chmin(mn,{root_cost(now,x,now_grid,bomb_cnt),x});}if(mn.first!=INF){for(auto &i:root(now,mn.second,now_grid,bomb_cnt)){now_ans.push_back({1,i});}now=mn.second;int i,j;tie(i,j)=back(mn.second);if(shop_cnt==0){for(int k=t;k<int(cover_v.size());k++){now_ans.push_back({2,cover_v[k].second});bomb_cnt++;}}else{now_ans.push_back({2,now_bomb_idx});bomb_cnt++;}}for(auto &j:root(now,idx,now_grid,bomb_cnt)){now_ans.push_back({1,j});}now=idx;now_ans.push_back({3,now_bomb_idx});bomb_cnt--;rep(k,bomb[now_bomb_idx].L){int ti=idx_i+bomb[now_bomb_idx].a[k],tj=idx_j+bomb[now_bomb_idx].b[k];if(outside(ti,tj)) continue;now_grid[ti][tj]='.';}}return now_ans;}int fake_root_cost(int a,int b,int bomb_cnt){int ai,aj,bi,bj;tie(ai,aj)=back(a);tie(bi,bj)=back(b);return (abs(ai-bi)+abs(aj-bj))*(bomb_cnt+1)*(bomb_cnt+1);}int fake_cost(vector<pii> cover_v,vector<vector<vector<int>>> &shop_explosion){vector<int> shop_ok(int(bomb_v.size()),1);int now=0;int shop_cnt=int(bomb_v.size());int bomb_cnt=0;set<pii> last_shop_set;int ret=0;rep(t,int(cover_v.size())){int idx,now_bomb_idx;tie(idx,now_bomb_idx)=cover_v[t];int idx_i,idx_j;tie(idx_i,idx_j)=back(idx);int before_shop_cnt=shop_cnt;for(auto &ij:shop_explosion[idx][now_bomb_idx]){if(shop_ok[shop_idx[ij]]==1){shop_cnt--;}}if(shop_cnt==0&&!last_shop_set.count(cover_v[t])){last_shop_set.insert(cover_v[t]);shop_cnt=before_shop_cnt;cover_v.push_back(cover_v[t]);cover_v.erase(cover_v.begin()+t);t--;continue;}pii mn={INF,INF};for(auto &x:bomb_v){if(shop_ok[shop_idx[x]]==1) chmin(mn,{fake_root_cost(now,x,bomb_cnt),x});}if(mn.first!=INF){ret+=mn.first;now=mn.second;int i,j;tie(i,j)=back(mn.second);if(shop_cnt==0){for(int k=t;k<int(cover_v.size());k++){ret+=bomb[cover_v[k].second].C;bomb_cnt++;}}else{ret+=bomb[now_bomb_idx].C;bomb_cnt++;}}ret+=fake_root_cost(now,idx,bomb_cnt);now=idx;bomb_cnt--;for(auto &ij:shop_explosion[idx][now_bomb_idx]){shop_ok[shop_idx[ij]]=0;}}return ret;}void solve(){shop_idx.resize(N*N);int cnt_b=0;rep(i,N){rep(j,N){if(A[i][j]=='@'){bomb_v.push_back(to(i,j));shop_idx[to(i,j)]=cnt_b;cnt_b++;}}}vector<pii> cover_v=bomb_cover(near_shop_dist(5));int block_size=50/3;sort(cover_v.begin(),cover_v.end(),[&](pii i,pii j){int il,ir,jl,jr;tie(il,ir)=back(i.first);tie(jl,jr)=back(j.first);int block_i=il/block_size,block_j=jl/block_size;if(block_i!=block_j) return il<jl;if(block_i&1) return ir>jr;else return ir<jr;});vector<vector<vector<int>>> shop_explosion(N*N,vector<vector<int>>(M));rep(i,N){rep(j,N){rep(bomb_idx,M){if(ok_bomb[bomb_idx]==0) continue;rep(k,bomb[bomb_idx].L){int ti=i+bomb[bomb_idx].a[k],tj=j+bomb[bomb_idx].b[k];if(outside(ti,tj)) continue;if(A[ti][tj]=='@') shop_explosion[to(i,j)][bomb_idx].push_back(to(ti,tj));}}}}vector<pii> min_cost_cover_v=cover_v;int min_cost=fake_cost(min_cost_cover_v,shop_explosion);int cover_size=min_cost_cover_v.size();while(true){auto now=chrono::system_clock::now();int ms=chrono::duration_cast<chrono::milliseconds>(now-start).count();if(2700<=ms) break;if(mt()%2==0){int a=mt()%cover_size,b=mt()%cover_size,c=mt()%cover_size;if(a==b||b==c||a==c) continue;swap(min_cost_cover_v[a],min_cost_cover_v[b]);swap(min_cost_cover_v[b],min_cost_cover_v[c]);int new_cost=fake_cost(min_cost_cover_v,shop_explosion);if(new_cost<=min_cost){min_cost=new_cost;}else{swap(min_cost_cover_v[b],min_cost_cover_v[c]);swap(min_cost_cover_v[a],min_cost_cover_v[b]);}}else{int a=mt()%cover_size,b=mt()%cover_size;if(a==b) continue;swap(min_cost_cover_v[a],min_cost_cover_v[b]);int new_cost=fake_cost(min_cost_cover_v,shop_explosion);if(new_cost<=min_cost) min_cost=new_cost;else swap(min_cost_cover_v[a],min_cost_cover_v[b]);}}vector<pii> ans=cover_to_ans(min_cost_cover_v);output_answer(ans);}}Solver;int main(){ios::sync_with_stdio(false);cin.tie(nullptr);cin >> N >> M;A.resize(N);rep(i,N) cin >> A[i];bomb.resize(M);rep(i,M){cin >> bomb[i].C >> bomb[i].L;bomb[i].a.resize(bomb[i].L);bomb[i].b.resize(bomb[i].L);rep(j,bomb[i].L) cin >> bomb[i].a[j] >> bomb[i].b[j];}Solver.solve();}