#1149291 (C++17) No.5023 Airlines Optimization

• 問題: No.5023 Airlines Optimization
• ユーザー: さがかんすけ
• 提出日時: 2026-02-25 21:22:19
• 言語: C++17 (gcc 15.2.0 + boost 1.89.0)
• 結果: WA
• 実行時間: -
• コード長: 4,375 bytes
• コンパイル時間: 1,929 ms
• コンパイル使用メモリ: 134,092 KB
• 実行使用メモリ: 7,848 KB
• スコア: 0
• 最終ジャッジ日時: 2026-02-25 21:22:26
• 合計ジャッジ時間: 7,380 ms
• ジャッジサーバーID （参考情報）: judge3 / judge2

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

ソースコード

#include <algorithm>
#include <cmath>
#include <cstdint>
#include <iostream>
#include <numeric>
#include <vector>
using namespace std;
using ll = long long;

namespace {
constexpr int DAY_START = 6 * 60;
constexpr int DAY_END = 21 * 60;

struct Flight {
    int a;
    int s;
    int b;
    int t;
};

// 所要時間を5分単位で切り上げる
int calc_duration_min(double dist) {
    double raw = 60.0 * dist / 800.0 + 40.0;
    int q = (int)ceil(raw / 5.0 - 1e-12);
    return q * 5;
}

vector<Flight> build_shuttle_schedule(int hub, int spoke, int start_time, bool start_from_hub,
                                      const vector<vector<int>>& dur) {
    vector<Flight> out;
    int cur = start_from_hub ? hub : spoke;
    int nxt = start_from_hub ? spoke : hub;
    int tm = start_time;

    while (true) {
        int d = dur[cur][nxt];
        if (d <= 0) break;
        if (tm + d > DAY_END) break;
        out.push_back(Flight{cur + 1, tm, nxt + 1, tm + d});
        tm += d;
        swap(cur, nxt);
    }
    return out;
}
}  // namespace

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, R;
    cin >> N >> R;

    vector<int> x(N), y(N);
    vector<ll> w(N);
    for (int i = 0; i < N; ++i) {
        cin >> x[i] >> y[i] >> w[i];
    }

    int M;
    cin >> M;
    for (int i = 0; i < M; ++i) {
        int a, s, b, t;
        cin >> a >> s >> b >> t;
    }

    int K;
    cin >> K;

    vector<vector<int>> dur(N, vector<int>(N, 0));
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            if (i == j) continue;
            double dx = (double)x[i] - (double)x[j];
            double dy = (double)y[i] - (double)y[j];
            double d = sqrt(dx * dx + dy * dy);
            dur[i][j] = calc_duration_min(d);
        }
    }

    // 人口最大都市をハブにする
    int hub = 0;
    for (int i = 1; i < N; ++i) {
        if (w[i] > w[hub]) hub = i;
    }

    vector<int> spokes;
    spokes.reserve(N - 1);
    for (int i = 0; i < N; ++i) {
        if (i != hub) spokes.push_back(i);
    }

    // ハブからの距離も加味して重要度を作る
    vector<double> score(N, 0.0);
    for (int v : spokes) {
        double dx = (double)x[v] - (double)x[hub];
        double dy = (double)y[v] - (double)y[hub];
        double d = sqrt(dx * dx + dy * dy);
        score[v] = (double)w[v] * (1.0 + d / (double)R);
    }
    sort(spokes.begin(), spokes.end(), [&](int a, int b) {
        if (score[a] != score[b]) return score[a] > score[b];
        return w[a] > w[b];
    });

    int use_spokes = min((int)spokes.size(), min(K, 12));
    vector<int> alloc(use_spokes, 1);
    int remain = K - use_spokes;

    if (use_spokes > 0 && remain > 0) {
        vector<double> wt(use_spokes, 0.0), frac(use_spokes, 0.0);
        double sum_wt = 0.0;
        for (int i = 0; i < use_spokes; ++i) {
            wt[i] = sqrt(max(1.0, score[spokes[i]]));
            sum_wt += wt[i];
        }

        for (int i = 0; i < use_spokes; ++i) {
            double z = remain * wt[i] / sum_wt;
            int add = (int)floor(z);
            alloc[i] += add;
            remain -= add;
            frac[i] = z - add;
        }

        vector<int> ord(use_spokes);
        iota(ord.begin(), ord.end(), 0);
        sort(ord.begin(), ord.end(), [&](int a, int b) { return frac[a] > frac[b]; });
        for (int k = 0; k < remain; ++k) {
            alloc[ord[k % use_spokes]]++;
        }
    }

    vector<vector<Flight>> schedules(K);
    int plane_id = 0;

    for (int i = 0; i < use_spokes && plane_id < K; ++i) {
        int spoke = spokes[i];
        for (int j = 0; j < alloc[i] && plane_id < K; ++j) {
            int offset_slot = (i * 5 + j * 3) % 24;
            int start_time = DAY_START + offset_slot * 5;
            bool start_from_hub = ((i + j) % 2 == 0);
            schedules[plane_id] =
                build_shuttle_schedule(hub, spoke, start_time, start_from_hub, dur);
            plane_id++;
        }
    }

    // 余った機体は運航なし
    while (plane_id < K) {
        schedules[plane_id].clear();
        plane_id++;
    }

    for (int i = 0; i < K; ++i) {
        cout << schedules[i].size() << '\n';
        for (const auto& f : schedules[i]) {
            cout << f.a << ' ' << f.s << ' ' << f.b << ' ' << f.t << '\n';
        }
    }
    return 0;
}