#929343 (C++14) No.5019 Hakai Project

• 問題: No.5019 Hakai Project
• ユーザー: ぴぃいいいい
• 提出日時: 2023-11-18 01:07:39
• 言語: C++14 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 2,268 ms / 3,000 ms
• コード長: 7,309 bytes
• コンパイル時間: 2,450 ms
• コンパイル使用メモリ: 193,404 KB
• 実行使用メモリ: 6,676 KB
• スコア: 2,256,060,351
• 最終ジャッジ日時: 2023-11-18 01:09:04
• 合計ジャッジ時間: 85,496 ms
• ジャッジサーバーID （参考情報）: judge14 / judge15

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1,306 ms; 6,676 KB
testcase_01	AC	2,061 ms; 6,676 KB
testcase_02	AC	1,463 ms; 6,676 KB
testcase_03	AC	1,659 ms; 6,676 KB
testcase_04	AC	1,523 ms; 6,676 KB
testcase_05	AC	1,367 ms; 6,676 KB
testcase_06	AC	1,547 ms; 6,676 KB
testcase_07	AC	1,896 ms; 6,676 KB
testcase_08	AC	1,565 ms; 6,676 KB
testcase_09	AC	1,999 ms; 6,676 KB
testcase_10	AC	1,251 ms; 6,676 KB
testcase_11	AC	1,542 ms; 6,676 KB
testcase_12	AC	1,802 ms; 6,676 KB
testcase_13	AC	1,442 ms; 6,676 KB
testcase_14	AC	1,303 ms; 6,676 KB
testcase_15	AC	1,596 ms; 6,676 KB
testcase_16	AC	1,340 ms; 6,676 KB
testcase_17	AC	1,100 ms; 6,676 KB
testcase_18	AC	1,411 ms; 6,676 KB
testcase_19	AC	1,375 ms; 6,676 KB
testcase_20	AC	1,786 ms; 6,676 KB
testcase_21	AC	1,646 ms; 6,676 KB
testcase_22	AC	1,394 ms; 6,676 KB
testcase_23	AC	1,423 ms; 6,676 KB
testcase_24	AC	1,560 ms; 6,676 KB
testcase_25	AC	1,513 ms; 6,676 KB
testcase_26	AC	1,376 ms; 6,676 KB
testcase_27	AC	1,405 ms; 6,676 KB
testcase_28	AC	1,195 ms; 6,676 KB
testcase_29	AC	1,234 ms; 6,676 KB
testcase_30	AC	1,464 ms; 6,676 KB
testcase_31	AC	1,435 ms; 6,676 KB
testcase_32	AC	1,728 ms; 6,676 KB
testcase_33	AC	1,491 ms; 6,676 KB
testcase_34	AC	1,969 ms; 6,676 KB
testcase_35	AC	1,239 ms; 6,676 KB
testcase_36	AC	1,493 ms; 6,676 KB
testcase_37	AC	1,562 ms; 6,676 KB
testcase_38	AC	1,594 ms; 6,676 KB
testcase_39	AC	1,383 ms; 6,676 KB
testcase_40	AC	1,502 ms; 6,676 KB
testcase_41	AC	1,217 ms; 6,676 KB
testcase_42	AC	1,237 ms; 6,676 KB
testcase_43	AC	1,123 ms; 6,676 KB
testcase_44	AC	1,265 ms; 6,676 KB
testcase_45	AC	1,071 ms; 6,676 KB
testcase_46	AC	1,340 ms; 6,676 KB
testcase_47	AC	1,376 ms; 6,676 KB
testcase_48	AC	2,268 ms; 6,676 KB
testcase_49	AC	2,041 ms; 6,676 KB

ソースコード

#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;
    int building = 0;
    int 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]=='@');
        ll best_eval = INF+1;
        State best_state;
        while(best_eval>=INF){
            for(int iter=0;iter<5000;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 broken_shop = shop - state.shop;
                int usecost = state.cost - cost;
                ll eval;
                if(broken_building==0) eval = INF;
                else if(state.shop==0 && state.building!=0) eval = INF;
                else{
                    eval = usecost/broken_building;
                    eval *= max(1,2-state.shop);
                }
                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;
    }
    //出力
    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();
}