結果

問題 No.5016 Worst Mayor
ユーザー maimai
提出日時 2023-04-29 16:58:51
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 21,482 bytes
コンパイル時間 4,816 ms
コンパイル使用メモリ 262,924 KB
実行使用メモリ 25,956 KB
スコア 0
最終ジャッジ日時 2023-04-29 17:00:58
合計ジャッジ時間 12,001 ms
ジャッジサーバーID
(参考情報)
judge16 / judge11
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 TLE -
testcase_01 -- -
testcase_02 -- -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
testcase_37 -- -
testcase_38 -- -
testcase_39 -- -
testcase_40 -- -
testcase_41 -- -
testcase_42 -- -
testcase_43 -- -
testcase_44 -- -
testcase_45 -- -
testcase_46 -- -
testcase_47 -- -
testcase_48 -- -
testcase_49 -- -
権限があれば一括ダウンロードができます

ソースコード

diff #

#pragma GCC optimize("O3")
#include <bits/stdc++.h>

// clang-format off
using namespace std;
using ll = long long int;

#define all(v) (v).begin(),(v).end()
#define repeat(cnt,l) for(typename remove_const<typename remove_reference<decltype(l)>::type>::type cnt={};(cnt)<(l);++(cnt))
#define rrepeat(cnt,l) for(auto cnt=(l)-1;0<=(cnt);--(cnt))
#define iterate(cnt,b,e) for(auto cnt=(b);(cnt)!=(e);++(cnt))
#define upto(cnt,b,e,step) for(auto cnt=(b);(cnt)<=(e);(cnt)+=(step))
#define downto(cnt,b,e,step) for(auto cnt=(b);(e)<=(cnt);(cnt)-=(step))
const long long MD = 998244353; const long double PI = 3.1415926535897932384626433832795L;
template<typename T1, typename T2> inline ostream& operator <<(ostream &o, const pair<T1, T2> p) { o << '(' << p.first << ':' << p.second << ')'; return o; }
template<typename T> inline T& chmax(T& to, const T& val) { return to = max(to, val); }
template<typename T> inline T& chmin(T& to, const T& val) { return to = min(to, val); }
void bye(string s, int code = 0) { cout << s << endl; exit(code); }
mt19937_64 randdev(8901016);
template<typename T, typename Random = decltype(randdev), typename enable_if<is_integral<T>::value>::type* = nullptr>
inline T rand(T l, T h, Random& rand = randdev) { return uniform_int_distribution<T>(l, h)(rand); }
template<typename T, typename Random = decltype(randdev), typename enable_if<is_floating_point<T>::value>::type* = nullptr>
inline T rand(T l, T h, Random& rand = randdev) { return uniform_real_distribution<T>(l, h)(rand); }template<typename T>
static ostream& operator<<(ostream& o, const std::vector<T>& v) {
  o << "[ "; for(const auto& e : v) o<<e<<' '; return o << ']';
}

template <typename I> struct MyRangeFormat{ I b,e; MyRangeFormat(I _b, I _e):b(_b),e(_e){} };
template<typename I> static ostream& operator<<(ostream& o, const MyRangeFormat<I>& f) {
  o << "[ "; iterate(i,f.b,f.e) o<<*i<<' '; return o << ']';
}
template <typename I> struct MyMatrixFormat{
  const I& p; long long n, m;
  MyMatrixFormat(const I& _p, long long _n, long long _m):p(_p),n(_n),m(_m){}
};
template<typename I> static ostream& operator<<(ostream& o, const MyMatrixFormat<I>& f) {
  o<<'\n'; repeat(i,(f.n)) { repeat(j,f.m) o<<f.p[i][j]<<' '; o<<'\n'; }
  return o;
}
struct LOG_t { ~LOG_t() { clog << endl; } };
#define LOG (LOG_t(),clog<<'L'<<__LINE__<<": ")
#define FMTA(m,w) (MyRangeFormat<decltype(m+0)>(m,m+w))
#define FMTR(b,e) (MyRangeFormat<decltype(e)>(b,e))
#define FMTV(v) FMTR(v.begin(),v.end())
#define FMTM(m,h,w) (MyMatrixFormat<decltype(m+0)>(m,h,w))

