#929502 (C++17) No.5019 Hakai Project

提出ソース

結果

問題	No.5019 Hakai Project
ユーザー	ぴぃいいいい
提出日時	2023-11-19 02:19:40
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	1,810 ms / 3,000 ms
コード長	20,639 bytes
コンパイル時間	3,903 ms
コンパイル使用メモリ	255,436 KB
実行使用メモリ	6,676 KB
スコア	2,554,938,312
最終ジャッジ日時	2023-11-19 02:20:55
合計ジャッジ時間	74,648 ms
ジャッジサーバーID （参考情報）	judge15 / judge11
	純コード判定しない問題か言語

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1,140 ms 6,676 KB
testcase_01	AC	1,746 ms 6,676 KB
testcase_02	AC	1,215 ms 6,676 KB
testcase_03	AC	1,364 ms 6,676 KB
testcase_04	AC	1,288 ms 6,676 KB
testcase_05	AC	1,090 ms 6,676 KB
testcase_06	AC	1,220 ms 6,676 KB
testcase_07	AC	1,490 ms 6,676 KB
testcase_08	AC	1,259 ms 6,676 KB
testcase_09	AC	1,568 ms 6,676 KB
testcase_10	AC	991 ms 6,676 KB
testcase_11	AC	1,186 ms 6,676 KB
testcase_12	AC	1,403 ms 6,676 KB
testcase_13	AC	1,239 ms 6,676 KB
testcase_14	AC	1,116 ms 6,676 KB
testcase_15	AC	1,268 ms 6,676 KB
testcase_16	AC	1,127 ms 6,676 KB
testcase_17	AC	808 ms 6,676 KB
testcase_18	AC	1,271 ms 6,676 KB
testcase_19	AC	1,054 ms 6,676 KB
testcase_20	AC	1,440 ms 6,676 KB
testcase_21	AC	1,394 ms 6,676 KB
testcase_22	AC	1,128 ms 6,676 KB
testcase_23	AC	1,253 ms 6,676 KB
testcase_24	AC	1,276 ms 6,676 KB
testcase_25	AC	1,246 ms 6,676 KB
testcase_26	AC	1,065 ms 6,676 KB
testcase_27	AC	1,109 ms 6,676 KB
testcase_28	AC	1,006 ms 6,676 KB
testcase_29	AC	1,103 ms 6,676 KB
testcase_30	AC	1,220 ms 6,676 KB
testcase_31	AC	1,184 ms 6,676 KB
testcase_32	AC	1,405 ms 6,676 KB
testcase_33	AC	1,171 ms 6,676 KB
testcase_34	AC	1,553 ms 6,676 KB
testcase_35	AC	1,058 ms 6,676 KB
testcase_36	AC	1,054 ms 6,676 KB
testcase_37	AC	1,245 ms 6,676 KB
testcase_38	AC	1,203 ms 6,676 KB
testcase_39	AC	1,201 ms 6,676 KB
testcase_40	AC	1,114 ms 6,676 KB
testcase_41	AC	1,123 ms 6,676 KB
testcase_42	AC	1,009 ms 6,676 KB
testcase_43	AC	1,126 ms 6,676 KB
testcase_44	AC	998 ms 6,676 KB
testcase_45	AC	1,041 ms 6,676 KB
testcase_46	AC	1,280 ms 6,676 KB
testcase_47	AC	1,020 ms 6,676 KB
testcase_48	AC	1,576 ms 6,676 KB
testcase_49	AC	1,810 ms 6,676 KB

権限があれば一括ダウンロードができます

コンパイルメッセージ

main.cpp: In member function 'void State::one_step2()':
main.cpp:512:48: warning: 'best_t' may be used uninitialized [-Wmaybe-uninitialized]
  512 |         int best_explode_x = i-a[best_k][best_t];
      |                                                ^
main.cpp:471:20: note: 'best_t' was declared here
  471 |         int best_k,best_t;
      |                    ^~~~~~
In member function 'void State::use(int)',
    inlined from 'void State::one_step2()' at main.cpp:518:12:
