#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using Ps = pair; using vec_int = vector; using P = pair; using P2 = pair; using P3 = pair; // using T = tuple; using Td = tuple; using T2 = tuple; using T3 = tuple; using T4 = tuple; using T5 = tuple; using TT = tuple; using ll = long long; using uc = unsigned char; #define rep(i, n) for (int i = 0; i < (int)(n); i++) int N, T; vec_int A, B, C, D; // #pragma GCC optimize("Ofast") std::mt19937 mt{12345}; int RAND_ARR_LEN = 100000; int RAND_RANGE = 1000000000; float TIME_LIMIT = 2000; float INV_TIME_LIMIT = 1. / 1000.; const int JOB_MAX_LEN = 1003; std::uniform_int_distribution dist(1, RAND_RANGE); int WAITING_TASK = 1001; void remove_val_and_pop_from_last(vec_int &A, int val) { for (int i = 0; i < A.size(); i++) { if (A.at(i) == val) { A.at(i) = A.at(A.size() - 1); A.pop_back(); return; } } throw runtime_error("trying to remove non-existing value"); } class Rand { private: int count = 0; vec_int rand_arr; public: Rand(){ rep(i, RAND_ARR_LEN){ rand_arr.push_back(dist(mt)); } } ; int get(); int get_rand(int from, int to); float get_float(); } ; int Rand::get() { int num = rand_arr.at(count); count += 1; count %= RAND_ARR_LEN; return num; } int Rand::get_rand(int from, int to) { int diff = to - from; int num = get() % diff; return num + from; } float Rand::get_float() { // 0~1の間の一様乱数 return (float)get() / (float)RAND_RANGE; } Rand ro; class PseudoSet { private: vec_int index_arr; public: vec_int data; PseudoSet(){}; PseudoSet(int value_range) { index_arr = vec_int(value_range, -1); } bool count(int value); void insert(int value); void erase(int value); vec_int get_data() { return data; }; int size() { return data.size(); }; int get_random() { return data.at(ro.get_rand(0, size())); }; }; bool PseudoSet::count(int value) { return index_arr[value] != -1; } void PseudoSet::insert(int value) { if (count(value)) return; index_arr[value] = data.size(); data.push_back(value); } void PseudoSet::erase(int value) { if (!count(value)) { // throw runtime_error("no existing value:"+to_string(value)); return; } int tail_value = data[data.size() - 1]; if (value == tail_value) { data.pop_back(); index_arr[value] = -1; } else { index_arr[tail_value] = index_arr[value]; index_arr[value] = -1; data[index_arr[tail_value]] = tail_value; data.pop_back(); } } float get_time(bool init) { static std::chrono::system_clock::time_point start; if (init) { start = std::chrono::system_clock::now(); } std::chrono::system_clock::time_point end = std::chrono::system_clock::now(); return std::chrono::duration_cast(end - start).count(); // 処理に要した時間をミリ秒に変換 } double current_tmp(double current_time, double T0, double T1) { return T1 + (T0 - T1) * (TIME_LIMIT * 0.92 - current_time) / (TIME_LIMIT * 0.92); // double start_time = TIME_LIMIT * 0.6; // double x = (current_time - start_time) / (TIME_LIMIT * 0.32); // return pow(T1, 1 - x) + (T0, x); } bool is_valid_transition(int diff, double current_time, double T0, float T1) { float t = current_tmp(current_time, T0, T1); float rand = ro.get_float(); // diffが正だったら常にアクセぷと return rand < exp(((float)diff) / t); } class CityMap { private: int count_highway(int num); double cost_between(int x, int y, int z, int w); public: vector> horizontal_cost; vector> vertical_cost; CityMap(); void upgrade_road(int x, int y, int z, int w); int calculate_income(); }; CityMap::CityMap() { horizontal_cost = vector>(14, vector(13, 1)); vertical_cost = vector>(14, vector(13, 1)); } void CityMap::upgrade_road(int x, int y, int z, int w) { if (x == z) { // この時には横方向の道 int ymin = min(y, w); horizontal_cost.at(x - 1).at(ymin - 1) = 0.223; } else { int xmin = min(x, z); vertical_cost.at(y - 1).at(xmin - 1) = 0.223; } } double CityMap::cost_between(int x, int y, int z, int w) { if (x == z) { // この時には横方向の道 int ymin = min(y, w); return horizontal_cost.at(x - 1).at(ymin - 1); } else { int xmin = min(x, z); return vertical_cost.at(y - 1).at(xmin - 1); } } vector