#if defined(_WIN32) || defined(_WIN64)
#define getc_x _getc_nolock
#define putc_x _putc_nolock
#elif defined(__GNUC__)
#define getc_x getc_unlocked
#define putc_x putc_unlocked
#else
#define getc_x getc
#define putc_x putc
#endif
class MaiScanner {
  FILE* fp_;
  constexpr bool isvisiblechar(char c) noexcept { return (0x21<=(c)&&(c)<=0x7E); }
public:
  inline MaiScanner(FILE* fp):fp_(fp){}
  template<typename T> void input_integer(T& var) noexcept {
    var = 0; T sign = 1;
    int cc = getc_x(fp_);
    for (; cc < '0' || '9' < cc; cc = getc_x(fp_))
      if (cc == '-') sign = -1;
    for (; '0' <= cc && cc <= '9'; cc = getc_x(fp_))
      var = (var << 3) + (var << 1) + cc - '0';
    var = var * sign;
  }
  inline int c() noexcept { return getc_x(fp_); }
  template<typename T, typename enable_if<is_integral<T>::value, nullptr_t>::type = nullptr>
  inline MaiScanner& operator>>(T& var) noexcept { input_integer<T>(var); return *this; }
  inline MaiScanner& operator>>(string& var) {
    int cc = getc_x(fp_);
    for (; !isvisiblechar(cc); cc = getc_x(fp_));
    for (; isvisiblechar(cc); cc = getc_x(fp_))
      var.push_back(cc);
    return *this;
  }
  template<typename IT> inline void in(IT begin, IT end) { for (auto it = begin; it != end; ++it) *this >> *it; }
};
class MaiPrinter {
  FILE* fp_;
public:
  inline MaiPrinter(FILE* fp):fp_(fp){}
  template<typename T>
  void output_integer(T var) noexcept {
    if (var == 0) { putc_x('0', fp_); return; }
    if (var < 0)
      putc_x('-', fp_),
      var = -var;
    char stack[32]; int stack_p = 0;
    while (var)
      stack[stack_p++] = '0' + (var % 10),
      var /= 10;
    while (stack_p)
      putc_x(stack[--stack_p], fp_);
  }
  inline MaiPrinter& operator<<(char c) noexcept { putc_x(c, fp_); return *this; }
  template<typename T, typename enable_if<is_integral<T>::value, nullptr_t>::type = nullptr>
  inline MaiPrinter& operator<<(T var) noexcept { output_integer<T>(var); return *this; }
  inline MaiPrinter& operator<<(const char* str_p) noexcept { while (*str_p) putc_x(*(str_p++), fp_); return *this; }
  inline MaiPrinter& operator<<(const string& str) {
    const char* p = str.c_str();
    const char* l = p + str.size();
    while (p < l) putc_x(*p++, fp_);
    return *this;
  }
  template<typename IT> void join(IT begin, IT end, char sep = ' ') { for (bool b = 0; begin != end; ++begin, b = 1) b ? *this << sep << *begin : *this << *begin; }
};
MaiScanner scanner(stdin);
MaiPrinter printer(stdout);
// clang-format on

template <typename C = std::chrono::milliseconds> class Timer {
  std::chrono::system_clock::time_point tp_;

public:
  static inline auto now() { return std::chrono::system_clock::now(); }
  inline void tic() { tp_ = now(); }
  inline auto toc() const {
    return std::chrono::duration_cast<C>(now() - tp_).count();
  }
  inline Timer() : tp_(now()) {}
};
inline std::ostream &operator<<(std::ostream &o, const Timer<> &t) {
  return o << (long long)t.toc();
}

struct P {
  using T = int;
  T y, x;

  inline explicit P(T _y, T _x) : y(_y), x(_x) {}
  inline P() : y(0), x(0) {}

  inline bool operator==(P p) const { return y == p.y && x == p.x; }
  inline bool operator<(P p) const { return y == p.y ? x < p.x : y < p.y; }
  inline P operator+(P p) const { return P(y + p.y, x + p.x); }
  inline P operator-(P p) const { return P(y - p.y, x - p.x); }
  inline P &operator+=(P p) {
    y += p.y;
    x += p.x;
    return *this;
  }
  inline P &operator-=(P p) {
    y -= p.y;
    x -= p.x;
    return *this;
  }
  inline P &operator*=(T m) {
    y *= m;
    x *= m;
    return *this;
  }
  inline T distM(P p) const { return abs(y - p.y) + abs(x - p.x); }
  inline T distC(P p) const { return max(abs(y - p.y), abs(x - p.x)); }
  template <typename ITR> ITR nearestM(ITR begin, ITR end) const {
    if (begin == end)
      return end;
    T best = distM(*begin);
    ITR besti = begin;
    for (ITR it = begin; ++it, it != end;) {
      T m = distM(*it);
      if (best < m) {
        best = m;
        besti = it;
      }
    }
    return besti;
  }
};
inline ostream &operator<<(ostream &os, P p) {
  os << '(' << p.y << ',' << p.x << ')';
  return os;
}

