結果

問題 No.5019 Hakai Project
ユーザー askr58askr58
提出日時 2023-11-18 01:52:13
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 5,033 bytes
コンパイル時間 3,143 ms
コンパイル使用メモリ 227,960 KB
実行使用メモリ 6,676 KB
スコア 0
最終ジャッジ日時 2023-11-18 01:52:23
合計ジャッジ時間 9,794 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
testcase_32 WA -
testcase_33 WA -
testcase_34 WA -
testcase_35 WA -
testcase_36 WA -
testcase_37 WA -
testcase_38 WA -
testcase_39 WA -
testcase_40 WA -
testcase_41 WA -
testcase_42 WA -
testcase_43 WA -
testcase_44 WA -
testcase_45 WA -
testcase_46 WA -
testcase_47 WA -
testcase_48 WA -
testcase_49 WA -
権限があれば一括ダウンロードができます
コンパイルメッセージ
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;
      |                       ^~~

ソースコード

diff # 

#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<<endl;

    



    
    return 0;
}
0