結果

問題 No.5015 Escape from Labyrinth
ユーザー Yu_212Yu_212
提出日時 2023-04-16 17:39:37
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 22,121 bytes
コンパイル時間 6,253 ms
コンパイル使用メモリ 296,276 KB
実行使用メモリ 43,388 KB
スコア 168,300
最終ジャッジ日時 2023-04-16 17:42:44
合計ジャッジ時間 77,850 ms
ジャッジサーバーID
(参考情報)
judge14 / judge12
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 630 ms
31,788 KB
testcase_01 AC 2,842 ms
33,168 KB
testcase_02 AC 655 ms
35,980 KB
testcase_03 AC 2,812 ms
31,008 KB
testcase_04 AC 2,812 ms
27,296 KB
testcase_05 AC 2,817 ms
37,832 KB
testcase_06 AC 2,838 ms
34,256 KB
testcase_07 AC 2,835 ms
29,940 KB
testcase_08 AC 694 ms
33,332 KB
testcase_09 AC 634 ms
35,336 KB
testcase_10 AC 2,818 ms
34,368 KB
testcase_11 AC 744 ms
34,032 KB
testcase_12 AC 2,811 ms
30,396 KB
testcase_13 AC 1,145 ms
43,388 KB
testcase_14 AC 758 ms
42,092 KB
testcase_15 AC 2,841 ms
34,116 KB
testcase_16 AC 755 ms
35,696 KB
testcase_17 AC 842 ms
36,016 KB
testcase_18 AC 835 ms
33,720 KB
testcase_19 AC 630 ms
32,196 KB
testcase_20 AC 2,867 ms
33,680 KB
testcase_21 AC 755 ms
36,500 KB
testcase_22 AC 2,839 ms
31,992 KB
testcase_23 AC 2,815 ms
31,876 KB
testcase_24 AC 826 ms
33,204 KB
testcase_25 AC 562 ms
31,636 KB
testcase_26 AC 537 ms
30,044 KB
testcase_27 AC 1,356 ms
38,788 KB
testcase_28 AC 2,815 ms
32,224 KB
testcase_29 AC 1,051 ms
36,512 KB
testcase_30 AC 2,816 ms
34,616 KB
testcase_31 AC 517 ms
31,028 KB
testcase_32 AC 634 ms
36,732 KB
testcase_33 AC 684 ms
31,152 KB
testcase_34 AC 2,838 ms
35,284 KB
testcase_35 AC 2,817 ms
37,528 KB
testcase_36 AC 952 ms
36,888 KB
testcase_37 AC 2,844 ms
42,400 KB
testcase_38 AC 2,829 ms
39,972 KB
testcase_39 AC 645 ms
35,164 KB
testcase_40 AC 789 ms
33,244 KB
testcase_41 AC 872 ms
33,980 KB
testcase_42 AC 2,819 ms
37,872 KB
testcase_43 AC 2,838 ms
31,820 KB
testcase_44 AC 777 ms
36,828 KB
testcase_45 AC 2,819 ms
38,464 KB
testcase_46 AC 2,850 ms
36,776 KB
testcase_47 AC 595 ms
33,924 KB
testcase_48 AC 2,821 ms
38,772 KB
testcase_49 AC 556 ms
34,176 KB
testcase_50 AC 507 ms
33,308 KB
testcase_51 AC 674 ms
33,732 KB
testcase_52 AC 740 ms
34,408 KB
testcase_53 AC 2,815 ms
33,872 KB
testcase_54 AC 704 ms
37,084 KB
testcase_55 AC 640 ms
36,276 KB
testcase_56 AC 948 ms
37,916 KB
testcase_57 AC 892 ms
35,616 KB
testcase_58 AC 2,838 ms
34,404 KB
testcase_59 AC 721 ms
31,936 KB
testcase_60 AC 2,845 ms
33,612 KB
testcase_61 AC 2,843 ms
32,292 KB
testcase_62 AC 2,843 ms
33,152 KB
testcase_63 AC 2,866 ms
34,964 KB
testcase_64 AC 2,824 ms
33,052 KB
testcase_65 AC 2,845 ms
34,040 KB
testcase_66 AC 960 ms
33,456 KB
testcase_67 AC 641 ms
35,144 KB
testcase_68 AC 2,845 ms
33,216 KB
testcase_69 AC 2,819 ms
35,540 KB
testcase_70 TLE -
testcase_71 AC 1,214 ms
37,944 KB
testcase_72 AC 820 ms
34,208 KB
testcase_73 AC 2,865 ms
35,508 KB
testcase_74 AC 788 ms
35,148 KB
testcase_75 AC 787 ms
33,364 KB
testcase_76 AC 2,843 ms
41,576 KB
testcase_77 AC 2,843 ms
32,744 KB
testcase_78 AC 1,123 ms
38,828 KB
testcase_79 AC 892 ms
32,676 KB
testcase_80 AC 2,849 ms
34,208 KB
testcase_81 AC 2,813 ms
27,784 KB
testcase_82 AC 641 ms
30,852 KB
testcase_83 AC 860 ms
32,060 KB
testcase_84 AC 2,843 ms
38,820 KB
testcase_85 AC 508 ms
31,460 KB
testcase_86 AC 838 ms
37,768 KB
testcase_87 AC 2,878 ms
34,680 KB
testcase_88 AC 792 ms
35,132 KB
testcase_89 AC 2,866 ms
35,676 KB
testcase_90 AC 2,868 ms
32,540 KB
testcase_91 AC 516 ms
30,360 KB
testcase_92 AC 2,848 ms
42,992 KB
testcase_93 AC 2,825 ms
40,420 KB
testcase_94 AC 2,821 ms
37,612 KB
testcase_95 AC 726 ms
34,192 KB
testcase_96 AC 789 ms
35,628 KB
testcase_97 AC 715 ms
35,660 KB
testcase_98 AC 2,821 ms
37,524 KB
testcase_99 AC 669 ms
36,192 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>
// #include "atcoder/all"