const P FourMoving[] = {P(-1, 0), P(0, 1), P(1, 0), P(0, -1)};
const P FiveMoving[] = {P(-1, 0), P(0, 1), P(1, 0), P(0, -1), P(0, 0)};
const P EightMoving[] = {P(-1, 0),  P(0, 1),  P(1, 0),  P(0, -1),
                         P(-1, -1), P(-1, 1), P(1, -1), P(1, 1)};

inline P operator*(P::T m, P p) noexcept { return P(m * p.y, m * p.x); }

template <typename T>
// using T = int;
struct F {
  int height, width;
  vector<T> data;

  explicit F(int h, int w) : height(h), width(w), data(h * w) {}
  F() : F(1, 1) {}

  inline bool safe(int y, int x) const {
    return 0 <= y && y < height && 0 <= x && x < width;
  }
  inline bool safe(P p) const {
    return 0 <= p.y && p.y < height && 0 <= p.x && p.x < width;
  }

#if 1
  void assert_safe(int y, int x) const {
    if (!safe(y, x)) {
      clog << "assertion failed: field=" << height << "x" << width
           << ": try=" << y << "," << x << endl;
      assert(safe(y, x));
    }
  }
  inline T &operator()(int y, int x) {
    assert_safe(y, x);
    return data[x + y * width];
  }
  inline T &operator()(P p) {
    assert_safe(p.y, p. x);
    return data[p.x + p.y * width];
  }
  inline T operator()(int y, int x) const {
    assert_safe(y, x);
    return data[x + y * width];
  }
  inline T operator()(P p) const {
    assert_safe(p.y, p.x);
    return data[p.x + p.y * width];
  }
#else
  inline T &operator()(int y, int x) { return data[x + y * width]; }
  inline T &operator()(P p) { return data[p.x + p.y * width]; }
  inline T operator()(int y, int x) const { return data[x + y * width]; }
  inline T operator()(P p) const { return data[p.x + p.y * width]; }
#endif
  inline T getA(int i) const { return data[i]; }
  inline T &getAmut(int i) { return data[i]; }

  inline void fill(T e) { std::fill(data.begin(), data.end(), e); }
  inline void resize(int h, int w) {
    height = h;
    width = w;
    data.resize(h * w);
  }

  void print(ostream &os, int setw_arg = 4) {
    for (int y = 0; y < height; ++y) {
      for (int x = 0; x < width; ++x)
        os << setw(setw_arg) << operator()(y, x) << ' ';
      os << '\n';
    }
  }
};

class Graph2d {
 public:
  using W_T = int;
  int n;
  vector<W_T> matrix;

  explicit Graph2d(int size) : n(size), matrix(size * size){};

  inline int size() const { return n; }
  void resize(int s) {
    n = s;
    matrix.resize(n * n);
  }
  void resize(int s, W_T val) {
    n = s;
    matrix.resize(n * n, val);
  }

  inline W_T& at(int y, int x) { return matrix[y * n + x]; }
  inline W_T& operator()(int y, int x) { return matrix[y * n + x]; }
  inline W_T at(int y, int x) const { return matrix[y * n + x]; }
  inline W_T operator()(int y, int x) const { return matrix[y * n + x]; }

  inline void connect(int u, int v, W_T dist = 1) { at(u, v) = at(v, u) = dist; }
  inline void connect_d(int from, int to, W_T dist = 1) {  // directedEdge u->v
    at(from, to) = dist;
  }
};

void warshall_floyd(Graph2d& g) {
  int i, j, k;
  for (i = 0; i < g.n; i++) {
    for (j = 0; j < g.n; j++) {
      for (k = 0; k < g.n; k++) {
        g(j, k) = std::min(g(j, k), g(j, i) + g(i, k));
      }
    }
  }
}

