#pragma GCC optimize("O3") #include // 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::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 inline ostream& operator <<(ostream &o, const pair p) { o << '(' << p.first << ':' << p.second << ')'; return o; } template inline T& chmax(T& to, const T& val) { return to = max(to, val); } template 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::value>::type* = nullptr> inline T rand(T l, T h, Random& rand = randdev) { return uniform_int_distribution(l, h)(rand); } template::value>::type* = nullptr> inline T rand(T l, T h, Random& rand = randdev) { return uniform_real_distribution(l, h)(rand); }template static ostream& operator<<(ostream& o, const std::vector& v) { o << "[ "; for(const auto& e : v) o< struct MyRangeFormat{ I b,e; MyRangeFormat(I _b, I _e):b(_b),e(_e){} }; template static ostream& operator<<(ostream& o, const MyRangeFormat& f) { o << "[ "; iterate(i,f.b,f.e) o<<*i<<' '; return o << ']'; } template 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 static ostream& operator<<(ostream& o, const MyMatrixFormat& f) { o<<'\n'; repeat(i,(f.n)) { repeat(j,f.m) o<(m,m+w)) #define FMTR(b,e) (MyRangeFormat(b,e)) #define FMTV(v) FMTR(v.begin(),v.end()) #define FMTM(m,h,w) (MyMatrixFormat(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 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::value, nullptr_t>::type = nullptr> inline MaiScanner& operator>>(T& var) noexcept { input_integer(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 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 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::value, nullptr_t>::type = nullptr> inline MaiPrinter& operator<<(T var) noexcept { output_integer(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 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 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(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 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 // using T = int; struct F { int height, width; vector 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 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& 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 createEmpty() { return make_shared(root()); } static shared_ptr pushed(shared_ptr& me, Direction cmd) { // assert(me.get()); if (me->node_.full()) { auto new_chain = make_shared(me); new_chain->node_.push(cmd); return new_chain; } else { auto copied_chain = make_shared(*me); copied_chain->node_.push(cmd); return copied_chain; } } int last() const { return node_.last(); } void dumpTo(vector& out) const { if (prev_.get()) { prev_->dumpTo(out); // root does not have value node_.dump(out); } } vector dump() const { vector out; dumpTo(out); return out; } // TODO: make private... CommandChain(shared_ptr& prev) : prev_(prev), node_() {} private: // friend shared_ptr; static shared_ptr& root() { static shared_ptr e(new CommandChain()); return e; }; shared_ptr 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> 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 &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 calcDistance(const F &field, P start) const { vector dist(N * N, MD); priority_queue> 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 createTableFromDist2Num() { constexpr int h = N * 2 * 1000; vector 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 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::min(); ll money_ = 0; ll income_ = 0; int turn_ = 0; int highway_ = 0; int man_power_ = 1; // int score_ = numeric_limits::min(); shared_ptr 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 nextStateHighway(const vector &command_bh) { // TODO: check next.highway_ < command_bh.size if (highway_ + 1 >= command_bh.size()) return optional(); ll cost = ceil(10000000.0 / sqrt(man_power_)); // floor らしいけど怖いのでceil if (money_ < cost) return optional(); 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(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> problem_routes_mat{N, N}; for (auto &p : problem.routes_) { problem_routes_mat(p.first).push_back(p.second); } // 高速道路を追加する順番を FIX する vector command_bh; command_bh.push_back( CommandBuildHighway{.income = 0, .pos = P{0, 0}, .horizontal = false}); // よくわからないのでとりあえず中央から選んでいくことにする F done{N, N}; queue

que; que.emplace(N / 2, N / 2); done(N / 2, N / 2) = true; F 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> 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; }