結果
| 問題 | No.5019 Hakai Project |
| ユーザー |
 askr58
|
| 提出日時 | 2023-11-18 01:59:06 |
| 言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 8 ms / 3,000 ms |
| コード長 | 5,027 bytes |
| コンパイル時間 | 2,603 ms |
| コンパイル使用メモリ | 228,188 KB |
| 実行使用メモリ | 6,676 KB |
| スコア | 281,297,245 |
| 最終ジャッジ日時 | 2023-11-18 01:59:15 |
| 合計ジャッジ時間 | 7,717 ms |
|
ジャッジサーバーID （参考情報） |
judge13 / judge14 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 50 |
コンパイルメッセージ
main.cpp: In lambda function:
main.cpp:101:49: warning: 'res.bomb_instance::id' may be used uninitialized [-Wmaybe-uninitialized]
101 | for(int i=0;i<m;i++)if(bombs[i].id==res.id)index=i;
| ~~~~^~
main.cpp:67:23: note: 'res' declared here
67 | bomb_instance res;
| ^~~
ソースコード
#include <bits/stdc++.h>using namespace std;using ll=long long;ll linf=1000000000000000000;template <typename T>bool chmax(T& a,T b){if(a<b){a=b;return true;}else return false;}template <typename T>bool chmin(T& a,T b){if(a>b){a=b;return true;}else return false;}vector<int> dx={1,0,-1,0};vector<int> dy={0,1,0,-1};struct bomb{ll c,l;int id;vector<pair<int,int>> range;bomb(){}bomb(ll c,ll l,int id):c(c),l(l),id(id){range.resize(l);}};struct bomb_instance{int x,y;int id;bomb_instance(){}bomb_instance(int x,int y,int id):x(x),y(y),id(id){}};int n,m;vector<bomb> bombs;vector<bomb_instance> locates;vector<string> grid;string ans;int ans_count;void read_input(){cin>>n>>m;ans_count=0;bombs.resize(m);grid.resize(n);for(int i=0;i<n;i++)cin>>grid[i];for(int i=0;i<m;i++){ll c,l;cin>>c>>l;bombs[i]=bomb(c,l,i);for(int j=0;j<l;j++){int a,b;cin>>a>>b;bombs[i].range[j]=make_pair(a,b);}}sort(bombs.begin(),bombs.end(),[](bomb a,bomb b)->bool{return a.c<b.c;});}void greedy(){vector<string> copy_grid=grid;auto good_bomb=[&](int x,int y)->void{bomb_instance res;int max_score=0;for(int i=0;i<m;i++){int nx=0,ny=0;for(auto [lx,ly]:bombs[i].range){if(x<n/2){if(y<n/2){if(lx>0||ly>0)continue;}else{if(lx>0||ly<0)continue;}}else{if(y<n/2){if(lx<0||ly>0)continue;}else{if(lx<0||ly<0)continue;}}if(abs(nx)+abs(ny)<abs(lx)+abs(ly)){nx=lx;ny=ly;}}int score=0;for(auto [lx,ly]:bombs[i].range){int mx=x-nx+lx,my=y-ny+ly;if(mx<0||mx>=n||my<0||my>=n)continue;if(copy_grid[mx][my]!='.')score++;}if(score>max_score){max_score=score;res=bomb_instance(x-nx,y-ny,bombs[i].id);}}int index=0;for(int i=0;i<m;i++)if(bombs[i].id==res.id)index=i;for(auto [lx,ly]:bombs[index].range){if(res.x+lx<0||res.x+lx>=n||res.y+ly<0||res.y+ly>=n)continue;copy_grid[res.x+lx][res.y+ly]='.';}locates.push_back(res);};for(int i=0;i<n-1;i++){for(int j=0;j<=i;j++){if(j>=n/2||i-j>=n/2)continue;int x=j,y=i-j;if(copy_grid[x][y]!='.')good_bomb(x,y);if(copy_grid[n-1-x][y]!='.')good_bomb(n-1-x,y);if(copy_grid[x][n-1-y]!='.')good_bomb(x,n-1-y);if(copy_grid[n-1-x][n-1-y]!='.')good_bomb(n-1-x,n-1-y);//for(string s:copy_grid)cout<<s<<endl;}}//cout<<endl;//for(string s:copy_grid)cout<<s<<endl;}void go_straight(int from,int to){int now_x=from/n,now_y=from%n,next_x=to/n,next_y=to%n;if(now_x>next_x){for(int i=0;i<now_x-next_x;i++){ans+="1 U\n";ans_count++;}}else if(now_x<next_x){for(int i=0;i<next_x-now_x;i++){ans+="1 D\n";ans_count++;}}if(now_y>next_y){for(int i=0;i<now_y-next_y;i++){ans+="1 L\n";ans_count++;}}else if(next_y>now_y){for(int i=0;i<next_y-now_y;i++){ans+="1 R\n";ans_count++;}}}int main(){read_input();greedy();int nearest_shop_x=100,nearest_shop_y=100;for(int i=0;i<n;i++)for(int j=0;j<n;j++){if(grid[i][j]=='@'&&nearest_shop_x+nearest_shop_y>i+j){nearest_shop_x=i;nearest_shop_y=j;}}go_straight(0,nearest_shop_x*n+nearest_shop_y);for(bomb_instance b:locates){ans+="2 "+to_string(b.id+1)+"\n";ans_count++;}int now_x=nearest_shop_x,now_y=nearest_shop_y;int q=locates.size();for(int i=0;i<q;i++){int index=0,min_dist=1000000;bomb_instance b=locates[0];for(int j=0;j<locates.size();j++){bomb_instance c=locates[j];if(abs(now_x-c.x)+abs(now_y-c.y)<min_dist){min_dist=abs(now_x-c.x)+abs(now_y-c.y);b=c;index=j;}}go_straight(now_x*n+now_y,b.x*n+b.y);ans+="3 "+to_string(b.id+1)+"\n";ans_count++;now_x=b.x;now_y=b.y;if(index+1!=locates.size())swap(locates[index],locates[locates.size()-1]);locates.pop_back();}cout<<ans_count<<endl;cout<<ans;return 0;}