#pragma GCC optimize("-O2") #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include struct Point { int i, j; }; bool operator<(const Point& lhs, const Point& rhs) { return (lhs.i < rhs.i || lhs.j < rhs.j); } bool operator>(const Point& lhs, const Point& rhs) { return (lhs.i > rhs.i || lhs.j > rhs.j); } struct Road { Point u, v; }; bool operator==(const Point& lhs, const Point& rhs) { return (lhs.i == rhs.i && lhs.j == rhs.j); } // --------------------- macros ---------------------- #define pii std::pair #define Vec std::vector #define rep(i, s, n) for(int i = s; i < (n); i++) using namespace std; using ll = long long; // --------------------- constants ---------------------- constexpr int INF = 1e9 + 10; constexpr ll LINF = 1LL<<60; constexpr double EPS = 1e-6; const double PI = std::acos(-1); // clockwise static const int di[4] = {0, 1, 0, -1}; static const int dj[4] = {1, 0, -1, 0}; const double TL = 2.0; const double TL_90 = TL * 0.9; const double TL_95 = TL * 0.95; constexpr int N = 3000; constexpr int TERM = 400; constexpr int H = 14; constexpr int W = 14; constexpr int INIT_FUND = 1'000'000; constexpr double TIME_ROAD = 1.0; constexpr double TIME_HIGHWAY = 0.223; constexpr int DONATION = 50'000; constexpr int FEE_HIGHWAY = 60; // --------------------- global variables ---------------------- std::random_device seed_gen; std::mt19937 mt(seed_gen()); clock_t start_time, cur_time; Point A[N], C[N]; // --------------------- functionss ---------------------- double get_time() { return (double)(clock() - start_time) / CLOCKS_PER_SEC; } bool is_out(int i, int j, int d) { return (i < 0 || i >= d || j < 0 || j >= d); } bool is_out(int i, int j, int h, int w) { return (i < 0 || i >= h || j < 0 || j >= w); } template T pow2(T a) { return a * a; } bool arg_parse(int argv, char* argc[]) { for(int i = 0; i < argv; i++) { if(std::strcmp(argc[i], "--seed") == 0) { if(i + 1 > argv) { std::cerr << "no arguments." << std::endl; return false; } int _seed = std::stoi(argc[i+1]); mt = std::mt19937(_seed); } } return true; } // --------------------- classes ---------------------- struct IOServer { int patron = 1; int fund = INIT_FUND; void read_output1(int i1, int j1, int i2, int j2) { fund -= std::floor((double)10000000 / std::sqrt(patron)); } void read_output2() { patron++; } void read_output3() { fund += DONATION; } }; // ---------------------------------------------------- struct Result { int k; long long score; }; class Solver { public: Result best_result; int num_search = 0; int money; int patron; Road p_road; // priority road Vec>>> cnt; Vec>> dist_cur; Vec>>> is_highway; Vec> highway_list; Vec num_highway_on_path; int num_reward = 0; int num_highway; #ifdef LOCAL IOServer judge; #endif Solver() { } // constructor void init() { int buf; std::cin >> buf >> buf; for(int i = 0; i < N; i++) { std::cin >> A[i].i >> A[i].j >> C[i].i >> C[i].j; A[i].i--; C[i].i--; A[i].j--; C[i].j--; } patron = 1; money = INIT_FUND; num_highway = 0; cnt.resize(H, Vec>>(W, Vec>(H, Vec(W, 0)))); is_highway.resize(H, Vec>>(W, Vec>(H, Vec(W, false)))); dist_cur.resize(N, Vec>(H, Vec(W, 1e18))); num_highway_on_path.resize(N, 0); // BFS Vec> dist; for(int i = 0; i < N; i++) { dist.clear(); dist.resize(H, Vec(W, INF)); if(A[i] == C[i]) continue; queue> q; dist[A[i].i][A[i].j] = 0; q.push(std::make_pair(0, A[i])); bool ok = false; int ni, nj; while(!q.empty() && !ok) { auto[cost, p] = q.front(); q.pop(); for(int d = 0; d < 4; d++) { ni = p.i + di[d]; nj = p.j + dj[d]; if(is_out(ni,nj,H,W)) continue; if(dist[ni][nj] > cost+1) { dist[ni][nj] = cost + 1; q.push(std::make_pair(cost+1, Point{ni,nj})); } if(ni == C[i].i && nj == C[i].j) { ok = true; break; } } } // 復元 queue> q_rev; Vec> visited(H, Vec(W, false)); q_rev.push({dist[C[i].i][C[i].j], C[i]}); ok = false; visited[C[i].i][C[i].j] = true; while(!q_rev.empty() && !ok) { auto[d, p] = q_rev.front(); q_rev.pop(); for(int dir = 0; dir < 4; dir++) { ni = p.i + di[dir]; nj = p.j + dj[dir]; if(is_out(ni,nj,H,W)) continue; if(dist[ni][nj] == d - 1) { cnt[ni][nj][p.i][p.j]++; cnt[p.i][p.j][ni][nj]++; if(!visited[ni][nj]) { visited[ni][nj] = true; q_rev.push(std::make_pair(d-1, Point{ni,nj})); } } } } } int max_cnt = -1; rep(i, 0, H)rep(j,0,W)rep(k,0,H)rep(l,0,W) if(cnt[i][j][k][l]>max_cnt){ max_cnt=cnt[i][j][k][l]; p_road = {Point{i,j}, Point{k,l}}; } fprintf(stderr, "[case] N: %d, TERM: %d\n", N, TERM); } // main solve void solve() { int pre_choice = -1; for(int t = 0; t < TERM; t++) { int nil; #ifndef LOCAL scanf("%d %d", &money, &patron); #endif #ifdef LOCAL if(t % 20 == 0) { fprintf(stderr, "[Info] TERM: %03d, time: %6.3f, money: %9d, patron: %2d\n", t, get_time(), money, patron ); fprintf(stderr, "...... Number of Highway: %2d, \n", num_highway ); fprintf(stderr, "...... Number of Highway on path: %3d, \n\n", num_reward ); } #endif // 60日までは協力者集め if(t < 59) { std::cout << "2" << std::endl; pre_choice = 2; patron++; } else { auto[u,v] = p_road; const ll exp_reward = cnt[u.i][u.j][v.i][v.j] * (TERM - t) * FEE_HIGHWAY; ll build_cost = get_cost_build_highway(); if(exp_reward >= get_cost_build_highway() && money >= build_cost) { #ifdef LOCAL fprintf(stderr, "[Info] BUILDING HIGHWAY!\n" ); fprintf(stderr, "...... EXPECTED REWARD: %10lld, BUILD COST: %10lld\n\n", exp_reward, build_cost ); #endif std::cout << "1 " << u.i + 1 << " " << u.j + 1 << " " << v.i + 1 << " " << v.j + 1 << std::endl; is_highway[u.i][u.j][v.i][v.j] = is_highway[v.i][v.j][u.i][u.j] = true; money -= build_cost; num_highway++; update_cnt(); } else { std::cout << "3" << std::endl; money += DONATION; } } get_reward(); } } // solve void update_cnt() { cnt.clear(); cnt.resize(H, Vec>>(W, Vec>(H, Vec(W, 0)))); // dijkstra Vec> dist; for(int i = 0; i < N; i++) { dist.clear(); dist.resize(H, Vec(W, 1e19)); if(A[i] == C[i]) continue; std::priority_queue, vector>, greater> > pq; dist[A[i].i][A[i].j] = 0.0; pq.push({0.0, A[i]}); int ni, nj; double len; while(!pq.empty()) { auto[cost, p] = pq.top(); pq.pop(); if(cost - dist[p.i][p.j] > EPS || cost > dist[C[i].i][C[i].j] + EPS) continue; for(int d = 0; d < 4; d++) { ni = p.i + di[d]; nj = p.j + dj[d]; if(is_out(ni,nj,H,W)) continue; len = is_highway[p.i][p.j][ni][nj] ? TIME_HIGHWAY : 1.0; if(dist[ni][nj] > cost+len+EPS) { dist[ni][nj] = cost + len; pq.push(std::make_pair(cost+len, Point{ni,nj})); } } } // while dist_cur[i] = dist; Vec> visited(H, Vec(W, false)); bool ok = false; int num_hw = 0; auto dfs=[&](auto dfs, const Point& u, const Point& v) -> void { if(visited[u.i][u.j] || ok) return; visited[u.i][u.j] = true; if(u==v) { ok = true; return; } for(int d = 0; d < 4; d++) { int ni = u.i + di[d]; int nj = u.j + dj[d]; if(is_out(ni,nj,H,W)) continue; double len = is_highway[ni][nj][u.i][u.j] ? TIME_HIGHWAY : 1.0; if(abs((dist[u.i][u.j]-len)-dist[ni][nj]) < EPS) { if(is_highway[ni][nj][u.i][u.j]) num_hw++; if(!ok) dfs(dfs, Point{ni,nj}, v); } } }; dfs(dfs, C[i], A[i]); num_highway_on_path[i] = num_hw; // 復元 queue> q_rev; q_rev.push({dist[C[i].i][C[i].j], C[i]}); visited.clear(); visited.resize(H, Vec(W, false)); visited[C[i].i][C[i].j] = true; while(!q_rev.empty()) { auto[d, p] = q_rev.front(); q_rev.pop(); for(int dir = 0; dir < 4; dir++) { ni = p.i + di[dir]; nj = p.j + dj[dir]; if(is_out(ni,nj,H,W)) continue; len = is_highway[p.i][p.j][ni][nj] ? TIME_HIGHWAY : 1.0; if(std::abs(dist[ni][nj] - (d - len)) < EPS) { cnt[ni][nj][p.i][p.j]++; cnt[p.i][p.j][ni][nj]++; if(!visited[ni][nj]) { visited[ni][nj] = true; q_rev.push(std::make_pair(d-len, Point{ni,nj})); } } } } } int max_cnt = -1; rep(i, 0, H)rep(j,0,W)rep(k,0,H)rep(l,0,W) if(cnt[i][j][k][l]>max_cnt&&!is_highway[i][j][k][l]){ max_cnt=cnt[i][j][k][l]; p_road = {Point{i,j}, Point{k,l}}; } } void get_reward() { num_reward = 0; for(int i = 0; i < N; i++) { money += num_highway_on_path[i] * FEE_HIGHWAY; num_reward += num_highway_on_path[i]; } } ll get_cost_build_highway() { constexpr double BASE = 1e7; return (ll)std::floor( BASE / std::sqrt(patron) ); } // return summaries of solve void summary() { std::cerr << "\n##### SUMMARY #######################\n"; fprintf(stderr, "ELAPSED TIME : %6.4f s\n", get_time()); fprintf(stderr, "NUMBER OF SEARCH : \n", this->num_search); std::cerr << "######################################\n"; } private: }; int main(int argv, char* argc[]) { start_time = clock(); Solver solver; #ifdef _OPTUNA bool ok = arg_parse(int argv, char* argc[]) #endif solver.init(); solver.solve(); solver.summary(); return 0; }