結果

問題 No.5019 Hakai Project
ユーザー FplusFplusFFplusFplusF
提出日時 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 -
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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();
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0