class CommandChain {
 public:
  using Direction = int;  // 2bit
  struct Node {
    Node() : value(0), len(0) {}
    void push(Direction dir) {
      value |= (uint64_t)(dir & 3) << (uint64_t)len;
      len += 2;
    }
    bool full() const { return len >= 64; }
    void dump(vector<int>& out) const {
      for (uint64_t p = 0; p < uint64_t(len); p += 2)
        out.push_back((value >> p) & 3);
    }
    int last() const { return (value >> uint64_t(len - 2)) & 3; }

    uint64_t value;
    int len = 0;
  };

  static shared_ptr<CommandChain> createEmpty() { return make_shared<CommandChain>(root()); }

  static shared_ptr<CommandChain> pushed(shared_ptr<CommandChain>& me, Direction cmd) {
    // assert(me.get());
    if (me->node_.full()) {
      auto new_chain = make_shared<CommandChain>(me);
      new_chain->node_.push(cmd);
      return new_chain;
    } else {
      auto copied_chain = make_shared<CommandChain>(*me);
      copied_chain->node_.push(cmd);
      return copied_chain;
    }
  }

  int last() const { return node_.last(); }

  void dumpTo(vector<int>& out) const {
    if (prev_.get()) {
      prev_->dumpTo(out);
      // root does not have value
      node_.dump(out);
    }
  }
  vector<int> dump() const {
    vector<int> out;
    dumpTo(out);
    return out;
  }

  // TODO: make private...
  CommandChain(shared_ptr<CommandChain>& prev) : prev_(prev), node_() {}

 private:
  // friend shared_ptr<CommandChain>;
  static shared_ptr<CommandChain>& root() {
    static shared_ptr<CommandChain> e(new CommandChain());
    return e;
  };

  shared_ptr<CommandChain> prev_;
  Node node_;
  CommandChain() : prev_(), node_() {}
};

//

constexpr int N = 14; // N^4 = 38416
constexpr int M = 3000;
constexpr int T = 400;

inline P idx2p(int i) { return P{i / N, i % N}; }
inline int p2idx(P p) { return p.y * N + p.x; }

Timer<> g_timer;

/*
考察
- 愚直に最短距離を計算する場合、warshall-floyd O(N^6) = 7529536 DEKKKA
  - ダイクストラ?|V| = N^2, |E| ~= 2|V| = 2N^2,
- 最短経路は、経路上では遠回りになっている可能性がある。1.0 > 0.223*3
  - 厳密に計算するならズルできません
- 最適な高速道路を追加する順番が存在する。NPかどうかは知らない
  - これを予め計算してFIXすると、コマンドは3つだけになる。

- 平均 0,標準偏差 1 に従う乱数 e p,q ​
なにこれ?正規分布?

*/

struct Problem {

  vector<pair<P, P>> routes_;

  void input() {
    int m, t;
    scanner >> m >> t;
    assert(M == m);
    assert(T == t);
    repeat(i, M) {
      int y1, x1, y2, x2;
      scanner >> y1 >> x1 >> y2 >> x2;
      routes_.emplace_back(P{y1, x1}, P{y2, x2});
    }
  }

  void inputGenerated() {
    routes_.reserve(N * N * N * N);
    repeat(a, N) {
      repeat(b, N) {
        repeat(c, N) {
          repeat(d, N) { routes_.emplace_back(P{a, b}, P{c, d}); }
        }
      }
    }
    shuffle(all(routes_), randdev);
    routes_.resize(M);
    routes_.shrink_to_fit();
  }

  Graph2d calcDistanceWF(const F<int> &field) const {
    Graph2d dist(N * N);
    fill(all(dist.matrix), MD);
    repeat(pi, N * N) {
      const P p = idx2p(pi);
      dist(pi, pi) = 0;
      if (p.y < N - 1) {
        const int c = field(p.y, p.x) & 1 ? 223 : 1000;
        dist(pi, pi + N) = c;
        dist(pi + N, pi) = c;
      }
      if (p.x < N - 1) {
        const int c = field(p.y, p.x) & 2 ? 223 : 1000;
        dist(pi, pi + 1) = c;
        dist(pi + 1, pi) = c;
      }
    }
    warshall_floyd(dist);
    return dist;
  }

