結果
| 問題 | No.5019 Hakai Project |
| ユーザー |
 ぴぃいいいい
|
| 提出日時 | 2023-11-18 00:56:01 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 355 ms / 3,000 ms |
| コード長 | 7,217 bytes |
| コンパイル時間 | 3,612 ms |
| コンパイル使用メモリ | 270,752 KB |
| 実行使用メモリ | 6,676 KB |
| スコア | 2,130,992,002 |
| 最終ジャッジ日時 | 2023-11-18 00:56:26 |
| 合計ジャッジ時間 | 24,651 ms |
|
ジャッジサーバーID （参考情報） |
judge11 / judge15 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 50 |
ソースコード
#include<bits/stdc++.h>using namespace std;#define Yes(n) cout << ((n) ? "Yes" : "No" ) << endl#define print(var) std::cout<<#var<<"="<<(var)<<std::endl#define all(a) (a).begin(), (a).end()#define vi vector<int>#define vvi vector<vi>#define vvvi vector<vvi>#define ll long long#define vll vector<ll>#define vvll vector<vll>#define vvvll vector<vvll>#define vmi vector<mint>#define vvmi vector<vmi>#define vvvmi vector<vvmi>#define vs vector<string>#define pii pair<int,int>#define vpii vector<pair<int,int>>#define bit(x,i)(((x)>>(i))&1)#define inf (1<<30)#define INF (1ll<<60)template<typename T> inline bool chmax(T &a, T b) { return ((a < b) ? (a = b, true) : (false)); }template<typename T> inline bool chmin(T &a, T b) { return ((a > b) ? (a = b, true) : (false)); }inline double get_time() {using namespace std::chrono;return duration_cast<milliseconds>(system_clock::now().time_since_epoch()).count();}unsigned long xor128(void){static unsigned long x=123456789,y=362436069,z=521288629,w=88675123;unsigned long t;t=(x^(x<<11));x=y;y=z;z=w; return( w=(w^(w>>19))^(t^(t>>8)) );}long long randInt(long long a,long long b){return a+xor128()%(b-a+1);}double randDouble(double a,double b){return a+(b-a)*xor128()/(double)ULONG_MAX;}double start_time;int n,m;vector<int> c(20),l(20);vector<vector<int>> a(20),b(20);bool is_valid(int x,int y){return 0<=x && x<n && 0<=y && y<n;}struct State{vector<vector<char>> A;vector<int> bomb;int bomb_sum=0;vector<pair<int,int>> hist;ll building = 0;ll shop = 0;ll cost=0;int nowx=0,nowy=0;State(){}State(vector<vector<char>> AA):A(AA){bomb.resize(m);for(int i=0;i<n;i++)for(int j=0;j<n;j++){if(A[i][j]=='#' || A[i][j]=='@') building++;if(A[i][j]=='@') shop++;}}//d:方向void move(char d){if(d=='U'){hist.emplace_back(make_pair(1,0));nowx--;}if(d=='D'){hist.emplace_back(make_pair(1,1));nowx++;}if(d=='L'){hist.emplace_back(make_pair(1,2));nowy--;}if(d=='R'){hist.emplace_back(make_pair(1,3));nowy++;}if(A[nowx][nowy]=='.') cost += (bomb_sum+1)*(bomb_sum+1);else cost += 2*(bomb_sum+1)*(bomb_sum+1);}//x,y:目的地の座標void move(int x,int y){while(nowx!=x){if(nowx<x){move('D');}else{move('U');}}while(nowy!=y){if(nowy<y){move('R');}else{move('L');}}}void move(pii p){move(p.first,p.second);}//i:爆弾の種類void buy(int i){assert(i>=0 && i<m);hist.emplace_back(make_pair(2,i));bomb[i]++;bomb_sum++;cost+=c[i];}//i:爆弾の種類void use(int i){assert(i>=0 && i<m);hist.emplace_back(make_pair(3,i));for(int j=0;j<l[i];j++){int broken_x = nowx+a[i][j];int broken_y = nowy+b[i][j];if(!is_valid(broken_x,broken_y)) continue;if(A[broken_x][broken_y]=='.') continue;if(A[broken_x][broken_y]=='@'){shop--;}building--;A[broken_x][broken_y]='.';}bomb[i]--;bomb_sum--;}//最も近い店の座標を返すpii nearest_shop(){int min_dist=inf;pii res;for(int i=0;i<n;i++)for(int j=0;j<n;j++){if(A[i][j]=='@'){if(chmin(min_dist,abs(nowx-i)+abs(nowy-j))){res = make_pair(i,j);}}}assert(min_dist!=inf);return res;}//最も近い店に移動するvoid move_nearest_shop(){pii p = nearest_shop();move(p);}//一手進めるvoid one_step(){move_nearest_shop();assert(A[nowx][nowy]=='@');int best_eval = inf+1;int best_i = -1;int best_j = -1;int best_k = -1;for(int iter=0;iter<1000;iter++){int i = randInt(0,n-1);int j = randInt(0,n-1);int k = randInt(0,m-1);State state = *this;state.buy(k);state.move(i,j);state.use(k);int broken_building = building - state.building;int usecost = state.cost - cost;int eval;if(broken_building==0) eval = inf;else if(state.shop==0 && state.building!=0) eval = inf;else{eval = usecost/broken_building;}if(chmin(best_eval,eval)){best_i = i;best_j = j;best_k = k;}}/* for(int i=0;i<n;i++)for(int j=0;j<n;j++){for(int k=0;k<m;k++){State state = *this;state.buy(k);state.move(i,j);state.use(k);int broken_building = building - state.building;int usecost = state.cost - cost;int eval;if(broken_building==0) eval = inf;else if(state.shop==0 && state.building!=0) eval = inf;else{eval = usecost/broken_building;}if(chmin(best_eval,eval)){best_i = i;best_j = j;best_k = k;}}} */buy(best_k);move(best_i,best_j);use(best_k);}//出力void output(){cout<<hist.size()<<endl;for(auto p:hist){if(p.first==1){cout<<1<<" ";if(p.second==0) cout<<"U";if(p.second==1) cout<<"D";if(p.second==2) cout<<"L";if(p.second==3) cout<<"R";cout<<'\n';}else cout<<p.first<<" "<<p.second+1<<"\n";}}};struct Solve{vector<vector<char>> A;void IN(){cin.tie(nullptr);ios::sync_with_stdio(false);cin>>n>>m;A.resize(n);for(int i=0;i<n;i++){A[i].resize(n);for(int j=0;j<n;j++){cin>>A[i][j];}}for(int i=0;i<m;i++){cin>>c[i]>>l[i];for(int j=0;j<l[i];j++){int tmpa,tmpb;cin>>tmpa>>tmpb;a[i].emplace_back(tmpa);b[i].emplace_back(tmpb);}}}void solve(){State state(A);while(state.building>0){state.one_step();cerr<<state.building<<" "<<state.shop<<" "<<state.cost<<endl;}state.output();}};int main(){start_time = get_time();Solve solve;solve.IN();solve.solve();}