using namespace std;

using i64 = long long;

const i64 MOD = 1e9 + 7;
const i64 INF = i64(1e18);

template <typename T>
bool chmin(T& x, T y){
    if(x > y){
        x = y;
        return true;
    }
    return false;
}

template <typename T>
bool chmax(T& x, T y){
    if(x < y){
        x = y;
        return true;
    }
    return false;
}


double elapsed_time(timespec& time_st){
    timespec time_now;
    clock_gettime(CLOCK_REALTIME, &time_now);
    return (time_now.tv_sec - time_st.tv_sec) + (time_now.tv_nsec - time_st.tv_nsec) / 1000000000.0;
}

struct Rnd{
    uint64_t x;
    Rnd(uint64_t seed) :
            x(0xdeadbeef0110dead ^ seed)
    {
    }
    uint64_t rnd(){
        x ^= x << 7;
        x ^= x >> 9;
        return x;
    }
    uint64_t rnd(int n){
        return rnd() % n;
    }
    double rnd_double(){
        return 1.0 * rnd() / numeric_limits<uint64_t>::max();
    }
    vector<int> rnd_perm(int n){
        vector<int> v(n);
        iota(v.begin(), v.end(), 0);
        for(int i = n - 1; i >= 1; --i){
            int j = rnd(i + 1);
            swap(v[i], v[j]);
        }
        return v;
    }
    template<typename T>
    void shuffle(vector<T>& v){
        int n = v.size();
        for(int i = n - 1; i >= 1; --i){
            int j = rnd(i + 1);
            swap(v[i], v[j]);
        }
    }
};


// #define OPTIMIZE

namespace params{
void load_params(){
    ifstream ifs("../params.txt");
    assert(ifs.is_open());
}
}


void read_file(istream& ifs){
    // TODO: input
}

clock_t st;

