#770637 (C++17) No.5006 Hidden Maze

提出ソース

結果

問題	No.5006 Hidden Maze
ユーザー	hiikunZ
提出日時	2022-06-12 16:52:35
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	1,606 ms / 2,000 ms
コード長	5,564 bytes
コンパイル時間	2,048 ms
実行使用メモリ	22,900 KB
スコア	1,264
平均クエリ数	988.36
最終ジャッジ日時	2022-06-12 16:55:19
合計ジャッジ時間	131,476 ms
ジャッジサーバーID （参考情報）	judge14 / judge15
	純コード判定しない問題か言語

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1,579 ms 22,004 KB
testcase_01	AC	1,582 ms 22,620 KB
testcase_02	AC	1,582 ms 21,904 KB
testcase_03	AC	1,568 ms 21,904 KB
testcase_04	AC	1,567 ms 21,940 KB
testcase_05	AC	1,582 ms 21,964 KB
testcase_06	AC	1,582 ms 22,716 KB
testcase_07	AC	1,585 ms 22,228 KB
testcase_08	AC	1,576 ms 21,940 KB
testcase_09	AC	1,561 ms 22,716 KB
testcase_10	AC	1,571 ms 22,632 KB
testcase_11	AC	1,580 ms 21,904 KB
testcase_12	AC	1,559 ms 22,288 KB
testcase_13	AC	1,576 ms 22,004 KB
testcase_14	AC	1,583 ms 21,940 KB
testcase_15	AC	1,581 ms 22,468 KB
testcase_16	AC	1,566 ms 21,952 KB
testcase_17	AC	1,565 ms 21,940 KB
testcase_18	AC	1,577 ms 21,916 KB
testcase_19	AC	1,596 ms 21,684 KB
testcase_20	AC	1,583 ms 21,992 KB
testcase_21	AC	1,565 ms 22,216 KB
testcase_22	AC	1,577 ms 21,768 KB
testcase_23	AC	1,582 ms 22,216 KB
testcase_24	AC	1,580 ms 21,940 KB
testcase_25	AC	1,588 ms 22,228 KB
testcase_26	AC	1,581 ms 21,952 KB
testcase_27	AC	1,560 ms 22,600 KB
testcase_28	AC	1,580 ms 22,588 KB
testcase_29	AC	1,580 ms 21,940 KB
testcase_30	AC	1,581 ms 21,916 KB
testcase_31	AC	1,585 ms 22,564 KB
testcase_32	AC	1,559 ms 22,276 KB
testcase_33	AC	368 ms 21,868 KB
testcase_34	AC	1,559 ms 21,920 KB
testcase_35	AC	1,591 ms 22,632 KB
testcase_36	AC	1,584 ms 21,928 KB
testcase_37	AC	1,573 ms 22,588 KB
testcase_38	AC	1,582 ms 21,892 KB
testcase_39	AC	1,560 ms 21,904 KB
testcase_40	AC	1,575 ms 22,576 KB
testcase_41	AC	1,581 ms 21,880 KB
testcase_42	AC	1,580 ms 22,456 KB
testcase_43	AC	1,579 ms 22,716 KB
testcase_44	AC	1,566 ms 22,264 KB
testcase_45	AC	1,597 ms 22,456 KB
testcase_46	AC	1,599 ms 22,624 KB
testcase_47	AC	1,583 ms 21,940 KB
testcase_48	AC	1,572 ms 21,904 KB
testcase_49	AC	1,583 ms 22,228 KB
testcase_50	AC	1,563 ms 21,928 KB
testcase_51	AC	1,572 ms 22,276 KB
testcase_52	AC	1,581 ms 21,904 KB
testcase_53	AC	1,580 ms 21,928 KB
testcase_54	AC	1,581 ms 21,952 KB
testcase_55	AC	1,573 ms 22,264 KB
testcase_56	AC	1,568 ms 21,780 KB
testcase_57	AC	1,600 ms 22,868 KB
testcase_58	AC	1,583 ms 22,264 KB
testcase_59	AC	1,574 ms 21,916 KB
testcase_60	AC	1,568 ms 21,904 KB
testcase_61	AC	1,570 ms 22,276 KB
testcase_62	AC	1,579 ms 21,928 KB
testcase_63	AC	1,584 ms 21,964 KB
testcase_64	AC	1,577 ms 22,004 KB
testcase_65	AC	1,581 ms 22,240 KB
testcase_66	AC	1,582 ms 22,456 KB
testcase_67	AC	1,583 ms 21,904 KB
testcase_68	AC	1,583 ms 21,952 KB
testcase_69	AC	1,581 ms 22,588 KB
testcase_70	AC	1,582 ms 22,456 KB
testcase_71	AC	1,558 ms 21,964 KB
testcase_72	AC	1,592 ms 22,276 KB
testcase_73	AC	1,585 ms 22,016 KB
testcase_74	AC	1,584 ms 21,940 KB
testcase_75	AC	1,563 ms 21,792 KB
testcase_76	AC	1,605 ms 22,132 KB
testcase_77	AC	1,580 ms 22,588 KB
testcase_78	AC	1,583 ms 22,728 KB
testcase_79	AC	1,561 ms 22,588 KB
testcase_80	AC	1,582 ms 21,836 KB
testcase_81	AC	1,585 ms 22,900 KB
testcase_82	AC	1,583 ms 22,576 KB
testcase_83	AC	1,560 ms 21,780 KB
testcase_84	AC	1,583 ms 22,560 KB
testcase_85	AC	1,585 ms 22,624 KB
testcase_86	AC	1,576 ms 21,780 KB
testcase_87	AC	1,567 ms 22,576 KB
testcase_88	AC	1,584 ms 22,612 KB
testcase_89	AC	1,584 ms 22,456 KB
testcase_90	AC	1,586 ms 21,796 KB
testcase_91	AC	1,584 ms 22,240 KB
testcase_92	AC	1,585 ms 21,904 KB
testcase_93	AC	1,583 ms 22,612 KB
testcase_94	AC	1,606 ms 22,632 KB
testcase_95	AC	1,579 ms 21,940 KB
testcase_96	AC	835 ms 22,868 KB
testcase_97	AC	1,584 ms 22,716 KB
testcase_98	AC	1,583 ms 21,904 KB
testcase_99	AC	1,585 ms 22,624 KB

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

