結果
問題 | No.5019 Hakai Project |
ユーザー |
![]() |
提出日時 | 2023-11-19 20:09:08 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2,964 ms / 3,000 ms |
コード長 | 26,889 bytes |
コンパイル時間 | 5,509 ms |
コンパイル使用メモリ | 236,540 KB |
実行使用メモリ | 136,044 KB |
スコア | 2,673,675,982 |
最終ジャッジ日時 | 2023-11-19 20:11:51 |
合計ジャッジ時間 | 162,508 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge15 |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 50 |
コンパイルメッセージ
main.cpp: In member function 'NBD* NBDGenerator::Generate(Solution*, int, double)': main.cpp:1010:3: warning: control reaches end of non-void function [-Wreturn-type] 1010 | } | ^ main.cpp: In static member function 'static void Pos::StaticInit(int)': main.cpp:350:24: warning: 'dir' may be used uninitialized [-Wmaybe-uninitialized] 350 | move_to[dir][p] = {adj_x, adj_y}; | ^ main.cpp:337:17: note: 'dir' declared here 337 | Dir dir; | ^~~
ソースコード
namespace atcoder {}#ifdef LOCAL#define dbg(x) cerr << __LINE__ << " : " << #x << " = " << (x) << endl;#else#define NDEBUG#define dbg(x) true;#pragma GCC target("avx2")#pragma GCC optimize("O3")#pragma GCC optimize("unroll-loops")#endif#ifdef GTEST#include <gtest/gtest.h>#endif#include <math.h>#include <algorithm>#include <array>#include <bitset>#include <cassert>#include <chrono>#include <cstdlib>#include <cstring>#include <functional>#include <iomanip>#include <iostream>#include <limits>#include <list>#include <map>#include <numeric>#include <queue>#include <set>#include <sstream>#include <stack>#include <string>#include <tuple>#include <unordered_map>#include <unordered_set>#include <vector>#ifdef PERF#include <gperftools/profiler.h>#endifusing namespace std;using namespace atcoder;#define fast_io \ios_base::sync_with_stdio(false); \cin.tie(0); \cout.tie(0);#define ll long long int#define rep(i, n) for (int i = 0; i < (int)(n); i++)#define reps(i, n) for (int i = 1; i <= (int)(n); i++)#define REP(i, n) for (int i = n - 1; i >= 0; i--)#define REPS(i, n) for (int i = n; i > 0; i--)#define MOD (long long int)(1e9 + 7)#define INF (int)(1e9)#define LINF (long long int)(1e18)#define chmax(a, b) a = (((a) < (b)) ? (b) : (a))#define chmin(a, b) a = (((a) > (b)) ? (b) : (a))#define ALL(v) v.begin(), v.end()typedef pair<int, int> Pii;typedef pair<ll, ll> Pll;constexpr double PI = acos(-1);#ifdef NDEBUG#define CHECK(v1, op, v2)#else#define CHECK(v1, op, v2) \if (!((v1)op(v2))) { \cerr << "ERROR:" << (v1) << " " << (v2) << endl; \assert((v1)op(v2)); \}#endiflong double nCr(const int n, const int r) {long double ret = 1;rep(t, r) {ret *= (n - t);ret /= (r - t);}return ret;}template <typename T>string to_string(const vector<T>& vec) {string ret = "";rep(i, vec.size()) {ret += vec[i].to_string();if (i + 1 != vec.size()) {ret += ",";}}return ret;}template <typename T>ostream& operator<<(ostream& os, const vector<T>& vec) {os << to_string(vec);return os;}uint32_t xorshift() {static uint32_t x = 12345789;static uint32_t y = 362436069;static uint32_t z = 521288629;static uint32_t w = 88675123;uint32_t t;t = x ^ (x << 11);x = y;y = z;z = w;w ^= t ^ (t >> 8) ^ (w >> 19);return w;}int rand(const uint32_t l, const uint32_t r) {return xorshift() % (r - l) + l;}uint32_t rand_other_than(const uint32_t l, const uint32_t r,const uint32_t other) {const uint32_t num = rand(l, r - 1);return num + (num >= other);}template <typename T>const T& rand_vec(const vector<T>& vec) {assert(vec.size() > 0);return vec[rand(0, vec.size())];}template <typename T>void shuffle(vector<T>& vec) {rep(l, (int)vec.size() - 1) {const int idx = rand(l, vec.size());swap(vec[idx], vec[l]);}}class Timer {chrono::system_clock::time_point _start, _end;ll _sum = 0, _count = 0;public:void start() { _start = chrono::system_clock::now(); }void stop() { _end = chrono::system_clock::now(); }void add() {const chrono::system_clock::time_point now = chrono::system_clock::now();_sum += static_cast<double>(chrono::duration_cast<chrono::nanoseconds>(now - _start).count());_count++;}ll sum() const { return _sum / 1000; }int count() const { return _count; }string average() const {if (_count == 0) {return "NaN";}return to_string(_sum / 1000 / _count);}void reset() {_start = chrono::system_clock::now();_sum = 0;_count = 0;}inline int ms() const {const chrono::system_clock::time_point now = chrono::system_clock::now();return static_cast<double>(chrono::duration_cast<chrono::microseconds>(now - _start).count() /1000);}inline int ns() const {const chrono::system_clock::time_point now = chrono::system_clock::now();return static_cast<double>(chrono::duration_cast<chrono::microseconds>(now - _start).count());}};#ifdef LOCALstruct Timers : unordered_map<string, Timer> {friend ostream& operator<<(ostream& os, const Timers& timers) {for (const auto& pa : timers) {os << pa.first << " time: " << pa.second.sum() / 1000<< " count: " << pa.second.count() << endl;}return os;}};#elsestruct Timers {struct Dummy {void start() const {}void add() const {}};Dummy dummy;const Dummy& operator[](const std::string& str) { return dummy; }friend ostream& operator<<(ostream& os, const Timers& timers) { return os; }};#endifTimers global_timers;enum Dir {// y-1, y+1, x-1, x+1kU,kD,kL,kR};Dir RightDir(const Dir dir) {constexpr Dir kRightDirs[4] = {kR, kL, kU, kD};return kRightDirs[dir];}Dir InvDir(const Dir dir) {constexpr Dir kInvDirs[4] = {kD, kU, kR, kL};return kInvDirs[dir];}struct Pos {int idx_;Pos() {}explicit Pos(const int _idx) : idx_(_idx) {}Pos(int _x, int _y) : idx_(_y * N + _x) { assert(N > 0); }int X() const { return pos_2_x[*this]; }int Y() const { return pos_2_y[*this]; }int Idx() const { return idx_; }operator int() const { return Idx(); }operator size_t() const { return Idx(); }const vector<Pos>& Adj() const { return adj_poses[*this]; }const vector<Dir>& AdjDirs() const { return adj_dirs[*this]; }int Manhattan(const Pos& other) const {return abs(X() - other.X()) + abs(Y() - other.Y());}int Euclid2(const Pos& other) const {const int dx = X() - other.X();const int dy = Y() - other.Y();return dx * dx + dy * dy;}bool Move(const Dir dir) {if (move_to[dir][*this].IsDummy()) {return false;} else {*this = move_to[dir][*this];return true;}}template <typename ID>bool IsConnectedAfterRemoving(const vector<ID>& ids) const {// 自身を削除してもids[p]の連結性が維持されるか3x3を見て判定bitset<8> bs = 0;int adj_count = 0;int i = -1;const auto& p = *this;const int base_id = ids[p];for (const auto adj : p.Adj()) {i++;if (ids[adj] == base_id) {adj_count++;bs[i] = true;}}if (adj_count <= 1) return true;i = 3;for (const auto adjadj : adjadjs_check_remove[p]) {i++;bs[i] = ids[adjadj] == base_id;}return can_remove_bses[p][bs.to_ulong()];}bool operator<(const Pos& other) const { return this->Idx() < other.Idx(); }bool operator==(const Pos& other) const { return this->Idx() == other.Idx(); }bool operator!=(const Pos& other) const { return this->Idx() != other.Idx(); }friend ostream& operator<<(ostream& os, const Pos& pos) {os << pos.X() << " " << pos.Y();return os;}bool IsDummy() const { return this->idx_ < 0; }static Pos Dummy() {Pos p;p.idx_ = -1;return p;}static Pos TryCreate(const int x, const int y) {if (y < 0 || y >= N || x < 0 || x >= N) {return Pos::Dummy();} else {return Pos(x, y);}}static void StaticInit(const int n) {N = n;N2 = N * N;N4 = N2 * N2;adj_poses = vector<vector<Pos>>(N2);adj_dirs = vector<vector<Dir>>(N2);move_to = vector<vector<Pos>>(4, vector<Pos>(N2, Pos::Dummy()));pos_2_y.resize(N2);pos_2_x.resize(N2);rep(y, N) {rep(x, N) {const Pos p{x, y};all_poses.push_back(p);pos_2_y[p] = y;pos_2_x[p] = x;for (int dy = -1; dy <= 1; ++dy) {for (int dx = -1; dx <= 1; ++dx) {if (abs(dy) + abs(dx) != 1) continue;const int adj_y = y + dy;const int adj_x = x + dx;if (adj_y < 0 || adj_y >= N) continue;if (adj_x < 0 || adj_x >= N) continue;adj_poses[p].emplace_back(adj_x, adj_y);Dir dir;if (dy == -1) {dir = kU;} else if (dy == 1) {dir = kD;} else if (dx == -1) {dir = kL;} else if (dx == 1) {dir = kR;} else {assert(false);}move_to[dir][p] = {adj_x, adj_y};adj_dirs[p].emplace_back(dir);}}}}all_poses.shrink_to_fit();if (N * N * 256 <= 1e7) {can_remove_bses.resize(N2);adjadjs_check_remove.resize(N2);rep(idx, N * N) {const Pos p(idx);set<Pos> S;for (const auto adj : p.Adj()) {for (const auto adjadj : adj.Adj()) {if (adjadj == p) continue;if (S.count(adjadj) > 0) {adjadjs_check_remove[p].push_back(adjadj);} else {S.insert(adjadj);}}}assert(adjadjs_check_remove[p].size() <= 4);rep(bit, 256) {// adj0, adj1, ..., adjadj0, adjdadj1, ... を詰めずに並べるbitset<8> bs(bit);set<Pos> adjs, adjadjs;rep(j, p.Adj().size()) {if (bs[j]) {adjs.insert(p.Adj()[j]);}}rep(j, adjadjs_check_remove[p].size()) {const auto adjadj = adjadjs_check_remove[p][j];if (bs[j + 4]) {int count = 0;for (const auto adjadjadj : adjadj.Adj()) {count += adjs.count(adjadjadj);}if (count >= 2) {adjadjs.insert(adjadj);}}}can_remove_bses[p][bs.to_ulong()] =((int)adjadjs.size() >= (int)adjs.size() - 1);}}}}static int N, N2, N4;static vector<Pos> all_poses;static vector<vector<Pos>> adj_poses;static vector<vector<Dir>> adj_dirs;static vector<vector<Pos>> move_to;static vector<int> pos_2_x, pos_2_y;// 2^8のbit列を受け取って削除可能かを返す// adj_poses[0], ..., adj_poses[3], adjadjs_check_remove[0], ...,// adjadjs_check_remove[3]// の順に詰めずに並べること 左が上位桁。static vector<bitset<256>> can_remove_bses;static vector<vector<Pos>> adjadjs_check_remove;};vector<Pos> Pos::all_poses;vector<vector<Pos>> Pos::adj_poses;vector<vector<Dir>> Pos::adj_dirs;vector<vector<Pos>> Pos::move_to;vector<int> Pos::pos_2_x, Pos::pos_2_y;int Pos::N, Pos::N2, Pos::N4;vector<bitset<256>> Pos::can_remove_bses;vector<vector<Pos>> Pos::adjadjs_check_remove;/* start */using BS = bitset<50 * 50>;using ShopBS = bitset<128>;Timer global_timer;const int N = 50, M = 20, PDelta = -20;const char kEmpty = '.';const char kBlock = '#';const char kShop = '@';vector<char> A;struct Bomb {int C;int L;vector<Pos> ps;};vector<Bomb> bombs;struct Explosion {int id;Pos p;bool operator<(const Explosion& other) const {if (id != other.id) {return id < other.id;}return p.Idx() < other.p.Idx();}};vector<Pos> shops;ShopBS all_shop_bs;BS input_blocks;vector<Explosion> all_explosions;vector<vector<Explosion>> pos2explosions;vector<vector<BS>> _bomb_id2pos2bs;const BS& BombId2Pos2BS(const int bomb_id, const Pos p) {return _bomb_id2pos2bs[bomb_id][p];}void InitBombId2Pos2BS() {// 破壊するなら0_bomb_id2pos2bs.resize(M, vector<BS>(N * N, 0));rep(bomb_id, M) {rep(idx, N * N) {const Pos base_p(idx);_bomb_id2pos2bs[bomb_id][base_p] = ~(BS{0});for (const auto delta : bombs[bomb_id].ps) {const Pos p = Pos::TryCreate(base_p.X() + delta.X() + PDelta,base_p.Y() + delta.Y() + PDelta);if (p.IsDummy()) continue;_bomb_id2pos2bs[bomb_id][base_p][p] = false;}}}}vector<vector<ShopBS>> _bomb_id2pos2shop_bs;const ShopBS& BombId2Pos2ShopBS(const int bomb_id, const Pos p) {return _bomb_id2pos2shop_bs[bomb_id][p];}void InitBombId2Pos2ShopBS() {// 破壊するなら0_bomb_id2pos2shop_bs.assign(M, vector<ShopBS>(N * N, ~(ShopBS{0})));rep(bomb_id, M) {rep(idx, N * N) {const Pos base_p(idx);const auto bs = BombId2Pos2BS(bomb_id, base_p);rep(shop_id, shops.size()) {if (!bs[shops[shop_id]]) {// 破壊対象_bomb_id2pos2shop_bs[bomb_id][base_p][shop_id] = false;}}}}}double EvalExplosion(const Explosion& exp) {// 大きいほうが嬉しいreturn BombId2Pos2BS(exp.id, exp.p).count() / bombs[exp.id].C;}struct Action {Pos p = Pos::Dummy();int buy_bomb = -1;int use_bomb = -1;static Action CreateMove(const Pos p) {Action action;action.p = p;return action;}static Action CreateBuy(const int id) {Action action;action.buy_bomb = id;return action;}static Action CreateUse(const int id) {Action action;action.use_bomb = id;return action;}friend ostream& operator<<(ostream& os, const vector<Action>& actions) {stringstream ss;int command_count = 0;Pos current_pos = Pos(0, 0);int move_cost = 0;int buy_cost = 0;int bomb_count = 0;BS remain_blocks = input_blocks;for (const auto action : actions) {const Pos p = action.p;if (!p.IsDummy()) {while (current_pos != p) {ss << "\n";command_count++;ss << "1 ";if (current_pos.Y() != p.Y()) {if (current_pos.Y() < p.Y()) {ss << "D";current_pos.Move(kD);} else {ss << "U";current_pos.Move(kU);}} else {if (current_pos.X() < p.X()) {ss << "R";current_pos.Move(kR);} else {ss << "L";current_pos.Move(kL);}}const int coef = remain_blocks[current_pos] ? 2 : 1;move_cost += (bomb_count + 1) * (bomb_count + 1) * coef;}} else if (action.buy_bomb != -1) {command_count++;bomb_count++;ss << "\n";ss << "2 " << action.buy_bomb + 1;buy_cost += bombs[action.buy_bomb].C;} else {command_count++;bomb_count--;ss << "\n";ss << "3 " << action.use_bomb + 1;remain_blocks &= BombId2Pos2BS(action.use_bomb, current_pos);}}os << command_count;os << ss.str();cerr << "move: " << move_cost << " "<< "buy: " << buy_cost << endl;cerr << "score: " << (int)(1e12 / (1e4 + move_cost + buy_cost)) << endl;return os;}};struct Output {static void StaticInit(istream& is) {global_timer.start();Pos::StaticInit(N);int _;is >> _ >> _;input_blocks = 0;A.resize(N * N);all_shop_bs = 0;rep(i, N) {string s;is >> s;rep(j, N) {const Pos p(j, i);A[p] = s[j];if (s[j] == kShop) {all_shop_bs[(int)shops.size()] = true;shops.push_back(p);}if (s[j] != kEmpty) {input_blocks[p] = true;}}}shops.shrink_to_fit();rep(t, M) {int C, L;is >> C >> L;vector<Pos> ps;rep(i, L) {int y, x;is >> y >> x;Pos p{x - PDelta, y - PDelta};ps.push_back(p);}bombs.push_back(Bomb{C, L, ps});}bombs.shrink_to_fit();InitBombId2Pos2BS();InitBombId2Pos2ShopBS();all_explosions.clear();rep(bomb_id, M) {rep(idx, N * N) {const Pos p(idx);all_explosions.push_back(Explosion{bomb_id, p});}}sort(ALL(all_explosions), [&](const auto& l, const auto& r) {return EvalExplosion(l) > EvalExplosion(r);});// const int kCount = N * N * 50;// if ((int)all_explosions.size() > kCount) {// all_explosions.resize(kCount);// }all_explosions.shrink_to_fit();pos2explosions.clear();pos2explosions.resize(N * N);for (const auto& exp : all_explosions) {const auto bs = BombId2Pos2BS(exp.id, exp.p);rep(idx, N * N) {const Pos p(idx);if (bs[p]) continue;// constexpr int kCount = 100;// if ((int)pos2explosions[idx].size() >= kCount) continue;pos2explosions[idx].push_back(exp);}}}friend ostream& operator<<(ostream& os, const Output& output) { return os; }};/* start */vector<double> PARAMS = {100.0, 1.0};/* start */struct ExplosionSolution {set<Explosion> S;BS blocks;ShopBS remain_shops;Explosion last_explosion;int buy_cost_sum = 0;ExplosionSolution() : blocks(input_blocks), remain_shops(0) {rep(i, shops.size()) { remain_shops[i] = true; }}int CountBlock() const { return blocks.count(); }int CountRemainShop() const { return remain_shops.count(); }int CountDestroy(const Explosion& exp) const {return (blocks & ~BombId2Pos2BS(exp.id, exp.p)).count();}void Add(Explosion exp) {if (S.count(exp)) return;S.insert(exp);blocks &= BombId2Pos2BS(exp.id, exp.p);remain_shops &= BombId2Pos2ShopBS(exp.id, exp.p);last_explosion = exp;buy_cost_sum += bombs[exp.id].C;}};class BombSolver {public:BombSolver() {}ExplosionSolution Zatsu() {ExplosionSolution sol;while (true) {auto next_best_sol = sol;double min_eval = INF;int start_idx = rand(0, N * N);int target_idx = sol.blocks._Find_next(start_idx);while (target_idx < N * N && A[target_idx] == '@') {target_idx = sol.blocks._Find_next(target_idx);}if (target_idx == N * N) {target_idx = sol.blocks._Find_first();while (target_idx < N * N && A[target_idx] == '@') {target_idx = sol.blocks._Find_next(target_idx);}}if (target_idx == N * N) {target_idx = sol.blocks._Find_first();}for (const auto& exp : pos2explosions[target_idx]) {auto next_sol = sol;next_sol.Add(exp);const int diff_count_block = sol.CountBlock() - next_sol.CountBlock();if (diff_count_block == 0) continue;if (next_sol.CountBlock() > 0 && next_sol.CountRemainShop() == 0)continue;// 1ブロックあたりのコストdouble eval = bombs[exp.id].C / diff_count_block;if (eval < min_eval) {min_eval = eval;next_best_sol = next_sol;}}if (min_eval == INF) continue;if (next_best_sol.CountBlock() == 0) return next_best_sol;sol = next_best_sol;}assert(false);}vector<Explosion> Solve() {auto best_sol = Zatsu();int g = 0;while (global_timer.ms() < 2000) {g++;auto sol = Zatsu();if (sol.buy_cost_sum < best_sol.buy_cost_sum) {best_sol = sol;}}cerr << "[first] g:" << g << endl;best_sol.S.erase(best_sol.last_explosion);auto ret_vec = vector<Explosion>(ALL(best_sol.S));ret_vec.push_back(best_sol.last_explosion);return ret_vec;}private:};/* start */// NBD = neighborhoodtemplate <class Solution, class NBDGenerator>struct SimulatedAnnealing {public:SimulatedAnnealing(double end_time, double start_temp, double end_temp): end_time_(end_time * 1000), // nsinv_time_(1.0 / end_time_),cur_time_(0.0),start_temp_(start_temp),end_temp_(end_temp),diff_temp_(end_temp_ / start_temp_),cur_temp_(start_temp) {assert(start_temp >= end_temp);timer_.start();}Solution run(const Solution& initial_sol, NBDGenerator& nbd_generator) {Solution sol(initial_sol);int acc = 0;int g = 0;for (;; ++g) {if ((g & 0xff) == 0) {#ifdef SA_MAX_Gif (g >= SA_MAX_G) {break;}#endifUpdateTime();UpdateTemp();if (cur_time_ > end_time_) {break;}}const auto nbd = nbd_generator.Generate(&sol, g, cur_time_ * inv_time_);constexpr int mod = 1'000'000'000;const int r = rand(0, mod);if (static_cast<double>(r) / mod < exp(-nbd->Diff() / cur_temp_)) {acc++;nbd->Update(&sol);} else {nbd->Restore(&sol);}}cerr << "g,acc: " << g << " " << acc << endl;return sol;}private:double end_time_, inv_time_, cur_time_;double start_temp_, end_temp_, diff_temp_, cur_temp_;Timer timer_;void UpdateTime() { cur_time_ = timer_.ns(); }void UpdateTemp() {cur_temp_ = start_temp_ * pow(diff_temp_, cur_time_ * inv_time_);// cur_temp_ = max(0.0, start_temp_ - cur_time_ * diff_temp_ * inv_time_);}};/*実装手順0. Output::StaticInit(istream&)を実装1. Solutionの初期解生成を書く2. Solutionに対する操作とEvalの更新を書く3. Evalの初期値計算を書く4. Eval::Sum()とSolution::Score()を書く5. 近傍操作と復元操作を書く6. 近傍の各確率を調整*/struct Eval {// 最小化問題とすることint dist_sum = 0;int no_shop_count = 0;double Sum() const { return (double)dist_sum + (double)no_shop_count * INF; }};struct Solution {// 爆弾を置く順番// 購入は最寄りの店から一つずつ貪欲にvector<int> order;vector<Action> actions;Eval eval;static vector<Explosion> all_explosions;static void InitAllExplosions(const vector<Explosion>& explosions) {all_explosions = explosions;}Solution() : order(all_explosions.size()) {assert((int)all_explosions.size() > 0);std::iota(ALL(order), 0);InitEval(false);}void InitEval(const bool update_action) {eval = Eval();actions.clear();ShopBS remain_shops = all_shop_bs;Pos current_pos = Pos(0, 0);for (const int exp_idx : order) {const auto& exp = all_explosions[exp_idx];const auto& explode_shop = BombId2Pos2ShopBS(exp.id, exp.p);// 残っている店のうち最も近いところ// TODO: 高速化int best_shop_id = -1;int min_manhattan = INF;rep(shop_id, shops.size()) {if (!remain_shops[shop_id]) continue;const auto shop_pos = shops[shop_id];const int manhattan =current_pos.Manhattan(shop_pos) + shop_pos.Manhattan(exp.p);if (manhattan < min_manhattan) {min_manhattan = manhattan;best_shop_id = shop_id;}}if (best_shop_id == -1) {eval.no_shop_count += 1;continue;}if (update_action) {// 店に移動、購入、犯行現場に移動、爆破actions.push_back(Action::CreateMove(shops[best_shop_id]));actions.push_back(Action::CreateBuy(exp.id));actions.push_back(Action::CreateMove(exp.p));actions.push_back(Action::CreateUse(exp.id));}remain_shops &= explode_shop;eval.dist_sum += min_manhattan;current_pos = exp.p;}}static Solution CreateInitialSol() {Solution sol;sol.InitEval(false);return sol;}double Evaluate() const { return eval.Sum(); }double Score() const {// 最大化問題とすることreturn -Evaluate();}friend ostream& operator<<(ostream& os, const Solution& sol) { return os; }};vector<Explosion> Solution::all_explosions;struct NBD {double Diff() const { return diff; }void Update(Solution*) const {};virtual void Restore(Solution*) const = 0;double diff;};struct NBD1 : public NBD {NBD1() {}NBD1(Solution* const sol) {diff = -sol->Evaluate();//順番swapwhile (true) {idx = rand(0, (int)sol->order.size() - 2);swap(sol->order[idx], sol->order[idx + 1]);sol->InitEval(false);diff += sol->Evaluate();return;}}void Restore(Solution* sol) const override {swap(sol->order[idx], sol->order[idx + 1]);sol->InitEval(false);}int idx = 0;};struct NBD2 : public NBD {NBD2() {}NBD2(Solution* const sol) {diff = -sol->Evaluate();//順番swapwhile (true) {idx = rand(0, (int)sol->order.size() - 2);idx1 = rand(0, (int)sol->order.size() - 2);if (idx == idx1) continue;swap(sol->order[idx], sol->order[idx1]);sol->InitEval(false);diff += sol->Evaluate();return;}}void Restore(Solution* sol) const override {swap(sol->order[idx], sol->order[idx1]);sol->InitEval(false);}int idx = 0;int idx1 = 0;};struct NBDGenerator {NBD* Generate(Solution* const sol, const int g, const double progress) {if (sol->Score() > best_sol.Score()) {best_sol = *sol;}const int random = rand(0, 100);if (random < 80) {nbd1_ = NBD1(sol);return &nbd1_;} else if (random < 100) {nbd2_ = NBD2(sol);return &nbd2_;} else {assert(false);}}const Solution& GetBestSol() const { return best_sol; }private:NBD1 nbd1_;NBD2 nbd2_;Solution best_sol;};vector<Action> SARun() {Solution first_sol = Solution::CreateInitialSol();NBDGenerator gen;SimulatedAnnealing<Solution, NBDGenerator> SA(2950 - global_timer.ms(),PARAMS[0], PARAMS[1]);const auto final_sol = SA.run(first_sol, gen);auto best_sol = gen.GetBestSol();cerr << "score: " << best_sol.Score() << endl;// return best_sol;best_sol.InitEval(true);// cerr << first_sol.actions.size() << " " << Solution::all_explosions.size()// << endl;// const auto bs = BombId2Pos2BS(0, Pos(21, 16));// rep(y, N) {// rep(x, N) { cerr << bs[Pos(x, y)]; }// cerr << endl;// }return best_sol.actions;}/* start */class PlanSolver {public:PlanSolver() {}void Solve(const vector<Explosion>& explosions) {Solution::InitAllExplosions(explosions);const auto actions = SARun();cout << actions << endl;}private:};/* start */class Solver {public:Solver() {}void Solve() {BombSolver solver;const auto sol = solver.Solve();PlanSolver solver2;solver2.Solve(sol);return;}private:};int main(int argc, char* argv[]) {fast_io;if (argc >= 2) {int idx = 0;for (int i = 1; i < argc; ++i) {PARAMS[idx++] = std::stod(argv[i]);}}Timer timer;timer.start();Output::StaticInit(cin);Solver solver;solver.Solve();return 0;}