void solve(){
    constexpr int K = 60;
    int n, damage, hp_max;
    cin >> n >> damage >> hp_max;
    vector<string> s(n);
    vector<vector<int>> v(n, vector<int>(n, 0));
    vector<int> dx = {0, 1, 0, -1};
    vector<int> dy = {1, 0, -1, 0};

    // 0: .
    // 1: #
    // 2: J (jewel)
    // 3: F (fire?)
    // 4: E (detecter)

    int sx, sy, ex, ey, kx, ky;
    vector<pair<pair<int,int>, int>> detectors;
    vector<pair<int,int>> jewels_;
    for(int i = 0; i < n; ++i){
        cin >> s[i];
        for(int j = 0; j < n; ++j){
            if(s[i][j] == '.'){
                v[i][j] = 0;
            }
            else if(s[i][j] == '#'){
                v[i][j] = 1;
            }
            else if(s[i][j] == 'S'){
                sx = i;
                sy = j;
            }
            else if(s[i][j] == 'G'){
                ex = i;
                ey = j;
            }
            else if(s[i][j] == 'K'){
                kx = i;
                ky = j;
            }
            else if(s[i][j] == 'J'){
                v[i][j] = 2;
                jewels_.emplace_back(i, j);
            }
            else if(s[i][j] == 'F'){
                v[i][j] = 3;
            }
            else if(s[i][j] == 'E'){
                v[i][j] = 4;
            }
        }
    }
    vector<pair<int,int>> jewels;
    jewels.emplace_back(sx, sy);
    jewels.emplace_back(kx, ky);
    jewels.emplace_back(ex, ey);
    for(auto& p : jewels_){
        jewels.emplace_back(p);
    }

    int num_detectors;
    cin >> num_detectors;
    for(int i = 0; i < num_detectors; ++i){
        int x, y, d;
        cin >> x >> y >> d;
        detectors.emplace_back(make_pair(x, y), d);
    }

    auto is_jewel = [&](int x, int y){
        return v[x][y] == 2;
    };
    auto is_wall = [&](int x, int y){
        if(x < 0 || y < 0 || x >= n || y >= n){
            return true;
        }
        return v[x][y] == 1 || v[x][y] == 4;
    };
    vector<vector<vector<int>>> damage_vec(n, vector<vector<int>>(n, vector<int>(K, 0)));
    vector<vector<int>> damage_sum(n, vector<int>(n, 0));
    for(auto [p, interval] : detectors){
        for(int d = 0; d < 4; ++d){
            auto [x, y] = p;
            do{
                // for(int i = interval - 1; i < K; i += interval){
                for(int i = 0; i < K; i += interval){
                    damage_vec[x][y][i] += damage;
                }
                damage_sum[x][y] += damage * K / interval;
                x += dx[d];
                y += dy[d];
            }while(!is_wall(x, y));
        }
    }

    int m = jewels.size();
    // dijkstra by average damage
    vector<vector<double>> dist_ave(m, vector<double>(m, MOD));
    vector<vector<vector<int>>> table_move(m, vector<vector<int>>(m));

    auto connected = [&](int x, int y){
        return dist_ave[x][y] < 1e9;
    };

    for(int jewel_idx = 0; jewel_idx < m; ++jewel_idx){
        // dijkstra
        auto [jx, jy] = jewels[jewel_idx];
        vector<vector<double>> dist(n, vector<double>(n, MOD));
        vector<vector<int>> prev(n, vector<int>(n, -1));
        priority_queue<pair<double,pair<int,int>>, vector<pair<double,pair<int,int>>>, greater<>> que;
        dist[jx][jy] = 0;
        que.emplace(0, make_pair(jx, jy));
        while(!que.empty()){
            auto [now_dist, p] = que.top();
            auto [x, y] = p;
            que.pop();
            if(now_dist != dist[x][y]){
                continue;
            }
            for(int d = 0; d < 4; ++d){
                int nx = x + dx[d];
                int ny = y + dy[d];
                if(is_wall(nx, ny)){
                    continue;
                }
                if(chmin(dist[nx][ny], now_dist + 1.0 * damage_sum[nx][ny] / K + 1)){
                    prev[nx][ny] = d;
                    que.emplace(dist[nx][ny], make_pair(nx, ny));
                }
            }
        }
        for(int i = 0; i < m; ++i){
            dist_ave[jewel_idx][i] = dist[jewels[i].first][jewels[i].second];
            int x = jewels[i].first;
            int y = jewels[i].second;
            if(prev[x][y] == -1){
                continue;
            }
            vector<int> moves;
            while(x != jx || y != jy){
                int d = prev[x][y];
                moves.emplace_back(prev[x][y]);
                x += dx[d ^ 2];
                y += dy[d ^ 2];
            }
            reverse(moves.begin(), moves.end());
            table_move[jewel_idx][i] = moves;
        }
    }

    auto simulate = [&](vector<int>& moves){
        int x = sx, y = sy;
        bool key = false;
        int turn = 1;
        int damage = 0;
        int jewel = 0;
        set<pair<int,int>> jew;
        for(auto d : moves){
            if(d < 4){
                x += dx[d], y += dy[d];
            }
            ++damage;
            damage += damage_vec[x][y][turn % 60];
            if(is_jewel(x, y) && !jew.count(make_pair(x, y))){
                ++jewel;
                jew.emplace(x, y);
            }
            ++turn;
            assert(!is_wall(x, y));
            if(x == kx && y == ky){
                key = true;
            }
        }
        assert(x == ex && y == ey);
        assert(key);
        return make_pair(jewel, damage);
    };
    auto output = [&](vector<int>& moves){
        for(auto d : moves){
            // cout << dx[d] << " " << dy[d] << " " << "RDLU"[d] << endl;
            if(d < 4){
                cout << "M " << "RDLU"[d] << endl;
            }
            else{
                cout << "S" << endl;
            }
        }
    };

    Rnd rn(0);

    auto get_moves = [&](vector<int>& route){
        assert(route.front() == 0);
        assert(route.back() == 2);
        vector<int> moves;
        for(int i = 0; i < route.size() - 1; ++i){
            auto [x, y] = jewels[route[i]];
            for(auto d : table_move[route[i]][route[i + 1]]){
                x += dx[d];
                y += dy[d];
                moves.emplace_back(d);
            }
            assert(make_pair(x, y) == jewels[route[i + 1]]);
        }
        return moves;
    };

    auto get_optimal_moves = [&](vector<int>& route){
        auto moves = get_moves(route);
        vector<vector<int>> dp(moves.size() + 1, vector<int>(60, MOD));
        vector<vector<int>> pre(moves.size() + 1, vector<int>(60, MOD));
        int x = sx, y = sy;
        int su = 0;
        for(int i = 0; i < 60; ++i){
            dp[0][i] = su;
            su += damage_vec[x][y][(i + 1) % 60] + 1;
        }

        for(int i = 0; i < moves.size(); ++i){
            int d = moves[i];
            int nx = x + dx[d];
            int ny = y + dy[d];
            auto v = dp[i];
            vector<int> v_pre(60);
            iota(v_pre.begin(), v_pre.end(), 0);
            for(int j = 0; j < 120; ++j){
                if(chmin(v[(j + 1) % 60], v[j % 60] + damage_vec[x][y][(j + 1) % 60] + 1)){
                    v_pre[(j + 1) % 60] = v_pre[j % 60];
                }
            }
            for(int j = 0; j < 60; ++j){
                dp[i + 1][(j + 1) % 60] = v[j] + damage_vec[nx][ny][(j + 1) % 60] + 1;
                pre[i + 1][(j + 1) % 60] = v_pre[j];
            }
            x = nx;
            y = ny;
        }
        int j = distance(dp.back().begin(), min_element(dp.back().begin(), dp.back().end()));
        vector<int> mods{j};
        for(int i = moves.size() - 1; i >= 0; --i){
            int pre_j = pre[i + 1][j];
            j = pre_j;
            mods.emplace_back(j);
        }
        reverse(mods.begin(), mods.end());

        vector<int> res;
        for(int i = 0; i < mods[0]; ++i){
            // wait
            res.emplace_back(5);
        }
        assert(moves.size() + 1 == mods.size());
        for(int i = 0; i < mods.size() - 1; ++i){
            int cn = 0;
            for(int j_ = mods[i]; (j_ + 1) % 60 != mods[i + 1]; ++j_){
                ++cn;
                res.emplace_back(5);
            }
            res.emplace_back(moves[i]);
        }
        return res;
    };

    auto get_damage = [&](vector<int>& route){
        array<int, 60> dp{};
        array<int, 60> nex{};
        int x = sx, y = sy;
        int su = 0;
        for(int i = 0; i < 60; ++i){
            dp[i] = su;
            su += damage_vec[x][y][(i + 1) % 60] + 1;
        }
        auto moves = get_moves(route);
        for(auto d : moves){
            int nx = x + dx[d];
            int ny = y + dy[d];
            assert(!is_wall(x, y));
            assert(!is_wall(nx, ny));
            for(int i = 0; i < 120; ++i){
                chmin(dp[(i + 1) % 60], dp[i % 60] + damage_vec[x][y][(i + 1) % 60] + 1);
            }
            for(int i = 0; i < 60; ++i){
                nex[(i + 1) % 60] = dp[i] + damage_vec[nx][ny][(i + 1) % 60] + 1;
            }
            x = nx;
            y = ny;
            swap(dp, nex);
        }

        // auto moves_ = get_optimal_moves(route);
        // auto [sc, dam] = simulate(moves_);
        // assert(*min_element(dp.begin(), dp.end()) == dam);

        return *min_element(dp.begin(), dp.end());
    };

    clock_t mid = clock();
    double mid_elapsed = 1.0 * (mid - st) / CLOCKS_PER_SEC;
    constexpr double TIME_MAX = 2.75;

    auto sa = [&](vector<int>& route, vector<int>& fl, double& dist_sum){
        while(true){
            double tim = 1.0 * (clock() - mid) / CLOCKS_PER_SEC;
            double per = tim / (TIME_MAX - mid_elapsed);
            if(per >= 1.0){
                break;
            }
            // erase != add
            vector<pair<double, int>> erase_adv;
            for(int erase_pos = 1; erase_pos < route.size() - 2; ++erase_pos){
                int x = route[erase_pos - 1];
                int y = route[erase_pos];
                int z = route[erase_pos + 1];
                if(y == 1){
                    continue;
                }
                erase_adv.emplace_back(dist_ave[x][y] + dist_ave[y][z] - dist_ave[x][z], erase_pos);
            }
            vector<tuple<double, int, int>> add_adv;
            for(int add_pos = 1; add_pos < route.size() - 2; ++add_pos){
                int x = route[add_pos - 1];
                int y = route[add_pos];
                for(int j = 3; j < jewels.size(); ++j){
                    if(fl[j]){
                        continue;
                    }
                    if(!connected(x, j) || !connected(j, y)){
                        continue;
                    }
                    double adv = dist_ave[x][y] - dist_ave[x][j] - dist_ave[j][y];
                    add_adv.emplace_back(adv, add_pos, j);
                }
            }
            constexpr size_t T = 10000;
            int te = min(erase_adv.size(), T);
            int ta = min(add_adv.size(), T);
            // nth_element(erase_adv.begin(), erase_adv.begin() + te, erase_adv.end(), greater<>());
            // nth_element(add_adv.begin(), add_adv.begin() + ta, add_adv.end(), greater<>());
            sort(erase_adv.begin(), erase_adv.end(), greater<>());
            sort(add_adv.begin(), add_adv.end(), greater<>());

            tuple<double,int,int,int> bes(-INF, 0, 0, 0);
            for(int i = 0; i < te; ++i){
                auto [e_val, erase_pos] = erase_adv[i];
                for(int j = 0; j < ta; ++j){
                    auto [a_val, add_pos, add_elm] = add_adv[j];
                    if(e_val + a_val < get<0>(bes)){
                        break;
                    }
                    if(erase_pos == add_pos || erase_pos + 1 == add_pos){
                        continue;
                    }
                    chmax(bes, make_tuple(e_val + a_val, erase_pos, add_pos, add_elm));
                }
            }
            auto [adv, erase_pos, add_pos, add_elm] = bes;
            if(adv < 0){
                return false;
            }

            fl[route[erase_pos]] = false;
            fl[add_elm] = true;

            dist_sum -= dist_ave[route[erase_pos - 1]][route[erase_pos]];
            dist_sum -= dist_ave[route[erase_pos]][route[erase_pos + 1]];
            dist_sum += dist_ave[route[erase_pos - 1]][route[erase_pos + 1]];

            dist_sum += dist_ave[route[add_pos - 1]][add_elm];
            dist_sum += dist_ave[add_elm][route[add_pos]];
            dist_sum -= dist_ave[route[add_pos - 1]][route[add_pos]];

            route.erase(route.begin() + erase_pos);
            if(erase_pos < add_pos){
                --add_pos;
            }
            route.insert(route.begin() + add_pos, add_elm);
            {
                if(dist_sum < hp_max){
                    return true;
                }
            }
        }
        return false;
    };

    auto sa2 = [&](vector<int>& route, vector<int>& fl, double& dist_sum){
        // cout << "sa2" << endl;
        auto now_damage = get_damage(route);
        if(now_damage < hp_max){
            return true;
        }
        /*
        // TODO: koko iranai kamo
        while(true){
            // cout << "sa2 iter" << endl;
            double tim = 1.0 * (clock() - mid) / CLOCKS_PER_SEC;
            double per = tim / (TIME_MAX - mid_elapsed);
            if(per >= 1.0){
                break;
            }

            // erase != add
            vector<pair<double, int>> erase_adv;
            for(int erase_pos = 1; erase_pos < route.size() - 2; ++erase_pos){
                int x = route[erase_pos - 1];
                int y = route[erase_pos];
                int z = route[erase_pos + 1];
                if(y == 1){
                    continue;
                }
                erase_adv.emplace_back(dist_ave[x][y] + dist_ave[y][z] - dist_ave[x][z], erase_pos);
            }
            vector<tuple<double, int, int>> add_adv;
            for(int add_pos = 1; add_pos < route.size() - 2; ++add_pos){
                int x = route[add_pos - 1];
                int y = route[add_pos];
                for(int j = 3; j < jewels.size(); ++j){
                    if(fl[j]){
                        continue;
                    }
                    if(!connected(x, j) || !connected(j, y)){
                        continue;
                    }
                    double adv = dist_ave[x][y] - dist_ave[x][j] - dist_ave[j][y];
                    add_adv.emplace_back(adv, add_pos, j);
                }
            }
            constexpr size_t T = 3;
            int te = min(erase_adv.size(), T);
            int ta = min(add_adv.size(), T);
            nth_element(erase_adv.begin(), erase_adv.begin() + te, erase_adv.end(), greater<>());
            nth_element(add_adv.begin(), add_adv.begin() + ta, add_adv.end(), greater<>());
            // sort(erase_adv.begin(), erase_adv.end(), greater<>());
            // sort(add_adv.begin(), add_adv.end(), greater<>());

            tuple<int,int,int,int> bes(MOD, 0, 0, 0);
            for(int i = 0; i < te; ++i){
                auto [e_val, erase_pos] = erase_adv[i];
                for(int j = 0; j < ta; ++j){
                    auto [a_val, add_pos, add_elm] = add_adv[j];
                    if(e_val + a_val < get<0>(bes)){
                        break;
                    }
                    if(erase_pos == add_pos || erase_pos + 1 == add_pos){
                        continue;
                    }

                    // TODO
                    fl[route[erase_pos]] = false;
                    fl[add_elm] = true;
                    auto nex_route = route;
                    nex_route.erase(nex_route.begin() + erase_pos);
                    if(erase_pos < add_pos){
                        --add_pos;
                    }
                    nex_route.insert(nex_route.begin() + add_pos, add_elm);
                    auto nex_damage = get_damage(nex_route);
                    if(now_damage < nex_damage){
                        // NG
                    }
                    else{
                        // OK
                        chmin(bes, make_tuple(nex_damage, erase_pos, add_pos, add_elm));
                    }
                }
            }
            if(get<0>(bes) < now_damage){
                auto [nex_damage, erase_pos, add_pos, add_elm] = bes;
                now_damage = nex_damage;
                fl[route[erase_pos]] = false;
                fl[add_elm] = true;
                route.erase(route.begin() + erase_pos);
                if(erase_pos < add_pos){
                    --add_pos;
                }
                route.insert(route.begin() + add_pos, add_elm);
                if(nex_damage < hp_max){
                    // cout << "OK: " << route.size() << endl;
                    return true;
                }
            }
        }
         */
        return false;
    };


    vector<int> fl(jewels.size(), 0);
    vector<int> route;

    auto greed = [&](){
        int dist = 0;
        route.emplace_back(0);
        fl[0] = fl[1] = fl[2] = true;
        constexpr double coef = 0.2;
        while(true){
            pair<double,int> mi(INF, 0);
            for(int i = 3; i < m; ++i){
                if(!fl[i]){
                    chmin(mi, make_pair(dist_ave[route.back()][i] + coef * dist_ave[i][1], i));
                }
            }
            if(dist + dist_ave[route.back()][mi.second] + dist_ave[route.back()][1] > hp_max / 2){
                break;
            }
            dist += dist_ave[route.back()][mi.second];
            route.emplace_back(mi.second);
            fl[mi.second] = true;
        }
        route.emplace_back(1);
        while(true){
            pair<double,int> mi(INF, 0);
            for(int i = 3; i < m; ++i){
                if(!fl[i]){
                    chmin(mi, make_pair(dist_ave[route.back()][i] + coef * dist_ave[i][2], i));
                }
            }
            if(dist + dist_ave[route.back()][mi.second] + dist_ave[route.back()][2] > hp_max){
                break;
            }
            dist += dist_ave[route.back()][mi.second];
            route.emplace_back(mi.second);
            fl[mi.second] = true;
        }
        route.emplace_back(2);
    };
    greed();

    /*
    fl[0] = fl[1] = fl[2] = true;
    for(int i = 1; i <= 10; ++i){
        fl[i * 10] = true;
    }
    vector<int> route{0, 10, 20, 30, 40, 50, 1, 60, 70, 80, 90, 100, 2};
     *

    /*
    vector<int> route{0};
    for(int i = 0; i < min(20, int(jewels.size())); ++i){
        route.emplace_back(i + 2);
    }
    route.emplace_back(1);
    for(int i = 0; i < min(20, int(jewels.size() - 22)); ++i){
        route.emplace_back(i + 22);
    }
    route.emplace_back(2);
     */
    double dist_sum = 0;
    for(int i = 0; i < route.size() - 1; ++i){
        dist_sum += dist_ave[route[i]][route[i + 1]];
    }
    auto bef = route;
    while(true){
        clog << route.size() << endl;
        if(sa(route, fl, dist_sum) || sa2(route, fl, dist_sum)){
            // auto moves = get_optimal_moves(route);
            // auto [sc, dam] = simulate(moves);
            // cout << route.size() << ": " << sc << " " << dam << endl;

            bef = route;
            if(route.size() == jewels.size()){
                break;
            }
            while(true){
                int pos = rn.rnd(route.size() - 2) + 1;
                int add = rn.rnd(jewels.size() - 2) + 2;
                if(!connected(route[pos - 1], add) || !connected(add, route[pos])){
                    continue;
                }
                if(fl[add]){
                    continue;
                }
                else{
                    dist_sum -= dist_ave[route[pos - 1]][route[pos]];
                    dist_sum += dist_ave[route[pos - 1]][add];
                    dist_sum += dist_ave[add][route[pos]];
                    route.insert(route.begin() + pos, add);
                    fl[add] = true;
                    break;
                }
            }
        }
        else{
            route = bef;
            break;
        }
    }

    sa2(route, fl, dist_sum);

    auto moves = get_optimal_moves(route);
    output(moves);
    auto [sc, dam] = simulate(moves);
    clog << "turn: " << moves.size() << endl;
    clog << "score: " << sc << endl;
    clog << "damage: " << dam << endl;
}

signed main(){

    st = clock();

#ifdef OPTIMIZE
    params::load_params();
#endif

#ifndef HAND
    read_file(cin);
#else
    ifstream ifs("./tools/in/0000.txt");
    assert(ifs.is_open());
    read_file(ifs);
#endif
    solve();
}
0