ソースコード

raw source code

#include <bits/stdc++.h>
using namespace std;
//#include<atcoder/all>
//using namespace atcoder;
using ll = long long int;
using ull = unsigned long long int;
using ld = long double;
constexpr ll MAX = 2000000000000000000;
constexpr ld PI = 3.14159265358979;
constexpr ll MOD = 0;//2024948111;
ld dotorad(ld K){return PI * K / 180.0;}
ld radtodo(ld K){return K * 180.0 / PI;}
mt19937 mt;
void randinit(){srand((unsigned)time(NULL));mt = mt19937(rand());}
ll sute,P;
ll cnt_h[21][20],cnt_w[20][21];//○方向に移動するとき当たる壁
ll k = 0;

struct state{
    bool visited[20][20];
    ll I,J;
    ld score;
    string move;
    ld kaku;
    void init(){
        for(ll i = 0;i < 20;i++) for(ll j = 0;j < 20;j++) visited[i][j] = 0;
        I = 0;
        J = 0;
        visited[0][0] = 1;
        score = 0;
        move = "";
        kaku = 1.0;
    }
};
vector<state> next(state now){
    vector<state> res;
    {
        //UP
        state s = now;
        if(cnt_h[s.I][s.J] <= 3){
            if(cnt_h[s.I][s.J] <= 0) s.kaku *= 1.0 * (100 - P) / 100.0;
            for(ll f = 0;f < cnt_h[s.I][s.J];f++){
                s.kaku *= 1.0 * P / 100.0;
            }
            s.I--;
            s.score += (1 - s.visited[s.I][s.J]) * 100000000 * s.kaku;
            s.visited[s.I][s.J] = 1;
            s.move += 'U';
            res.emplace_back(s);
        }
    }
    {
        //DOWN
        state s = now;
        if(cnt_h[s.I + 1][s.J] <= 3){
            if(cnt_h[s.I + 1][s.J] <= 0) s.kaku *= 1.0 * (100 - P) / 100.0;
            for(ll f = 0;f < cnt_h[s.I + 1][s.J];f++){
                s.kaku *= 1.0 * P / 100.0;
            }
            s.I++;
            s.score += (1 - s.visited[s.I][s.J]) * 100000000 * s.kaku;
            s.visited[s.I][s.J] = 1;
            s.move += 'D';
            res.emplace_back(s);
        }
    }
    {
        //LEFT
        state s = now;
        if(cnt_w[s.I][s.J] <= 3){
            if(cnt_w[s.I][s.J] <= 0) s.kaku *= 1.0 * (100 - P) / 100.0;
            for(ll f = 0;f < cnt_w[s.I][s.J];f++){
                s.kaku *= 1.0 * P / 100.0;
            }
            s.J--;
            s.score += (1 - s.visited[s.I][s.J]) * 100000000 * s.kaku;
            s.visited[s.I][s.J] = 1;
            s.move += 'L';
            res.emplace_back(s);
        }
    }
    {
        //RIGHT
        state s = now;
        if(cnt_w[s.I][s.J + 1] <= 3){
            if(cnt_w[s.I][s.J + 1] <= 0) s.kaku *= 1.0 * (100 - P) / 100.0;
            for(ll f = 0;f < cnt_w[s.I][s.J + 1];f++){
                s.kaku *= 1.0 * P / 100.0;
            }
            s.J++;
            s.score += (1 - s.visited[s.I][s.J]) * 100000000 * s.kaku;
            s.visited[s.I][s.J] = 1;
            s.move += 'R';
            res.emplace_back(s);
        }
    }
    return res;
}
bool operator< (const state &s1, const state &s2){
    return s1.score < s2.score;
};
int main(){
    int ti = clock();
    cin >> sute >> sute >> P;
    for(ll i = 0;i < 21;i++){
        for(ll j = 0;j < 20;j++){
            cnt_h[i][j] = (i == 0 || i == 20) * 100;
            cnt_w[j][i] = (i == 0 || i == 20) * 100;
        }
    }
    while(1){
         //cout<<k<<endl;
        vector<priority_queue<state,vector<state>>> que(401);
        state s;
        s.init();
        que[0].emplace(s);
        state a = s,b = s;
        k++;
        while(1){
            for(ll i = 0;i <= 400;i++){
                if(1.0 * (clock() - ti) / CLOCKS_PER_SEC > 1.5 / 1000 * k) break;
                if(!que[i].empty()){
                    state s = que[i].top();
            //\/ if(i%100==0)cout << i << "," << s.score << " " << s.kaku<<" "<<s.move.size()<< endl;
                    que[i].pop();
                    if(s.I == 19 && s.J == 19){
                        if(a.score < s.score){
                            a = s;
                        }
                    }
                    if(b.score < s.score){
                        b = s;
                    }
                    if(i != 400){
                        vector<state> S = next(s);
                        for(ll j = 0;j < (ll)S.size();j++) que[i + 1].emplace(S[j]);
                        while(que[i + 1].size() > 3) que[i + 1].pop();
                    }
                }
            }
            if(1.0 * (clock() - ti) / CLOCKS_PER_SEC > 1.5 / 1000 * k) break;
        }
        if(k % 3 != 0 || a.move.size() == 0) a = b;
        cout << a.move << endl;
        ll res;
        cin >> res;
        if(res == -1) return 0;
        ll I = 0,J = 0;
        for(ll i = 0;i < res;i++){
            if(a.move[i] == 'U'){
                cnt_h[I][J] = -1;
                I--;
            }
            if(a.move[i] == 'D'){
                cnt_h[I + 1][J] = -1;
                I++;
            }
            if(a.move[i] == 'L'){
                cnt_w[I][J] = -1;
                J--;
            }
            if(a.move[i] == 'R'){
                cnt_w[I][J + 1] = -1;
                J++;
            }
        }
        if(res != (ll)a.move.size()){
            ll i = res;
            if(a.move[i] == 'U'){
                if(cnt_h[I][J] != -1) cnt_h[I][J]++;
            }
            if(a.move[i] == 'D'){
                if(cnt_h[I + 1][J] != -1) cnt_h[I + 1][J]++;
                I++;
            }
            if(a.move[i] == 'L'){
                if(cnt_w[I][J] != -1) cnt_w[I][J]++;
                J--;
            }
            if(a.move[i] == 'R'){
                if(cnt_w[I][J + 1] != -1) cnt_w[I][J + 1]++;
                J++;
            }
        }
    }
}

yukicoder

結果

テストケース

ソースコード