#929333 (C++23) No.5019 Hakai Project

提出ソース

結果

問題	No.5019 Hakai Project
ユーザー	ぴぃいいいい
提出日時	2023-11-18 00:56:01
言語	C++23 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	355 ms / 3,000 ms
コード長	7,217 bytes
コンパイル時間	3,612 ms
コンパイル使用メモリ	270,752 KB
実行使用メモリ	6,676 KB
スコア	2,130,992,002
最終ジャッジ日時	2023-11-18 00:56:26
合計ジャッジ時間	24,651 ms
ジャッジサーバーID （参考情報）	judge11 / judge15
	純コード判定しない問題か言語

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	249 ms 6,676 KB
testcase_01	AC	337 ms 6,676 KB
testcase_02	AC	245 ms 6,676 KB
testcase_03	AC	298 ms 6,676 KB
testcase_04	AC	289 ms 6,676 KB
testcase_05	AC	266 ms 6,676 KB
testcase_06	AC	259 ms 6,676 KB
testcase_07	AC	334 ms 6,676 KB
testcase_08	AC	298 ms 6,676 KB
testcase_09	AC	323 ms 6,676 KB
testcase_10	AC	254 ms 6,676 KB
testcase_11	AC	273 ms 6,676 KB
testcase_12	AC	323 ms 6,676 KB
testcase_13	AC	285 ms 6,676 KB
testcase_14	AC	235 ms 6,676 KB
testcase_15	AC	267 ms 6,676 KB
testcase_16	AC	240 ms 6,676 KB
testcase_17	AC	205 ms 6,676 KB
testcase_18	AC	293 ms 6,676 KB
testcase_19	AC	254 ms 6,676 KB
testcase_20	AC	355 ms 6,676 KB
testcase_21	AC	318 ms 6,676 KB
testcase_22	AC	265 ms 6,676 KB
testcase_23	AC	258 ms 6,676 KB
testcase_24	AC	286 ms 6,676 KB
testcase_25	AC	268 ms 6,676 KB
testcase_26	AC	240 ms 6,676 KB
testcase_27	AC	242 ms 6,676 KB
testcase_28	AC	237 ms 6,676 KB
testcase_29	AC	238 ms 6,676 KB
testcase_30	AC	283 ms 6,676 KB
testcase_31	AC	268 ms 6,676 KB
testcase_32	AC	313 ms 6,676 KB
testcase_33	AC	262 ms 6,676 KB
testcase_34	AC	311 ms 6,676 KB
testcase_35	AC	224 ms 6,676 KB
testcase_36	AC	252 ms 6,676 KB
testcase_37	AC	260 ms 6,676 KB
testcase_38	AC	274 ms 6,676 KB
testcase_39	AC	224 ms 6,676 KB
testcase_40	AC	255 ms 6,676 KB
testcase_41	AC	246 ms 6,676 KB
testcase_42	AC	242 ms 6,676 KB
testcase_43	AC	226 ms 6,676 KB
testcase_44	AC	217 ms 6,676 KB
testcase_45	AC	222 ms 6,676 KB
testcase_46	AC	251 ms 6,676 KB
testcase_47	AC	237 ms 6,676 KB
testcase_48	AC	329 ms 6,676 KB
testcase_49	AC	323 ms 6,676 KB

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

ソースコード

raw source code

#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;
    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 iter=0;iter<1000;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 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;
            }
        }
        /* 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+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();
}

yukicoder

結果

テストケース

ソースコード