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

• 問題: No.5023 Airlines Optimization
• ユーザー: 👑 wanui
• 提出日時: 2026-02-25 22:28:38
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 8 ms / 1,000 ms
• コード長: 4,716 bytes
• コンパイル時間: 4,912 ms
• コンパイル使用メモリ: 373,652 KB
• 実行使用メモリ: 7,844 KB
• スコア: 21,961,695
• 最終ジャッジ日時: 2026-02-25 22:29:42
• 合計ジャッジ時間: 10,141 ms
• ジャッジサーバーID （参考情報）: judge2 / judge6

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

ソースコード

#include <bits/stdc++.h>
// clang-format off
#ifdef ONLINE_JUDGE
const int LOCAL = 0;
const double CLOCK_RATIO = 1000;
#else
const int LOCAL = 1;
const double CLOCK_RATIO = 1400;
#endif

using namespace std;
using ull = unsigned long long;
using pii = pair<int,int>;
using ll = long long;
#define debug1(a) {if(LOCAL){cerr<<#a<<":"<<a<<endl; }}
#define debug2(a,b) {if(LOCAL){cerr<<#a<<":"<<a<<" "<<#b<<":"<<b<<endl; }}
#define debug3(a,b,c) {if(LOCAL){cerr<<#a<<":"<<a<<" "<<#b<<":"<<b<<" "<<#c<<":"<<c<<endl; }}
#define debug4(a,b,c,d) {if(LOCAL){cerr<<#a<<":"<<a<<" "<<#b<<":"<<b<<" "<<#c<<":"<<c<<" "<<#d<<":"<<d<<endl; }}
#define debug5(a,b,c,d,e) {if(LOCAL){cerr<<#a<<":"<<a<<" "<<#b<<":"<<b<<" "<<#c<<":"<<c<<" "<<#d<<":"<<d<<" "<<#e<<":"<<e<<endl; }}
// clang-format on

const int N = 47;
const double R = 1000;
const int M = 400;
const int K = 25;
vector<pair<double, double>> CITY_POS;
vector<ll> CITY_WEIGHT;
vector<vector<int>> FLIGHT_TIME;
vector<vector<pair<int, int>>> SQ_PLAN;

const int LIMIT_ARRIVE = 180;
namespace marathon {
std::mt19937 engine(0);
clock_t start_time;
double now() {
    return CLOCK_RATIO * (clock() - start_time) / CLOCKS_PER_SEC;
}
void marathon_init() {
    start_time = clock();
    std::random_device seed_gen;
    engine.seed(seed_gen());
}
}  // namespace marathon

namespace Solver {

class Solver {
   public:
    string datestr(int s) {
        s = s * 5 + 360;
        int h = s / 60;
        string res;
        if (h < 10) {
            res.push_back('0');
        }
        for (auto c : to_string(h)) {
            res.push_back(c);
        }
        res.push_back(':');
        int m = s % 60;
        if (m < 10) {
            res.push_back('0');
        }
        for (auto c : to_string(m)) {
            res.push_back(c);
        }
        return res;
    }
    void output(vector<vector<tuple<int, int, int, int>>> ans) {
        for (int k = 0; k < K; k++) {
            cout << ans[k].size() << endl;
            for (auto fl : ans[k]) {
                int a, b;
                int s, t;
                tie(a, s, b, t) = fl;
                cout << (a + 1) << " " << datestr(s) << " " << (b + 1) << " " << datestr(t) << endl;
            }
        }
    }
    void solve() {
        vector<pii> cities;
        for (int i = 0; i < N; i++) {
            cities.push_back({CITY_WEIGHT[i], i});
        }
        sort(cities.rbegin(), cities.rend());

        vector<vector<tuple<int, int, int, int>>> ans(K);

        for (int k = 0; k < K; k++) {
            int tim = 0;
            int cur = cities[k % 3].second;
            while (true) {
                int nxt = cur;
                while (cur == nxt) {
                    if (ans[k].size() % 2 == 0) {
                        nxt = cities[marathon::engine() % 15].second;
                    } else {
                        nxt = cities[marathon::engine() % 3].second;
                    }
                }
                if (tim + FLIGHT_TIME[cur][nxt] > LIMIT_ARRIVE) break;
                ans[k].push_back({cur, tim, nxt, tim + FLIGHT_TIME[cur][nxt]});
                tim = tim + FLIGHT_TIME[cur][nxt];
                cur = nxt;
            }
        }
        output(ans);
    }
};
}  // namespace Solver

int main() {
    marathon::marathon_init();

    CITY_POS.resize(N);
    CITY_WEIGHT.resize(N);
    SQ_PLAN.resize(N);
    FLIGHT_TIME = vector<vector<int>>(N, vector<int>(N));
    int n, r;
    cin >> n >> r;
    for (int i = 0; i < N; i++) {
        double x, y;
        int w;
        cin >> x >> y >> w;
        CITY_POS[i] = {x, y};
        CITY_WEIGHT[i] = w;
    }
    for (int s = 0; s < N; s++) {
        for (int t = 0; t < N; t++) {
            double sx, sy, tx, ty;
            tie(sx, sy) = CITY_POS[s];
            tie(tx, ty) = CITY_POS[t];
            double d = sqrt((sx - tx) * (sx - tx) + (sy - ty) * (sy - ty));
            double tim = 60 * d / 800 + 40;
            FLIGHT_TIME[s][t] = int((4.99999999 + tim) / 5);
        }
    }
    int m;
    cin >> m;
    for (int i = 0; i < M; i++) {
        int a, b;
        string s0, t0;
        cin >> a >> s0 >> b >> t0;
        a--;
        b--;

        int s = stoi(s0.substr(0, 2)) * 60 + stoi(s0.substr(3, 5)) - 360;
        assert(s >= 0 && s % 5 == 0);
        s /= 5;
        int t = stoi(t0.substr(0, 2)) * 60 + stoi(t0.substr(3, 5)) - 360;
        assert(t >= 0 && t % 5 == 0);
        t /= 5;
        assert(t <= LIMIT_ARRIVE);
        // debug4(s, s0, t, t0);
        // debug4(a, s, b, t);
        // debug3(FLIGHT_TIME[a][b], s, t);
        // assert(FLIGHT_TIME[a][b] + s == t);
        SQ_PLAN[a].push_back({s, b});
    }
    int k;
    cin >> k;
    Solver::Solver().solve();
    return 0;
}