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 #endif #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #ifdef PERF #include #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 Pii; typedef pair 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 string to_string(const vector& vec) { string ret = ""; rep(i, vec.size()) { ret += vec[i].to_string(); if (i + 1 != vec.size()) { ret += ","; } } return ret; } template ostream& operator<<(ostream& os, const vector& 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 const T& rand_vec(const vector& vec) { assert(vec.size() > 0); return vec[rand(0, vec.size())]; } template void shuffle(vector& 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( chrono::duration_cast(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( chrono::duration_cast(now - _start).count() / 1000); } inline int ns() const { const chrono::system_clock::time_point now = chrono::system_clock::now(); return static_cast( chrono::duration_cast(now - _start).count()); } }; #ifdef LOCAL struct Timers : unordered_map { 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; /* start */ vector PARAMS = {}; enum Dir { // y-1, y+1, x-1, x+1 kU, kD, kL, kR }; 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& Adj() const { return adj_poses[*this]; } const vector& 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; } } 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, const int z) { 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>(N2); adj_dirs = vector>(N2); move_to = vector>(4, vector(N2, Pos::Dummy())); pos_2_y.resize(N2); pos_2_x.resize(N2); rep(y, N) { rep(x, N) { const Pos p{x, y}; 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); } } } } } static int N, N2, N4; static vector> adj_poses; static vector> adj_dirs; static vector> move_to; static vector pos_2_x, pos_2_y; }; vector> Pos::adj_poses; vector> Pos::adj_dirs; vector> Pos::move_to; vector Pos::pos_2_x, Pos::pos_2_y; int Pos::N, Pos::N2, Pos::N4; /* start */ int N, T; vector Ss, Gs; enum ActionKind { kBuild, kHuman, kMoney }; struct Action { ActionKind kind; Pos p0, p1; }; struct Solution { Solution() {} static void StaticInit() {} friend ostream& operator<<(ostream& os, const Solution& sol) { return os; } }; /* start */ struct Road { Pos p0, p1; }; struct ROI { Pos p0, p1, s, g; ROI(const Pos& _pa, const Pos& _pb) : p0(min(_pa.X(), _pb.X()), min(_pa.Y(), _pb.Y())), p1(max(_pa.X(), _pb.X()), max(_pa.Y(), _pb.Y())), s(_pa), g(_pb) {} }; class Solver { public: Solver(istream& _is) : is(_is) { is >> N >> T; Pos::StaticInit(14); Ss.reserve(N); Gs.reserve(N); rep(i, N) { int a, b, c, d; is >> a >> b >> c >> d; a--; b--; c--; d--; Ss.emplace_back(b, a); Gs.emplace_back(d, c); } } ll Cost(const int v) const { return (ll)((long double)1e7 / sqrt((long double)v) + 0.01); } vector> WarshalOrder() const { // 初期化 vector> warshal(Pos::N2, vector(Pos::N2, INF)); rep(i, Pos::N2) { rep(j, Pos::N2) { const Pos pi(i); const Pos pj(j); warshal[pi][pj] = pi.Manhattan(pj) * 1000; } } vector> order; vector> exists(30, vector(30, false)); constexpr int kKosoku = 223; vector dist2kosoku(14 * 2 * 1000 + 100); rep(kosoku, 999) { rep(hutu, 30) { const int dist = kosoku * kKosoku + hutu * 1000; if (dist >= (int)dist2kosoku.size()) { break; } assert(dist2kosoku[dist] == 0); dist2kosoku[dist] = kosoku; } } // TODO: 200調整 rep(t, 200) { pair best; best.second = 0; // 各辺を変更した時の高速道路の個数を求める rep(y, Pos::N) { rep(x, Pos::N) { const Pos p0(x, y); rep(_t, 2) { Pos p1 = p0; if (_t == 0) { if (!p1.Move(kD)) { continue; } } else { if (!p1.Move(kR)) { continue; } } if (exists[p0.Y() + p1.Y()][p0.X() + p1.X()]) continue; // 高速道路片道合計の差分 int diff_count = 0; rep(i, N) { const Pos s = Ss[i]; const Pos g = Gs[i]; const auto original_dist = warshal[s][g]; const auto next_dist_0 = warshal[s][p0] + kKosoku + warshal[p1][g]; const auto next_dist_1 = warshal[s][p1] + kKosoku + warshal[p0][g]; const auto next_dist = min(next_dist_0, next_dist_1); if (next_dist < original_dist) { diff_count += dist2kosoku[next_dist] - dist2kosoku[original_dist]; } } if (best.second < diff_count) { best.first = Road{p0, p1}; best.second = diff_count; } } } } if (best.second == 0) break; order.emplace_back(best); // warshal更新 rep(i, Pos::N2) { const Pos pi(i); rep(j, Pos::N2) { const Pos pj(j); const auto next_dist_0 = warshal[pi][best.first.p0] + kKosoku + warshal[best.first.p1][pj]; const auto next_dist_1 = warshal[pi][best.first.p1] + kKosoku + warshal[best.first.p0][pj]; const auto next_dist = min(next_dist_0, next_dist_1); chmin(warshal[pi][pj], next_dist); } } } return order; } vector> GreedyOrder() const { vector> order; vector rois; vector> exists(30, vector(30, false)); // ROI初期化 rep(i, N) { rois.emplace_back(Ss[i], Gs[i]); } rep(t, T) { if (order.size() == 13 * 14 * 2) { break; } //各ROIに対してimos vector> imos(30, vector(30, 0)); for (const auto& roi : rois) { imos[roi.p0.Y() * 2][roi.p0.X() * 2] += 1; imos[roi.p0.Y() * 2][roi.p1.X() * 2 + 1] += -1; imos[roi.p1.Y() * 2 + 1][roi.p0.X() * 2] += -1; imos[roi.p1.Y() * 2 + 1][roi.p1.X() * 2 + 1] += 1; } // imos rep(y, 30) { rep(x, 29) { imos[y][x + 1] += imos[y][x]; } } rep(x, 30) { rep(y, 29) { imos[y + 1][x] += imos[y][x]; } } // 一番偉い辺 Road best_road; int best_count = -1; rep(y, 14) { rep(x, 14) { // y+1 if (y + 1 < 14 && !exists[y * 2 + 1][x * 2]) { const int count = imos[y * 2 + 1][x * 2]; // cerr << count << endl; if (count > best_count) { best_count = count; best_road = Road{Pos{x, y}, Pos{x, y + 1}}; } } // x+1 if (x + 1 < 14 && !exists[y * 2][x * 2 + 1]) { const int count = imos[y * 2][x * 2 + 1]; if (count > best_count) { best_count = count; best_road = Road{Pos{x, y}, Pos{x + 1, y}}; } } } } if (best_count <= 0) break; order.emplace_back(best_road, best_count); exists[best_road.p0.Y() + best_road.p1.Y()] [best_road.p0.X() + best_road.p1.X()] = true; // roiの更新 vector next_rois; next_rois.reserve(rois.size() * 2); const auto& p0 = best_road.p0; const auto& p1 = best_road.p1; for (const auto& roi : rois) { // s,gをroadのp0,p1のどちらに対応させるか // dist + dist + 1 == 元のdist Pos s = roi.s; Pos g = roi.g; if (s.Manhattan(p0) + g.Manhattan(p1) + 1 == s.Manhattan(g)) { } else if (s.Manhattan(p1) + g.Manhattan(p0) + 1 == s.Manhattan(g)) { swap(s, g); } else { // 通過しない next_rois.emplace_back(roi); continue; } // s,p0とg,p1が誕生 if (s != p0) { next_rois.emplace_back(s, p0); } if (g != p1) { next_rois.emplace_back(g, p1); } } rois = std::move(next_rois); } return order; } Solution Solve(const int time_limit) const { auto order = WarshalOrder(); // 番兵 order.emplace_back(Road{Pos{0, 0}, Pos{0, 1}}, 0); vector ruiseki_counts; ruiseki_counts.insert(ruiseki_counts.begin(), 0); rep(i, order.size()) { ruiseki_counts.emplace_back(ruiseki_counts.back() + order[i].second); } // dp[t][v][k] := t時点で協力者v人で次はk番目のorder constexpr int kMaxV = 200; vector> dp(kMaxV + 1, vector(order.size(), -INF)); using IDX = tuple; vector>> prevs( T + 1, vector>(kMaxV + 1, vector(order.size(), {0, 0, 0}))); dp[1][0] = 1'000'000; rep(t, T) { auto next_dp = dp; rep(v, kMaxV + 1) { rep(k, order.size()) { const IDX current_idx = std::make_tuple(t, v, k); if (dp[v][k] < 0) continue; // 建設 if (k + 1 < (int)order.size() && dp[v][k] >= Cost(v)) { const ll next_val = dp[v][k] - Cost(v) + (ll)60 * ruiseki_counts[k + 1]; if (next_dp[v][k + 1] < next_val) { // cerr << next_val << endl; next_dp[v][k + 1] = next_val; prevs[t + 1][v][k + 1] = current_idx; } } // 協力者 if (v + 1 <= kMaxV) { const ll next_val = dp[v][k] + (ll)60 * ruiseki_counts[k]; if (next_dp[v + 1][k] < next_val) { // cerr << next_val << endl; next_dp[v + 1][k] = next_val; prevs[t + 1][v + 1][k] = current_idx; } } // 金 const ll next_val = dp[v][k] + 50'000 + (ll)60 * ruiseki_counts[k]; if (next_dp[v][k] < next_val) { // cerr << next_val << endl; next_dp[v][k] = next_val; prevs[t + 1][v][k] = current_idx; } } } dp = std::move(next_dp); } ll best_money = 0; tuple best_idxes; rep(v, kMaxV + 1) { rep(k, order.size()) { if (dp[v][k] > best_money) { best_money = dp[v][k]; best_idxes = std::make_tuple(T, v, k); } } } cerr << "best_money: " << best_money << endl; vector actions; { auto current_idx = best_idxes; while (std::get<0>(current_idx) != 0) { const auto [t, v, k] = current_idx; const auto [prev_t, prev_v, prev_k] = prevs[t][v][k]; if (v == prev_v && k == prev_k) { actions.push_back({kMoney, Pos::Dummy(), Pos::Dummy()}); } else if (v == prev_v) { actions.push_back( {kBuild, order[prev_k].first.p0, order[prev_k].first.p1}); } else { actions.push_back({kHuman, Pos::Dummy(), Pos::Dummy()}); } current_idx = prevs[t][v][k]; } assert((int)actions.size() == T); reverse(all(actions)); } rep(t, T) { ll u, v; is >> u >> v; const auto& action = actions[t]; if (action.kind == kBuild) { cout << 1 << " " << 1 + action.p0.Y() << " " << 1 + action.p0.X() << " " << 1 + action.p1.Y() << " " << 1 + action.p1.X() << endl; } else if (action.kind == kHuman) { cout << 2 << endl; } else { cout << 3 << endl; } } std::quick_exit(0); return Solution(); } istream& is; }; 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(); Solver solver(cin); auto sol = solver.Solve(1850 - timer.ms()); cout << sol << endl; return 0; }