結果
| 問題 | No.5015 Escape from Labyrinth |
| ユーザー |
 Yu_212
|
| 提出日時 | 2023-04-16 17:27:20 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 2,994 ms / 3,000 ms |
| コード長 | 20,437 bytes |
| コンパイル時間 | 7,469 ms |
| コンパイル使用メモリ | 295,312 KB |
| 実行使用メモリ | 43,952 KB |
| スコア | 161,680 |
| 最終ジャッジ日時 | 2023-04-16 17:30:44 |
| 合計ジャッジ時間 | 202,306 ms |
|
ジャッジサーバーID （参考情報） |
judge14 / judge16 |
| 純コード判定しない問題か言語 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2,889 ms
32,356 KB |
| testcase_01 | AC | 2,910 ms
33,332 KB |
| testcase_02 | AC | 2,886 ms
35,984 KB |
| testcase_03 | AC | 722 ms
31,644 KB |
| testcase_04 | AC | 707 ms
27,908 KB |
| testcase_05 | AC | 1,395 ms
38,808 KB |
| testcase_06 | AC | 2,903 ms
34,936 KB |
| testcase_07 | AC | 2,885 ms
30,388 KB |
| testcase_08 | AC | 901 ms
33,892 KB |
| testcase_09 | AC | 2,892 ms
35,628 KB |
| testcase_10 | AC | 1,134 ms
34,584 KB |
| testcase_11 | AC | 2,910 ms
34,312 KB |
| testcase_12 | AC | 2,890 ms
30,840 KB |
| testcase_13 | AC | 1,338 ms
43,952 KB |
| testcase_14 | AC | 876 ms
42,472 KB |
| testcase_15 | AC | 1,229 ms
34,680 KB |
| testcase_16 | AC | 2,885 ms
36,360 KB |
| testcase_17 | AC | 2,891 ms
36,728 KB |
| testcase_18 | AC | 2,866 ms
34,200 KB |
| testcase_19 | AC | 2,866 ms
32,700 KB |
| testcase_20 | AC | 2,864 ms
34,000 KB |
| testcase_21 | AC | 2,895 ms
36,860 KB |
| testcase_22 | AC | 2,883 ms
32,664 KB |
| testcase_23 | AC | 872 ms
32,680 KB |
| testcase_24 | AC | 928 ms
33,792 KB |
| testcase_25 | AC | 2,864 ms
32,000 KB |
| testcase_26 | AC | 963 ms
30,828 KB |
| testcase_27 | AC | 2,867 ms
39,520 KB |
| testcase_28 | AC | 2,860 ms
32,800 KB |
| testcase_29 | AC | 2,867 ms
36,476 KB |
| testcase_30 | AC | 2,863 ms
34,992 KB |
| testcase_31 | AC | 2,863 ms
31,620 KB |
| testcase_32 | AC | 946 ms
37,088 KB |
| testcase_33 | AC | 850 ms
31,600 KB |
| testcase_34 | AC | 2,863 ms
35,776 KB |
| testcase_35 | AC | 1,176 ms
38,268 KB |
| testcase_36 | AC | 1,083 ms
37,512 KB |
| testcase_37 | AC | 2,866 ms
42,908 KB |
| testcase_38 | AC | 2,861 ms
40,324 KB |
| testcase_39 | AC | 791 ms
35,476 KB |
| testcase_40 | AC | 1,132 ms
33,800 KB |
| testcase_41 | AC | 2,869 ms
34,536 KB |
| testcase_42 | AC | 2,862 ms
37,524 KB |
| testcase_43 | AC | 2,864 ms
32,068 KB |
| testcase_44 | AC | 906 ms
36,876 KB |
| testcase_45 | AC | 1,231 ms
39,264 KB |
| testcase_46 | AC | 2,861 ms
37,216 KB |
| testcase_47 | AC | 1,092 ms
34,064 KB |
| testcase_48 | AC | 999 ms
39,468 KB |
| testcase_49 | AC | 820 ms
34,712 KB |
| testcase_50 | AC | 1,096 ms
33,928 KB |
| testcase_51 | AC | 2,892 ms
34,096 KB |
| testcase_52 | AC | 1,021 ms
34,956 KB |
| testcase_53 | AC | 2,866 ms
34,376 KB |
| testcase_54 | AC | 863 ms
37,544 KB |
| testcase_55 | AC | 2,867 ms
36,760 KB |
| testcase_56 | AC | 1,078 ms
38,588 KB |
| testcase_57 | AC | 2,862 ms
35,756 KB |
| testcase_58 | AC | 2,862 ms
34,644 KB |
| testcase_59 | AC | 596 ms
32,188 KB |
| testcase_60 | AC | 1,024 ms
34,136 KB |
| testcase_61 | AC | 1,035 ms
32,896 KB |
| testcase_62 | AC | 960 ms
33,664 KB |
| testcase_63 | AC | 908 ms
35,364 KB |
| testcase_64 | AC | 761 ms
33,208 KB |
| testcase_65 | AC | 2,861 ms
35,216 KB |
| testcase_66 | AC | 1,021 ms
33,784 KB |
| testcase_67 | AC | 1,026 ms
35,328 KB |
| testcase_68 | AC | 2,890 ms
33,884 KB |
| testcase_69 | AC | 971 ms
35,800 KB |
| testcase_70 | AC | 2,889 ms
38,352 KB |
| testcase_71 | AC | 1,262 ms
38,644 KB |
| testcase_72 | AC | 968 ms
34,960 KB |
| testcase_73 | AC | 833 ms
35,680 KB |
| testcase_74 | AC | 781 ms
35,540 KB |
| testcase_75 | AC | 950 ms
33,572 KB |
| testcase_76 | AC | 1,182 ms
42,412 KB |
| testcase_77 | AC | 777 ms
33,184 KB |
| testcase_78 | AC | 2,887 ms
38,860 KB |
| testcase_79 | AC | 932 ms
33,152 KB |
| testcase_80 | AC | 1,145 ms
34,668 KB |
| testcase_81 | AC | 694 ms
28,528 KB |
| testcase_82 | AC | 1,106 ms
31,024 KB |
| testcase_83 | AC | 2,865 ms
32,816 KB |
| testcase_84 | AC | 908 ms
39,300 KB |
| testcase_85 | AC | 2,861 ms
31,980 KB |
| testcase_86 | AC | 2,890 ms
37,992 KB |
| testcase_87 | AC | 2,861 ms
34,932 KB |
| testcase_88 | AC | 2,867 ms
35,212 KB |
| testcase_89 | AC | 926 ms
36,120 KB |
| testcase_90 | AC | 2,868 ms
33,004 KB |
| testcase_91 | AC | 809 ms
30,860 KB |
| testcase_92 | AC | 1,219 ms
43,340 KB |
| testcase_93 | AC | 2,918 ms
40,892 KB |
| testcase_94 | AC | 2,957 ms
37,924 KB |
| testcase_95 | AC | 1,044 ms
34,652 KB |
| testcase_96 | AC | 1,331 ms
36,156 KB |
| testcase_97 | AC | 1,061 ms
36,228 KB |
| testcase_98 | AC | 2,994 ms
37,416 KB |
| testcase_99 | AC | 1,044 ms
36,544 KB |
ソースコード
#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.8;
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);
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};
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){
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();
}