  vector<int> calcDistance(const F<int> &field, P start) const {
    vector<int> dist(N * N, MD);
    priority_queue<pair<int, int>> que;
    const int starti = p2idx(start);
    que.emplace(0, starti);
    dist[starti] = 0;
    while (!que.empty()) {
      const int d = -que.top().first;
      const int pi = que.top().second;
      que.pop();
      if (dist[pi] < d)
        continue;
      const P p = idx2p(pi);
      // 事故りそう
      if (p.y > 0) {
        int cost = field(p.y - 1, p.x) & 1 ? 223 : 1000;
        int d2 = d + cost;
        if (dist[pi - N] > d2) {
          dist[pi - N] = d2;
          que.emplace(-d2, pi - N);
        }
      }
      if (p.x > 0) {
        int cost = field(p.y, p.x - 1) & 2 ? 223 : 1000;
        int d2 = d + cost;
        if (dist[pi - 1] > d2) {
          dist[pi - 1] = d2;
          que.emplace(-d2, pi - 1);
        }
      }
      if (p.y < N - 1) {
        int cost = field(p.y, p.x) & 1 ? 223 : 1000;
        int d2 = d + cost;
        if (dist[pi + N] > d2) {
          dist[pi + N] = d2;
          que.emplace(-d2, pi + N);
        }
      }
      if (p.x < N - 1) {
        int cost = field(p.y, p.x) & 2 ? 223 : 1000;
        int d2 = d + cost;
        if (dist[pi + 1] > d2) {
          dist[pi + 1] = d2;
          que.emplace(-d2, pi + 1);
        }
      }
    }
    return dist;
  }
};

// 距離から高速道路の使用数を特定する
vector<int> createTableFromDist2Num() {
  constexpr int h = N * 2 * 1000;
  vector<int> d2n(h, MD);
  d2n[0] = 0;
  repeat(d, h - 223) {
    if (d2n[d] == MD)
      continue;
    if (d + 1000 < h)
      d2n[d + 1000] = d2n[d];
    d2n[d + 223] = d2n[d] + 1;
  }
  return d2n;
}

int dist2NumEdge(int dist) {
  static vector<int> table = createTableFromDist2Num();
  int n = table[dist];
  assert(n < N * N);
  return n;
}

struct CommandBuildHighway {
  int income;
  P pos;
  bool horizontal;
};

struct BeamState {
  ll heuristic_ = numeric_limits<ll>::min();
  ll money_ = 0;
  ll income_ = 0;
  int turn_ = 0;
  int highway_ = 0;
  int man_power_ = 1;

  // int score_ = numeric_limits<int>::min();

  shared_ptr<CommandChain> commands_;

  BeamState() : commands_(CommandChain::createEmpty()) {}

  bool operator<(const BeamState &another) const {
    return heuristic_ < another.heuristic_;
  }

  void updateHeuristic() {
    // TODO:
    heuristic_ = income_; // floor(sqrt(man_power_));
  }

  static BeamState initialState() {
    BeamState next;
    next.money_ = 1000000;
    next.income_ = 0;
    next.turn_ = 0;
    next.highway_ = 0;
    next.man_power_ = 1;
    return next;
  }

  optional<BeamState>
  nextStateHighway(const vector<CommandBuildHighway> &command_bh) {
    // TODO: check next.highway_ < command_bh.size
    if (highway_ + 1 >= command_bh.size())
      return optional<BeamState>();
    ll cost =
        ceil(10000000.0 / sqrt(man_power_)); // floor らしいけど怖いのでceil
    if (money_ < cost)
      return optional<BeamState>();
    BeamState next;
    next.money_ = money_;
    next.income_ = income_;
    next.turn_ = turn_ + 1;
    next.highway_ = highway_;
    next.man_power_ = man_power_;
    // Do
    next.money_ -= cost;
    next.commands_ = CommandChain::pushed(commands_, 1);
    next.highway_ += 1;
    next.income_ = ll(command_bh[next.highway_].income) * 60;
    // receive income
    next.money_ = money_ + next.income_;
    next.updateHeuristic();

    return optional<BeamState>(next);
  }
  BeamState nextStateAddManPower() {
    // TODO: check next.highway_ < command_bh.size
    BeamState next;
    next.money_ = money_;
    next.income_ = income_;
    next.turn_ = turn_ + 1;
    next.highway_ = highway_;
    next.man_power_ = man_power_;
    // Do
    next.commands_ = CommandChain::pushed(commands_, 2);
    next.man_power_ += 1;
    // receive income
    next.money_ = money_ + next.income_;
    next.updateHeuristic();
    return next;
  }
  BeamState nextStateAddMoney() {
    // TODO: check next.highway_ < command_bh.size
    BeamState next;
    next.money_ = money_;
    next.income_ = income_;
    next.turn_ = turn_ + 1;
    next.highway_ = highway_;
    next.man_power_ = man_power_;
    // Do
    next.commands_ = CommandChain::pushed(commands_, 3);
    next.money_ += 50000;
    // receive income
    next.money_ = money_ + next.income_;
    next.updateHeuristic();
    return next;
  }
};

