#pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include // #include using namespace std; // using namespace atcoder; struct Timer { chrono::system_clock::time_point start; double elapsed; void begin() { start = chrono::system_clock::now(); } double stopwatch() { chrono::system_clock::time_point end = chrono::system_clock::now(); elapsed = chrono::duration_cast(end - start).count(); elapsed *= 1e-9; // nanoseconds -> seconds return elapsed; } }; constexpr double time_limit = 1.85; constexpr int g = 14; constexpr int slow = 1000; constexpr int fast = 223; constexpr long long bonus = 50000; struct Input { int n, t; vector> ab, cd; void input() { cin >> n >> t; ab.resize(n); cd.resize(n); for (int i = 0; i < n; ++i) { int a, b, c, d; cin >> a >> b >> c >> d; ab[i] = {a - 1, b - 1}; cd[i] = {c - 1, d - 1}; } } }; long long expense(int people) { return floor(1e7 / sqrt(people)); } constexpr int inf = 1e9; constexpr int no_construction_turn = 300; constexpr int min_people = 35; constexpr int max_people = 100; constexpr int add_people = 25; struct Solver { Timer timer; int n, t; vector> ab, cd; vector> h, v; long long money = 1000000; int people = 1; int income = 0; int constructions = 0; vector>>> costs; mt19937 engine = mt19937(0); Solver(const Input& input) { timer.begin(); n = input.n; t = input.t; ab = input.ab; cd = input.cd; h = vector>(g, vector(g - 1, false)); v = vector>(g - 1, vector(g, false)); calc_income(); } void solve() { for (int turn = 0; turn < t; ++turn) { //money += income; cin >> money >> people; if (turn >= no_construction_turn || timer.stopwatch() > time_limit) { cout << 3 << endl; money += bonus; } else if (money >= expense(people)) { auto [x, y, z, w] = choose_road(turn); if (x == -1) { cout << 3 << endl; money += bonus; continue; } cout << 1 << " " << x + 1 << " " << y + 1 << " " << z + 1 << " " << w + 1 << endl; ++constructions; money -= expense(people); income = update_income(x, y, z, w); } else if (people < min(max_people, min_people + add_people * constructions)) { cout << 2 << endl; ++people; } else { cout << 3 << endl; money += bonus; } } } vector> dijkstra(int sx, int sy) { vector> costs(g, vector(g, inf)); costs[sx][sy] = 0; priority_queue> todo; todo.push({0, sx, sy}); while (!todo.empty()) { auto [cost, x, y] = todo.top(); todo.pop(); cost = -cost; if (costs[x][y] < cost) { continue; } if (x > 0) { int c = v[x - 1][y] ? fast : slow; if (cost + c < costs[x - 1][y]) { costs[x - 1][y] = cost + c; todo.push({-(cost + c), x - 1, y}); } } if (x < g - 1) { int c = v[x][y] ? fast : slow; if (cost + c < costs[x + 1][y]) { costs[x + 1][y] = cost + c; todo.push({-(cost + c), x + 1, y}); } } if (y > 0) { int c = h[x][y - 1] ? fast : slow; if (cost + c < costs[x][y - 1]) { costs[x][y - 1] = cost + c; todo.push({-(cost + c), x, y - 1}); } } if (y < g - 1) { int c = h[x][y] ? fast : slow; if (cost + c < costs[x][y + 1]) { costs[x][y + 1] = cost + c; todo.push({-(cost + c), x, y + 1}); } } } return costs; } vector>>> all_costs() { vector>>> costs(g, vector>>(g)); for (int x = 0; x < g; ++x) { for (int y = 0; y < g; ++y) { costs[x][y] = dijkstra(x, y); } } return costs; } long long calc_income() { costs = all_costs(); long long s = 0; for (int i = 0; i < n; ++i) { auto [a, b] = ab[i]; auto [c, d] = cd[i]; int cost = costs[a][b][c][d]; int j = 0; while ((cost - slow * j) % fast) { ++j; } s += (cost - slow * j) / fast; } return 60 * s; } long long update_income(int x, int y, int z, int w) { for (int a = 0; a < g; ++a) { for (int b = 0; b < g; ++b) { for (int c = 0; c < g; ++c) { for (int d = 0; d < g; ++d) { costs[a][b][c][d] = min(costs[a][b][c][d], min(costs[a][b][x][y] + fast + costs[z][w][c][d], costs[a][b][z][w] + fast + costs[x][y][c][d])); } } } } long long s = 0; for (int i = 0; i < n; ++i) { auto [a, b] = ab[i]; auto [c, d] = cd[i]; int cost = costs[a][b][c][d]; int j = 0; while ((cost - slow * j) % fast) { ++j; } s += (cost - slow * j) / fast; } return 60 * s; } long long calc_new_income(int x, int y, int z, int w) { long long s = 0; for (int i = 0; i < n; ++i) { auto [a, b] = ab[i]; auto [c, d] = cd[i]; int cost = min(costs[a][b][c][d], min(costs[a][b][x][y] + fast + costs[z][w][c][d], costs[a][b][z][w] + fast + costs[x][y][c][d])); int j = 0; while ((cost - slow * j) % fast) { ++j; } s += (cost - slow * j) / fast; } return 60 * s; } tuple choose_road(int turn) { vector> sampled; int patience = 200; while (--patience && (int)sampled.size() < 3000 / turn && timer.stopwatch() < time_limit) { if (engine() % 2) { int x = engine() % g; int y = engine() % (g - 1); if (x % 3 != 2) { continue; } if (!h[x][y]) { sampled.push_back({true, x, y}); } } else { int x = engine() % (g - 1); int y = engine() % g; if (y % 3 != 2) { continue; } if (!v[x][y]) { sampled.push_back({false, x, y}); } } } int max_profit = 0; int best = -1; for (int i = 0; i < (int)sampled.size(); ++i) { auto [is_h, x, y] = sampled[i]; long long new_income = is_h ? calc_new_income(x, y, x, y + 1) : calc_new_income(x, y, x + 1, y); long long profit = (new_income - income) * (t - turn - 1); if (max_profit < profit) { max_profit = profit; best = i; } } if (best == -1) { if (timer.stopwatch() < time_limit) { return choose_road(turn); } else { return {-1, -1, -1, -1}; } } auto [is_h, x, y] = sampled[best]; if (is_h) { h[x][y] = true; return {x, y, x, y + 1}; } else { v[x][y] = true; return {x, y, x + 1, y}; } } }; int main() { Input input; input.input(); Solver solver(input); solver.solve(); cerr << solver.money << endl; cerr << solver.timer.stopwatch() << endl; return 0; }