#929326 (C++17(clang)) No.5019 Hakai Project

• 問題: No.5019 Hakai Project
• ユーザー: ぴぃいいいい
• 提出日時: 2023-11-18 00:42:11
• 言語: C++17(clang) (17.0.6 + boost 1.89.0)
• 結果: TLE
• 実行時間: -
• コード長: 5,932 bytes
• コンパイル時間: 2,895 ms
• コンパイル使用メモリ: 163,660 KB
• 実行使用メモリ: 16,680 KB
• スコア: 0
• 最終ジャッジ日時: 2023-11-18 00:42:24
• 合計ジャッジ時間: 11,122 ms
• ジャッジサーバーID （参考情報）: judge11 / judge13

ファイルパターン	結果
other	TLE * 1 -- * 49

ソースコード

#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)); }

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 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<<"\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(){
    Solve solve;
    solve.IN();
    solve.solve();
}