void solve(const Problem &problem) {
  F<vector<P>> problem_routes_mat{N, N};
  for (auto &p : problem.routes_) {
    problem_routes_mat(p.first).push_back(p.second);
  }

  // 高速道路を追加する順番を FIX する
  vector<CommandBuildHighway> command_bh;
  command_bh.push_back(
      CommandBuildHighway{.income = 0, .pos = P{0, 0}, .horizontal = false});

  // よくわからないのでとりあえず中央から選んでいくことにする
  F<int> done{N, N};
  queue<P> que;
  que.emplace(N / 2, N / 2);
  done(N / 2, N / 2) = true;

  F<int> highway{N, N};
  repeat(i, T / 6) {
    P p = que.front();
    que.pop();
    done(p) = true;
    // 次の候補
    for (P v : FourMoving) {
      P p2 = p + v;
      if (done(p2))
        continue;
      done(p2) = true;
      que.emplace(p2);
    }

    highway(p) |= 1;
    int income = 0;
    repeat(y, N) {
      repeat(x, N) {
        auto dist = problem.calcDistance(highway, P{y, x});
        for (P to : problem_routes_mat(y, x)) {
          income += dist2NumEdge(dist[p2idx(to)]);
        }
        //
      }
    }
    command_bh.push_back(
        CommandBuildHighway{.income = income, .pos = p, .horizontal = false});

    highway(p) |= 2;
    income = 0;
    repeat(y, N) {
      repeat(x, N) {
        auto dist = problem.calcDistance(highway, P{y, x});
        for (P to : problem_routes_mat(y, x)) {
          income += dist2NumEdge(dist[p2idx(to)]);
        }
      }
    }
    command_bh.push_back(
        CommandBuildHighway{.income = income, .pos = p, .horizontal = true});
  }

  // コマンドを決める

  BeamState best_state = BeamState::initialState();
  ll best_score = best_state.money_ + T * 50000;

  vector<priority_queue<BeamState>> beam_states(T + 1); // keep buffer
  beam_states[0].push(best_state);

  while (g_timer.toc() < 1500) {
    repeat(turn, T) {
      BeamState top_state = beam_states[turn].top();
      beam_states[turn].pop();

      {
        ll score = top_state.money_ + (T - turn) * 50000;
        if (best_score < score) {
          best_state = top_state;
          best_score = score;
        }
      }

      auto may_next_state1 = top_state.nextStateHighway(command_bh);
      if (may_next_state1.has_value())
        beam_states[turn + 1].push(move(*may_next_state1));
      BeamState next_state2 = top_state.nextStateAddManPower();
      beam_states[turn + 1].push(move(next_state2));
      BeamState next_state3 = top_state.nextStateAddMoney();
      beam_states[turn + 1].push(move(next_state3));
    }
    while (!beam_states[T].empty()) {
      auto state = beam_states[T].top();
      beam_states[T].pop();
      if (best_score < state.money_) {
        best_state = state;
        best_score = state.money_;
      }
    }
  }

  {
    auto commands = best_state.commands_->dump();
    int turn = 0;
    int cnt_highway = 0;
    for (int cmd : commands) {
      if (cmd == 1) {
        cnt_highway += 1;
        auto c = command_bh[cnt_highway];
        if (c.horizontal) {
          cout << "1 " << c.pos.y << " " << c.pos.x << " " << c.pos.y << " "
               << c.pos.x + 1 << endl;
        } else {
          cout << "1 " << c.pos.y << " " << c.pos.x << " " << c.pos.y + 1 << " "
               << c.pos.x << endl;
        }
        int u, v;
        cin >> u >> v;
      } else {
        cout << cmd << endl;
        int u, v;
        cin >> u >> v;
      }
      turn += 1;
    }
    while (turn < T) {
      cout << "3" << endl;
      int u, v;
      cin >> u >> v;
      turn += 1;
    }
  }
}

//

int main(int argc, char **argv) {

  Problem problem;
  // problem.inputGenerated();
  problem.input();

  solve(problem);

  return 0;
}
0