結果

問題 No.5019 Hakai Project
ユーザー Jiro_tech15Jiro_tech15
提出日時 2023-11-19 19:08:41
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 2,805 ms / 3,000 ms
コード長 24,579 bytes
コンパイル時間 4,453 ms
コンパイル使用メモリ 218,212 KB
実行使用メモリ 20,588 KB
スコア 1,719,026,565
最終ジャッジ日時 2023-11-19 19:11:16
合計ジャッジ時間 153,894 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge12
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2,804 ms
20,584 KB
testcase_01 AC 2,803 ms
20,584 KB
testcase_02 AC 2,803 ms
20,588 KB
testcase_03 AC 2,804 ms
20,584 KB
testcase_04 AC 2,804 ms
20,584 KB
testcase_05 AC 2,804 ms
20,588 KB
testcase_06 AC 2,803 ms
20,580 KB
testcase_07 AC 2,805 ms
20,584 KB
testcase_08 AC 2,803 ms
20,584 KB
testcase_09 AC 2,804 ms
20,584 KB
testcase_10 AC 2,803 ms
20,584 KB
testcase_11 AC 2,803 ms
20,584 KB
testcase_12 AC 2,804 ms
20,584 KB
testcase_13 AC 2,804 ms
20,584 KB
testcase_14 AC 2,804 ms
20,588 KB
testcase_15 AC 2,804 ms
20,580 KB
testcase_16 AC 2,804 ms
20,584 KB
testcase_17 AC 2,804 ms
20,588 KB
testcase_18 AC 2,804 ms
20,580 KB
testcase_19 AC 2,802 ms
20,584 KB
testcase_20 AC 2,805 ms
20,584 KB
testcase_21 AC 2,804 ms
20,584 KB
testcase_22 AC 2,805 ms
20,588 KB
testcase_23 AC 2,803 ms
20,584 KB
testcase_24 AC 2,803 ms
20,584 KB
testcase_25 AC 2,804 ms
20,584 KB
testcase_26 AC 2,804 ms
20,584 KB
testcase_27 AC 2,803 ms
20,588 KB
testcase_28 AC 2,804 ms
20,584 KB
testcase_29 AC 2,803 ms
20,584 KB
testcase_30 AC 2,804 ms
20,580 KB
testcase_31 AC 2,805 ms
20,580 KB
testcase_32 AC 2,805 ms
20,584 KB
testcase_33 AC 2,804 ms
20,584 KB
testcase_34 AC 2,804 ms
20,580 KB
testcase_35 AC 2,804 ms
20,584 KB
testcase_36 AC 2,804 ms
20,580 KB
testcase_37 AC 2,804 ms
20,580 KB
testcase_38 AC 2,805 ms
20,580 KB
testcase_39 AC 2,803 ms
20,588 KB
testcase_40 AC 2,804 ms
20,580 KB
testcase_41 AC 2,803 ms
20,584 KB
testcase_42 AC 2,803 ms
20,584 KB
testcase_43 AC 2,804 ms
20,588 KB
testcase_44 AC 2,803 ms
20,588 KB
testcase_45 AC 2,804 ms
20,584 KB
testcase_46 AC 2,804 ms
20,588 KB
testcase_47 AC 2,803 ms
20,584 KB
testcase_48 AC 2,804 ms
20,588 KB
testcase_49 AC 2,804 ms
20,588 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
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;
      |                 ^~~

ソースコード

diff # 


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>
#endif

using 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));                              \
  }
#endif

long 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 LOCAL
struct 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;
  }
};
#else
struct 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; }
};
#endif

Timers global_timers;




enum Dir {
  // y-1, y+1, x-1, x+1
  kU,
  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;
};

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<Bomb> bombs;
vector<Pos> shops;
ShopBS all_shop_bs;
BS input_blocks;

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;
        }
      }
    }
  }
}

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;
    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();
  }
  friend ostream& operator<<(ostream& os, const Output& output) { return os; }
};



/* start */

vector<double> PARAMS = {1.0, 0.1};





/* 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;
      rep(t, 10) {
        Explosion exp{rand(0, M), rand_vec(Pos::all_poses)};
        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() < 2800) {
      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 = neighborhood
template <class Solution, class NBDGenerator>
struct SimulatedAnnealing {
 public:
  SimulatedAnnealing(double end_time, double start_temp, double end_temp)
      : end_time_(end_time * 1000),  // ns
        inv_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_G
        if (g >= SA_MAX_G) {
          break;
        }
#endif
        UpdateTime();
        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;
        cerr << "hoge" << endl;
        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(); }
  void Restore(Solution* sol) const override {}
};

struct NBD2 : public NBD {
  NBD2() {}
  NBD2(Solution* const sol) { diff = -sol->Evaluate(); }
  void Restore(Solution* sol) const override {}
};

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 < 50) {
      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(1950 - global_timer.ms(),
  //                                               PARAMS[0], PARAMS[1]);
  // const auto final_sol = SA.run(first_sol, gen);
  // const auto best_sol = gen.GetBestSol();
  // cerr << "score: " << best_sol.Score() << endl;
  // cout << best_sol << endl;

  // return best_sol;
  first_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 first_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;
}
0