#1149444 (C++23) No.5023 Airlines Optimization

• 問題: No.5023 Airlines Optimization
• ユーザー: Shymohn _
• 提出日時: 2026-02-26 00:05:06
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 3 ms / 1,000 ms
• コード長: 3,614 bytes
• コンパイル時間: 3,711 ms
• コンパイル使用メモリ: 356,144 KB
• 実行使用メモリ: 7,844 KB
• スコア: 12,305,566
• 最終ジャッジ日時: 2026-02-26 00:05:23
• 合計ジャッジ時間: 8,881 ms
• ジャッジサーバーID （参考情報）: judge4 / judge2

ファイルパターン	結果
other	AC * 100

ソースコード

#include <bits/stdc++.h>
using namespace std;

int timeStrToMin(const string &s) {
    int h = stoi(s.substr(0,2));
    int m = stoi(s.substr(3,2));
    return h * 60 + m;
}

string minToTimeStr(int t) {
    int h = t / 60;
    int m = t % 60;
    char buf[6];
    snprintf(buf, sizeof(buf), "%02d:%02d", h, m);
    return string(buf);
}

int flightDurationMin(double x1, double y1, double x2, double y2) {
    double dx = x1 - x2;
    double dy = y1 - y2;
    double d = sqrt(dx*dx + dy*dy);
    double raw = 60.0 * d / 800.0 + 40.0;
    int dur = (int)ceil(raw / 5.0) * 5;
    return dur;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    int R;
    if (!(cin >> N >> R)) return 0;
    vector<pair<double,double>> coords(N);
    vector<long long> pops(N);
    for (int i = 0; i < N; ++i) {
        double x, y;
        long long w;
        cin >> x >> y >> w;
        coords[i] = {x, y};
        pops[i] = w;
    }
    int M;
    cin >> M;
    // read and ignore Square airline flights (we don't use them here)
    for (int i = 0; i < M; ++i) {
        int a, b;
        string s, t;
        cin >> a >> s >> b >> t;
        (void)a; (void)s; (void)b; (void)t;
    }
    int K;
    cin >> K;

    const int DAY_START = 6 * 60;   // 06:00 = 360
    const int DAY_END   = 21 * 60;  // 21:00 = 1260

    // RNG (fixed seed for reproducibility)
    std::mt19937 rng(42);
    std::uniform_int_distribution<int> cityDist(1, max(1, N));

    // For each plane, build a sequence of flights
    vector<vector<tuple<int,int,int,int>>> schedules; // per plane: list of (a, smin, b, tmin)
    schedules.reserve(K);

    for (int p = 0; p < K; ++p) {
        vector<tuple<int,int,int,int>> flights;
        if (N == 0) { schedules.push_back(flights); continue; }
        int cur_city = cityDist(rng); // 1..N
        int cur_time = DAY_START;

        while (true) {
            // pick next city different from cur_city (try a few times)
            int next_city = cityDist(rng);
            int tries = 0;
            while (next_city == cur_city && tries < 10 && N > 1) {
                next_city = cityDist(rng);
                ++tries;
            }
            if (next_city == cur_city) {
                // couldn't pick different city; break to avoid infinite loop
                break;
            }
            double x1 = coords[cur_city-1].first;
            double y1 = coords[cur_city-1].second;
            double x2 = coords[next_city-1].first;
            double y2 = coords[next_city-1].second;
            int dur = flightDurationMin(x1, y1, x2, y2);
            int depart = cur_time;
            int arrive = depart + dur;

            if (depart < DAY_START) {
                depart = DAY_START;
                arrive = depart + dur;
            }
            // if arrival would exceed DAY_END, stop adding flights
            if (arrive > DAY_END) break;

            flights.emplace_back(cur_city, depart, next_city, arrive);

            // update state: immediate departure allowed
            cur_city = next_city;
            cur_time = arrive;
            if (cur_time >= DAY_END) break;
        }
        schedules.push_back(flights);
    }

    // Output: for each plane, first the count c_i then c_i lines of "a s b t"
    for (const auto &flights : schedules) {
        cout << flights.size() << "\n";
        for (const auto &f : flights) {
            int a, smin, b, tmin;
            tie(a, smin, b, tmin) = f;
            cout << a << " " << minToTimeStr(smin) << " " << b << " " << minToTimeStr(tmin) << "\n";
        }
    }

    return 0;
}