main.cpp:326:26: warning: 'best_k' may be used uninitialized [-Wmaybe-uninitialized]
  326 |         for(int j=0;j<l[i];j++){
      |                       ~~~^
main.cpp: In member function 'void State::one_step2()':
main.cpp:471:13: note: 'best_k' was declared here
  471 |         int best_k,best_t;
      |             ^~~~~~
main.cpp:468:18: warning: 'j' may be used uninitialized [-Wmaybe-uninitialized]
  468 |         if(A[i][j]=='.') return;
      |            ~~~~~~^
main.cpp:462:15: note: 'j' was declared here
  462 |         int i,j;
      |               ^
main.cpp:468:18: warning: 'i' may be used uninitialized [-Wmaybe-uninitialized]
  468 |         if(A[i][j]=='.') return;
      |            ~~~~~~^
main.cpp:462:13: note: 'i' was declared here
  462 |         int i,j;
      |             ^

ソースコード

raw source code

#pragma GCC optimize("O3")
#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;
int c[20],l[20];
vector<int> a[20],b[20];

bool is_valid(int x,int y){
    return 0<=x && x<n && 0<=y && y<n;
}

struct Bombplan{
    char A[50][50];
    tuple<int,int,int> plan[50][50];
    
    Bombplan(){}
    Bombplan(char AA[50][50]){
        for(int i=0;i<n;i++)for(int j=0;j<n;j++) A[i][j] = AA[i][j];
        greedy_all();
    }

    //a[i][j]の爆破方法をランダムに決める
    void random_generate(int i,int j){
        if(A[i][j]=='.') return;
        int k,x;
        do{
            k = randInt(0,m-1);
            x = randInt(0,l[k]);
        }while(!is_valid(i-a[k][x],j-b[k][x]));
        plan[i][j] = make_tuple(k,i-a[k][x],j-b[k][x]);
    }
    //すべての位置の爆破方法をランダムに決める
    void random_all(){
        for(int i=0;i<n;i++)for(int j=0;j<n;j++) random_generate(i,j);
    }
    //すべての位置の爆破方法をgreedyに決める
    void greedy_all(){
        char AA[50][50];
        for(int i=0;i<n;i++)for(int j=0;j<n;j++) AA[i][j] = A[i][j];
        int building = 0;
        for(int i=0;i<n;i++)for(int j=0;j<n;j++){
            if(AA[i][j]=='.') continue;
            building++;
        }
        while(building>0){
            int best_i,best_j,best_k;
            double best = (double)INF;
            for(int iter=0;iter<10000;iter++){
                int i = randInt(0,n-1);
                int j = randInt(0,n-1);
                int k = randInt(0,m-1);
                int broken_cnt = 0;
                for(int x=0;x<l[k];x++){
                    int broken_x = i+a[k][x];
                    int broken_y = j+b[k][x];
                    if(is_valid(broken_x,broken_y) && AA[broken_x][broken_y]!='.'){
                        broken_cnt++;
                    }
                }
                if(broken_cnt==0) continue;
                double tmp = (double)c[k]/(double)broken_cnt;
                if(chmin(best,tmp)){
                    best_i = i;
                    best_j = j;
                    best_k = k;
                }
            }
            for(int x=0;x<l[best_k];x++){
                int broken_x = best_i+a[best_k][x];
                int broken_y = best_j+b[best_k][x];
                if(!is_valid(broken_x,broken_y)) continue;
                if(AA[broken_x][broken_y]=='.') continue;
                AA[broken_x][broken_y] = '.';
                building--;
                plan[broken_x][broken_y] = make_tuple(best_k,best_i,best_j);
            }
        }
    }

    //ランダムな一か所の爆破方法を変更する
    void random_trans_plan(){
        int i,j;
        do{
            i = randInt(0,n-1);
            j = randInt(0,n-1);
        }while(A[i][j]=='.');

        random_generate(i,j);
        compress(i,j);
    }

    void compress(int i,int j){
        if(A[i][j]=='.') return;
        auto [k,x,y] = plan[i][j];
        for(int t=0;t<l[k];t++){
            int broken_x = x+a[k][t];
            int broken_y = y+b[k][t];
            if(!is_valid(broken_x,broken_y)) continue;
            if(A[broken_x][broken_y]=='.') continue;
            plan[broken_x][broken_y] = plan[i][j];
        }
    }
    void compress_all(){
        vector<vector<bool>> dicided(n,vector<bool>(n));
        vector<pii> que;
        for(int i=0;i<n;i++)for(int j=0;j<n;j++){
            if(A[i][j]=='.') continue;
            que.push_back(make_pair(i,j));
        }
        //queを真ん中からの距離で並び替え
        sort(all(que),[](pii a,pii b){
            return abs(a.first-n/2)+abs(a.second-n/2) < abs(b.first-n/2)+abs(b.second-n/2);
        });
        //queを順番に見ていく
        //queの中でまだ決まっていない建物を見つけて確定させる
        for(auto [i,j]:que){
            if(dicided[i][j]) continue;
            auto [k,x,y] = plan[i][j];
            for(int t=0;t<l[k];t++){
                int broken_x = x+a[k][t];
                int broken_y = y+b[k][t];
                if(!is_valid(broken_x,broken_y)) continue;
                if(A[broken_x][broken_y]=='.') continue;
                if(dicided[broken_x][broken_y]) continue;
                dicided[broken_x][broken_y] = true;
                plan[broken_x][broken_y] = make_tuple(k,x,y);
            }
        }
    }
    set<tuple<int,int,int>> explode_list(){
        set<tuple<int,int,int>> res;
        for(int i=0;i<n;i++)for(int j=0;j<n;j++){
            if(A[i][j]=='.') continue;
            res.insert(plan[i][j]);
        }
        return res;
    }
    double eval(){
        Bombplan bombplan = *this;
        double res = 0;
        bombplan.compress_all();
        auto bombplan_explode_list = bombplan.explode_list();
        for(auto [k,x,y]:bombplan_explode_list){
            res += c[k];
        }
        return res;
    }
    //出力
    void output(){
        auto res = explode_list();
        for(auto [k,x,y]:res){
            cerr<<x<<" "<<y<<" "<<k<<endl;
        }
    }
};



struct State{
    char A[50][50];
    int center_shop_x;
    int center_shop_y;
    int bomb[20];
    int bomb_sum=0;
    vector<pair<int,int>> hist;
    int building = 0;
    int shop = 0;
    ll cost=0;
    int buy_cost=0;
    int move_cost=0;
    int nowx=0,nowy=0;
    queue<pii> que;

    State(){}
    State(char AA[50][50]){
        for(int i=0;i<n;i++)for(int j=0;j<n;j++) A[i][j] = AA[i][j];
        vpii tmp;
        int min_center_dist = inf;
        for(int i=0;i<n;i++)for(int j=0;j<n;j++){
            if(A[i][j]=='.') continue;
            tmp.emplace_back(make_pair(i,j));
            building++;
            if(A[i][j]=='@'){
                shop++;
                if(chmin(min_center_dist,abs(i-n/2)+abs(j-n/2))){
                    center_shop_x = i;
                    center_shop_y = j;
                }
            }
        }
        sort(all(tmp),[](pii x, pii y){
            int x_dist = abs(x.first-n/2)+abs(x.second-n/2);
            int y_dist = abs(y.first-n/2)+abs(y.second-n/2);
            if(x_dist==y_dist) return atan2(x.second-n/2,x.first-n/2) < atan2(y.second-n/2,y.first-n/2);
            return x_dist>y_dist;
        });
        for(auto e:tmp){
            que.push(e);
        }

    }

    pair<int,vector<char>> smart_route(int sx,int sy,int gx,int gy){
        char x_ope = gx>sx ? 'D' : 'U';
        int dx = gx>sx ? 1 : -1;
        char y_ope = gy>sy ? 'R' : 'L';
        int dy = gy>sy ? 1 : -1;
        vvi dp(abs(gx-sx)+1,vi(abs(gy-sy)+1,inf));
        dp[0][0] = 0;
        for(int i=0;i<=abs(gx-sx);i++)for(int j=0;j<=abs(gy-sy);j++){
            if(i+1<=abs(gx-sx)){
                chmin(dp[i+1][j],dp[i][j]+(A[sx+dx*(i+1)][sy+dy*j]!='.')+1);
            }
            if(j+1<=abs(gy-sy)){
                chmin(dp[i][j+1],dp[i][j]+(A[sx+dx*i][sy+dy*(j+1)]!='.')+1);
            }
        }
        //dpから最短経路を復元
        vector<char> res(abs(gx-sx) + abs(gy-sy));
        int i=abs(gx-sx),j=abs(gy-sy);
        int index = res.size() - 1;
        while(i>0 || j>0){
            if(i>0 && dp[i-1][j]+(A[sx+dx*i][sy+dy*j]!='.')+1==dp[i][j]){
                res[index] = x_ope;
                i--;
            }
            else{
                res[index] = y_ope;
                j--;
            }
            index--;
        }
        int cost = dp[abs(gx-sx)][abs(gy-sy)];
        return make_pair(cost,res);
    }
    
    //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);
            move_cost += (bomb_sum+1)*(bomb_sum+1);
        }
        else{
            cost += 2*(bomb_sum+1)*(bomb_sum+1);
            move_cost += 2*(bomb_sum+1)*(bomb_sum+1);
        }
    }
    //x,y:目的地の座標
    void move(int x,int y){
        pair<int, vector<char>> route_result = smart_route(nowx, nowy, x, y);
        for (char direction : route_result.second) {
            move(direction);
        }
    }
    //piiに対応する座標に移動する
    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];
        buy_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--;
    }
    //爆弾を使ったときに壊れる建物の数,壊れる店の数,center_shopが壊れるかどうかを返す
    tuple<int,int,bool> use_simulate(int i,int x,int y){
        assert(i>=0 && i<m);
        int broken_building = 0;
        int broken_shop = 0;
        bool broken_center_shop = false;
        for(int j=0;j<l[i];j++){
            int broken_x = x+a[i][j];
            int broken_y = y+b[i][j];
            if(!is_valid(broken_x,broken_y)) continue;
            if(A[broken_x][broken_y]=='.') continue;
            
            if(A[broken_x][broken_y]=='@'){
                broken_shop++;
                if(broken_x==center_shop_x && broken_y==center_shop_y){
                    broken_center_shop = true;
                }
            }
            broken_building++;
        }
        return make_tuple(broken_building,broken_shop,broken_center_shop);
    }
    //最も近い店の座標を返す
    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;
    }
    pii nearest_shop(int x, int y){
        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(x-i)+abs(y-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]=='@');
        double best_eval = (double)INF+1;
        State best_state;
        while(best_eval>=(double)INF){
            for(int i=0;i<m;i++){
                State state = *this;
                state.buy(i);
                state.use(i);

                double eval = diff_eval(*this,state);
                if(chmin(best_eval,eval)){
                    best_state = state;
                }
            }
            for(int iter=0;iter<5000;iter++){
                int num = 1;
                vi i(num),j(num),k(num);
                for(int t=0;t<num;t++){
                    i[t] = randInt(0,n-1);
                    j[t] = randInt(0,n-1);
                    k[t] = randInt(0,m-1);
                }
                
                State state = *this;
                for(int t=0;t<num;t++){
                    state.buy(k[t]);
                }
                for(int t=0;t<num;t++){
                    state.move(i[t],j[t]);
                    state.use(k[t]);
                }

                double eval = diff_eval(*this,state);
                if(chmin(best_eval,eval)){
                    best_state = state;
                }
            }
        }
        
        /* 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;
                }
            }
        } */
        *this = best_state;
    }
    //爆破場所を決め打ちして1手進める
    void one_step2(){
        int i,j;
        while(!que.empty()){
            tie(i,j) = que.front();
            que.pop();
            if(A[i][j]!='.') break;
        }
        if(A[i][j]=='.') return;

        double best_eval = (double)INF+1;
        int best_k,best_t;

        while(best_eval>=(double)INF){
            int max_iter = 5000;
            for(int iter=0;iter<max_iter;iter++){
                //爆弾の種類とどの爆風で破壊するか決める
                int k,t,explode_x,explode_y;
                do{
                    k = randInt(0,m-1);
                    t = randInt(0,l[k]);
                    //爆破場所
                    explode_x = i-a[k][t];
                    explode_y = j-b[k][t];
                }while(!is_valid(explode_x,explode_y));

                //爆破したらどうなるか
                int broken_building;
                int broken_shop;
                bool center_shop_broken;
                tie(broken_building,broken_shop,center_shop_broken) = use_simulate(k,explode_x,explode_y);
                if(broken_building==0) continue;

                //コストシミュレーション
                auto shop_pos = nearest_shop(explode_x,explode_y);
                int use_cost = 0;
                //shopまでの移動
                use_cost += smart_route(nowx,nowy,shop_pos.first,shop_pos.second).first;
                //shopでの購入
                use_cost += c[k];
                //shopから爆破場所までの移動
                use_cost += 4*smart_route(shop_pos.first,shop_pos.second,explode_x,explode_y).first;

                double eval = eval_func(use_cost,broken_building,broken_shop,center_shop_broken);

                if(chmin(best_eval,eval)){
                    best_k = k;
                    best_t = t;
                }
            }
        }

        int best_explode_x = i-a[best_k][best_t];
        int best_explode_y = j-b[best_k][best_t];
        auto shop_pos = nearest_shop(best_explode_x,best_explode_y);
        move(shop_pos.first,shop_pos.second);
        buy(best_k);
        move(best_explode_x,best_explode_y);
        use(best_k);
    }
    
    //シミュレーション結果で評価
    double eval_func(double usecost,double broken_building,double broken_shop,bool center_shop_broken){
        if(broken_building==0) return (double)INF;
        else if(shop==broken_shop && building>broken_building) return (double)INF;
        else{
            double eval = (double)usecost/(double)broken_building;
            if(center_shop_broken) eval *= 10;
            return eval;
        }

    }
    //差分評価
    double diff_eval(State now, State nex){
        int broken_building = now.building - nex.building;
        int usecost = nex.cost - now.cost;
        if(broken_building==0) return (double)INF;
        else if(nex.shop==0 && nex.building!=0) return (double)INF;
        else{
            double eval = (double)usecost/(double)broken_building;
            if(nex.A[nex.center_shop_x][nex.center_shop_y]!='@') eval *= 10;
            return eval;
        }
    }
    
    //出力
    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{
    char A[50][50];
    void IN(){
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cin>>n>>m;
        for(int i=0;i<n;i++){
            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(){
        /* Bombplan bombplan(A);
        cerr<<bombplan.eval()<<endl; */
        State state(A);
        while(state.building>0){
            state.one_step2();
            cerr<<state.building<<" "<<state.shop<<" "<<state.cost<<'\n';
        }
        cerr<<"buy_cost:"<<state.buy_cost<<endl;
        cerr<<"move_cost:"<<state.move_cost<<endl;
        cerr<<"total_cost:"<<state.cost<<endl;
        state.output();
    }

    /* void sa(){
        Bombplan bombplan(A);
        double start_temp = 1;
        double end_tmp = 1;
        double start = get_time();
        cerr<<"start_sa\n";
        int iter=0;
        int trans_cnt = 0;
        while(true){
            iter++;
            double now_time = get_time();
            if(now_time-start>1900) break;

            Bombplan new_bombplan = bombplan;
            new_bombplan.random_trans_plan();
            int pre_score = bombplan.eval();
            int new_score = new_bombplan.eval();

            //温度関数
            double temp = start_temp + (end_tmp-start_temp)*(now_time-start)/1900;
            //遷移確率関数
            double prob = exp((pre_score-new_score)/temp);
            //遷移回数
            if(prob>randDouble(0,1)){
                //遷移
                bombplan = new_bombplan;
                trans_cnt++;
                if(iter%500==1){
                    cerr<<"iter:"<<iter<<endl;
                    cerr<<"trans_cnt:"<<trans_cnt<<endl;
                    cerr<<"time:"<<now_time-start<<"ms\n";
                    cerr<<"score:"<<new_score<<endl;
                }
            }
            else{
                if(iter%500==1){
                    cerr<<"iter:"<<iter<<endl;
                    cerr<<"trans_cnt:"<<trans_cnt<<endl;
                    cerr<<"time:"<<now_time-start<<"ms\n";
                    cerr<<"score:"<<pre_score<<endl;
                }
            }
        }
        best_plan = bombplan;
    } */
};

int main(){
    start_time = get_time();
    Solve solve;
    solve.IN();
    solve.solve();
    cerr<<"time:"<<get_time()-start_time<<"ms\n";
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード