#include #include #include #include #include #include #include using namespace std; class action { public: static constexpr int D = 14; static constexpr int ACTION_BUILD = 1; static constexpr int ACTION_LEVEL = 2; static constexpr int ACTION_MONEY = 3; int tp, id; action() : tp(-1), id(-1) {} action(int tp_) : tp(tp_), id(-1) { assert(tp == 2 || tp == 3); } action(int tp_, int id_) : tp(tp_), id(id_) { assert(tp == 1 && 0 <= id && id < D * (D - 1) * 2); } string to_string() const { assert(tp != -1); if (tp == 2 || tp == 3) { return std::to_string(tp); } int xa, ya, xb, yb; if (id < D * (D - 1)) { xa = id / D; ya = id % D; xb = xa + 1; yb = ya; } else { xa = (id - D * (D - 1)) / (D - 1); ya = (id - D * (D - 1)) % (D - 1); xb = xa; yb = ya + 1; } // output in 1-indexed return std::to_string(tp) + " " + std::to_string(xa + 1) + " " + std::to_string(ya + 1) + " " + std::to_string(xb + 1) + " " + std::to_string(yb + 1); } }; uint64_t seed = 123456789; uint64_t xorshift64() { seed ^= seed << 13; seed ^= seed >> 7; seed ^= seed << 17; return seed; } int main() { // step #1. initial input const int INF = 1012345678; const int D = action::D; int N, T; cin >> N >> T; vector X(N), Y(N); for (int i = 0; i < N; i++) { int a, b, c, d; cin >> a >> b >> c >> d; X[i] = (a - 1) * D + (b - 1); Y[i] = (c - 1) * D + (d - 1); } // step #2. make graph-like list of citizens vector deg(D * D); for (int i = 0; i < N; i++) { deg[X[i]] += 1; deg[Y[i]] += 1; } vector > G(D * D); for (int i = 0; i < N; i++) { if (deg[X[i]] > deg[Y[i]] || (deg[X[i]] == deg[Y[i]] && X[i] < Y[i])) { G[X[i]].push_back(Y[i]); } else { G[Y[i]].push_back(X[i]); } } int cnt = 0; for (int i = 0; i < D * D; i++) { if (deg[i] >= 1) { cnt += 1; } } // step #3. function to calculate score auto getdist = [&](const vector& road) { vector > dist(D * D, vector(D * D, INF)); vector q1(D * D); vector q2(D * D); for (int i = 0; i < D * D; i++) { dist[i][i] = 0; int ql1 = 0, qr1 = 1; int ql2 = 0, qr2 = 0; q1[0] = i; while (ql1 != qr1 || ql2 != qr2) { int c1 = (ql1 != qr1 ? q1[ql1] : INF); int c2 = (ql2 != qr2 ? q2[ql2] : INF); int pos = -1, curdist = 0; if (c1 <= c2) { curdist = (c1 >> 12); pos = (c1 & ((1 << 12) - 1)); ql1 += 1; } else { curdist = (c2 >> 12); pos = (c2 & ((1 << 12) - 1)); ql2 += 1; } int px = pos / D, py = pos % D; // direction 1: down if (px != D - 1 && road[px * D + py] == 0) { if (dist[i][pos + D] > curdist + 1000) { dist[i][pos + D] = curdist + 1000; q1[qr1++] = (dist[i][pos + D] << 12) | (pos + D); } } if (px != D - 1 && road[px * D + py] == 1) { if (dist[i][pos + D] > curdist + 223) { dist[i][pos + D] = curdist + 223; q2[qr2++] = (dist[i][pos + D] << 12) | (pos + D); } } // direction 2: up if (px != 0 && road[(px - 1) * D + py] == 0) { if (dist[i][pos - D] > curdist + 1000) { dist[i][pos - D] = curdist + 1000; q1[qr1++] = (dist[i][pos - D] << 12) | (pos - D); } } if (px != 0 && road[(px - 1) * D + py] == 1) { if (dist[i][pos - D] > curdist + 223) { dist[i][pos - D] = curdist + 223; q2[qr2++] = (dist[i][pos - D] << 12) | (pos - D); } } // direction 3: right if (py != D - 1 && road[D * (D - 1) + px * (D - 1) + py] == 0) { if (dist[i][pos + 1] > curdist + 1000) { dist[i][pos + 1] = curdist + 1000; q1[qr1++] = (dist[i][pos + 1] << 12) | (pos + 1); } } if (py != D - 1 && road[D * (D - 1) + px * (D - 1) + py] == 1) { if (dist[i][pos + 1] > curdist + 223) { dist[i][pos + 1] = curdist + 223; q2[qr2++] = (dist[i][pos + 1] << 12) | (pos + 1); } } // direction 4: left if (py != 0 && road[D * (D - 1) + px * (D - 1) + py - 1] == 0) { if (dist[i][pos - 1] > curdist + 1000) { dist[i][pos - 1] = curdist + 1000; q1[qr1++] = (dist[i][pos - 1] << 12) | (pos - 1); } } if (py != 0 && road[D * (D - 1) + px * (D - 1) + py - 1] == 1) { if (dist[i][pos - 1] > curdist + 223) { dist[i][pos - 1] = curdist + 223; q2[qr2++] = (dist[i][pos - 1] << 12) | (pos - 1); } } } } return dist; }; // step #4. process queries int current_money = 1000000; int current_level = 1; int current_score = 0; int used_roads = 0; vector road(D * (D - 1) * 2, 0); vector > dist = getdist(road); auto calc = [&](const vector& road) { int answer = 0; for (int i = 0; i < N; i++) { answer += (dist[X[i]][Y[i]] * 287) % 1000; } return answer; }; vector a(T); vector level(T + 1), money(T + 1), score(T + 1); for (int i = 0; i < T; i++) { int tmp1, tmp2; cin >> tmp1 >> tmp2; // decide action int required_money = int(10000000 / sqrt(current_level)); if (i < 37) { a[i] = action(action::ACTION_LEVEL); } else if (used_roads == 0 && current_money < required_money) { a[i] = action(action::ACTION_MONEY); } else { if (current_money >= required_money) { int opt_choice = -1; int opt_score = -INF; for (int j = 0; j < D * (D - 1) * 2; j++) { if (road[j] == 0) { int va, vb; if (j < D * (D - 1)) { va = j; vb = j + D; } else { va = (j - D * (D - 1)) / (D - 1) * D + (j - D * (D - 1)) % (D - 1); vb = va + 1; } int subscore = 0; for (int k = 0; k < N; k++) { int d1 = dist[X[k]][Y[k]]; int d2 = dist[X[k]][va] + dist[Y[k]][vb] + 223; int d3 = dist[X[k]][vb] + dist[Y[k]][va] + 223; int d4 = min(d1, min(d2, d3)); subscore += (d4 * 287) % 1000; } if (opt_score < subscore) { opt_score = subscore; opt_choice = j; } } } a[i] = action(action::ACTION_BUILD, opt_choice); used_roads += 1; } else { a[i] = action(action::ACTION_LEVEL); } } // process action if (a[i].tp == action::ACTION_BUILD) { road[a[i].id] = 1; used_roads += 1; dist = getdist(road); current_money -= required_money; current_score = calc(road); } if (a[i].tp == action::ACTION_LEVEL) { current_level += 1; } if (a[i].tp == action::ACTION_MONEY) { current_money += 50000; } current_money += current_score * 60; money[i + 1] = current_money; level[i + 1] = current_level; score[i + 1] = current_score; } int best_money = -INF; int best_sep = -1; for (int i = 0; i <= T; i++) { int final_money = money[i] + (score[i] * 60 + 50000) * (T - i); if (best_money < final_money) { best_money = final_money; best_sep = i; } } for (int i = best_sep; i < T; i++) { a[i] = action(action::ACTION_MONEY); } for (int i = 0; i < T; i++) { cout << a[i].to_string() << endl; } cerr << "level = " << level[best_sep] << ", money = " << best_money << ", score = " << score[best_sep] << " (sep = " << best_sep << ")" << endl; return 0; }