dirs = {make_pair(1, 0), make_pair(-1, 0), make_pair(0, 1), make_pair(0, -1)}; int CityMap::count_highway(int num) { // dijkstra法で高速道路の数を調べる int x1 = A.at(num); int y1 = B.at(num); int x2 = C.at(num); int y2 = D.at(num); priority_queue, greater> pq; pq.emplace(0., 0, x1, y1); vector> cost_map(15, vector(15, pow(10, 9))); while (!pq.empty()) { double cost; int count, x, y; tie(cost, count, x, y) = pq.top(); pq.pop(); // cerr << x << " " << y << " " << cost << " " << count << endl; if (cost_map.at(x).at(y) <= cost) continue; cost_map.at(x).at(y) = cost; if (x == x2 && y == y2) { return count; } for (int i = 0; i < 4; i++) { int dx, dy; tie(dx, dy) = dirs.at(i); int xx = x + dx; int yy = y + dy; if (xx <= 0 || xx >= 15 || yy <= 0 || yy >= 15) continue; double add_cost = cost_between(x, y, xx, yy); if (cost_map.at(xx).at(yy) < 10000) continue; int count2 = count; if (add_cost < 0.5) count2++; pq.emplace(cost + add_cost, count2, xx, yy); } } throw runtime_error("dijkstra must reach answer"); } int CityMap::calculate_income() { // dijkstra法で各人のベストなルートを探して、通る高速道路の本数を計算する int result = 0; for (int i = 0; i < N; i++) { // cerr << "i=" << i << " " << result << endl; result += 60 * count_highway(i); } return result; } vector road_plan; void make_road_plan() { road_plan = vector(); int y0 = 2; int y1 = 5; // int y2 = 10; // int y3 = 13; for (int x = 3; x < 12; x++) { if ((x - 3) % 4 < 2) { road_plan.push_back(make_tuple(x, y1, x + 1, y1)); } else { road_plan.push_back(make_tuple(x, y0, x + 1, y0)); } } for (int y = y0; y < y1; y++) { road_plan.push_back(make_tuple(3, y, 3, y + 1)); road_plan.push_back(make_tuple(5, y, 5, y + 1)); road_plan.push_back(make_tuple(7, y, 7, y + 1)); road_plan.push_back(make_tuple(9, y, 9, y + 1)); road_plan.push_back(make_tuple(11, y, 11, y + 1)); road_plan.push_back(make_tuple(13, y, 13, y + 1)); } for (int y = y1; y < 13; y++) { road_plan.push_back(make_tuple(3, y, 3, y + 1)); road_plan.push_back(make_tuple(8, y, 8, y + 1)); road_plan.push_back(make_tuple(13, y, 13, y + 1)); } for (int y = 2; y < y0; y++) { // road_plan.push_back(make_tuple(3, y, 6, y + 1)); road_plan.push_back(make_tuple(6, y, 6, y + 1)); road_plan.push_back(make_tuple(10, y, 10, y + 1)); // road_plan.push_back(make_tuple(13, y, 10, y + 1)); } /**/ vector> tmp_road_plan; for (auto tmp : road_plan) { int x, y, z, w; tie(x, y, z, w) = tmp; int score = abs(7 - x) + abs(7 - y); // cerr << score << " " << x << " " << y << endl; tmp_road_plan.push_back(make_pair(score, tmp)); } road_plan.clear(); cerr << road_plan.size() << " " << tmp_road_plan.size() << endl; sort(tmp_road_plan.begin(), tmp_road_plan.end()); for (auto tmp : tmp_road_plan) { road_plan.push_back(tmp.second); } cerr << road_plan.size() << " " << tmp_road_plan.size() << endl; /* for (int y = 3; y < y0; y++) { road_plan.push_back(make_tuple(3, y, 3, y + 1)); road_plan.push_back(make_tuple(8, y, 8, y + 1)); road_plan.push_back(make_tuple(13, y, 13, y + 1)); } for (int y = y1; y < 13; y++) { road_plan.push_back(make_tuple(8, y, 8, y + 1)); } */ /* for (int y = y2; y < y3; y++) { road_plan.push_back(make_tuple(3, y, 3, y + 1)); road_plan.push_back(make_tuple(5, y, 5, y + 1)); road_plan.push_back(make_tuple(7, y, 7, y + 1)); road_plan.push_back(make_tuple(9, y, 9, y + 1)); road_plan.push_back(make_tuple(11, y, 11, y + 1)); road_plan.push_back(make_tuple(13, y, 13, y + 1)); } */ /* for (int y = 9; y < 12; y++) { road_plan.push_back(make_tuple(3, y, 3, y + 1)); road_plan.push_back(make_tuple(5, y, 5, y + 1)); road_plan.push_back(make_tuple(7, y, 7, y + 1)); road_plan.push_back(make_tuple(9, y, 9, y + 1)); road_plan.push_back(make_tuple(11, y, 11, y + 1)); road_plan.push_back(make_tuple(13, y, 13, y + 1)); } */ } int main() { #ifdef OPTUNA_STUDY cerr << "optuna study, override parameters" << endl; #endif get_time(true); cin >> N >> T; A = vec_int(N); B = vec_int(N); C = vec_int(N); D = vec_int(N); rep(i, N) cin >> A.at(i) >> B.at(i) >> C.at(i) >> D.at(i); make_road_plan(); int a; int b; int supporter_count = 64; rep(i, supporter_count) { cin >> a >> b; cout << "2" << endl; } int turn = supporter_count; int cost_per_road = 1000 * 1000 * 10 / sqrt(supporter_count); // 1.25*10^6 int money = 1000 * 1000; CityMap city_map = CityMap(); int daily_income = 0; int road_ind = 0; int last_income_calculation = 0; while (turn < 300 && road_ind < road_plan.size()) { cin >> a >> b; // cerr << "turn:" << turn << " money:" << money << endl; #ifdef LOCAL #else if (a != money) { int diff = a - money; daily_income += diff; money = a; } #endif if (money >= cost_per_road) { int x, y, z, w; tie(x, y, z, w) = road_plan.at(road_ind); cout << "1 " << x << " " << y << " " << z << " " << w << endl; city_map.upgrade_road(x, y, z, w); #ifdef LOCAL if (turn > last_income_calculation) { daily_income = city_map.calculate_income(); last_income_calculation = turn; } #endif //} money -= cost_per_road; road_ind++; } else { money += 50000; cout << "3" << endl; } money += daily_income; turn++; } while (turn < 400) { cin >> a >> b; cout << "3" << endl; money += daily_income; money += 50000; turn++; } cerr << "score:" << money << endl; return 0; }