#1149339 (C++17(clang)) No.5023 Airlines Optimization

• 問題: No.5023 Airlines Optimization
• ユーザー: Pechi
• 提出日時: 2026-02-25 22:57:29
• 言語: C++17(clang) (clang++ 21.1.8 + boost 1.89.0)
• 結果: AC
• 実行時間: 4 ms / 1,000 ms
• コード長: 4,922 bytes
• コンパイル時間: 8,871 ms
• コンパイル使用メモリ: 192,048 KB
• 実行使用メモリ: 7,848 KB
• スコア: 36,172,081
• 最終ジャッジ日時: 2026-02-25 22:57:43
• 合計ジャッジ時間: 11,910 ms
• ジャッジサーバーID （参考情報）: judge3 / judge4

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

ソースコード

#define _USE_MATH_DEFINES
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;

#ifdef _MSC_VER
inline unsigned long long __builtin_ctzll(unsigned long long x) { unsigned long r; _BitScanForward64(&r, x); return r; }
inline unsigned long long __builtin_clzll(unsigned long long x) { unsigned long r; _BitScanReverse64(&r, x); return 63 - r; }
inline unsigned long long __builtin_ffsll(unsigned long long x) { unsigned long r; return _BitScanForward64(&r, x) ? r + 1 : 0; }
inline unsigned long long __builtin_popcountll(unsigned long long x) { return __popcnt64(x); }
#endif // _MSC_VER

#define LP(I,S,G) for (long long int I = (S); I < (G); ++I)
#define IN(X) 	for (int in = 0; in < X.size(); in++)cin >> X[in]
#define OUT(X) 	for (int in = 0; in < X.size(); in++)cout << X[in]<<" "
#define SORT(X) sort((X).begin(), (X).end())
#define CSORT(X,Y) sort(X.begin(), X.end(),Y)
#define COPY(X,Y) copy(X.begin(), X.end(), Y.begin())
#define ALL(X,Y) for (auto (X) :(Y))
#define FULL(a)  (a).begin(),(a).end()
#define BFS(Q,S) for(Q.push(S);Q.size()!=0;Q.pop())
typedef long long int ll;
typedef unsigned long long int ull;
long long int M = 998244353;

chrono::system_clock::time_point starttime;
using namespace std::chrono;
using namespace atcoder;
#ifndef ONLINE_JUDGE
#define DEBUG
#endif

inline float getTime() {
#ifdef DEBUG
    return duration_cast<milliseconds>(system_clock::now() - starttime).count() / 2;
#else
    return duration_cast<milliseconds>(system_clock::now() - starttime).count();
#endif
}


int dx[] = { -1,0,1,0 }, dy[] = { 0,1,0,-1 };
inline long long int xor128() {
    static long long int x = 123456789, y = 362436069, z = 521288629, w = 88675123;
    long long int t = (x ^ (x << 11));
    x = y; y = z; z = w;
    return (w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)));
}


mt19937_64 rnd;
struct Solver {
    int n, r, m, k;
    int plan_size = 10;
    vector<ll> x, y, w;
    vector<vector<array<int, 3>>> g;
    vector<vector<int>> dist;
    vector<vector<array<int, 4>>> plan;

    string convert(int t) {
        string a = to_string(t / 12 + 6);
        if (a.size() == 1)a = "0" + a;
        string b = to_string((t % 12) * 5);
        if (b.size() == 1)b = "0" + b;
        return a + ":" + b;
    }

    int convert(string s) {
        int a = stoi(string(s.begin(), s.begin() + 2)) - 6;
        int b = stoi(string(s.begin() + 3, s.end())) / 5;
        return a * 12 + b;
    }

    void init_dist() {
        dist = vector<vector<int>>(n, vector<int>(n));
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                double d = sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]));
                dist[i][j] = ((int)ceil(3 * d / 40 + 40) + 4) / 5;
            }
        }
    }

    Solver() {
        cin >> n >> r;
        g = vector<vector<array<int, 3>>>(n);
        x = vector<ll>(n);
        y = vector<ll>(n);
        w = vector<ll>(n);
        for (int i = 0; i < n; ++i)cin >> x[i] >> y[i] >> w[i];
        cin >> m;
        for (int i = 0; i < m; ++i) {
            int a, b;
            string s, t;
            cin >> a >> s >> b >> t;
            --a, --b;
            g[a].push_back({ b,convert(s),convert(t) });
        }
        cin >> k;
        init_dist();
    }

    vector<array<int, 4>> make_plan(int u,int v,int c,int base) {
        deque<array<int, 4>> q;
        int now = base;
        int end = 180;
        int idx = 0;
        vector<int> route = { c,u,v };
        while (now < end) {
            int n_idx = (idx + 1) % 3;
            int next = now + dist[route[idx]][route[n_idx]];
            if (next >= end)break;
            q.push_back({ route[idx],now,route[n_idx],next });
            now = next;
            idx = n_idx;
        }
        now = base;
        idx = 0;
        while (now > 0) {
            int n_idx = (idx + 2) % 3;
            int next = now - dist[route[idx]][route[n_idx]];
            if (next < 0)break;
            q.push_front({ route[n_idx] ,next,route[idx],now });
            now = next;
            idx = n_idx;
        }
        return vector<array<int, 4>>(q.begin(), q.end());
    }


    void solve() {
        for (int i = 0; i < k; ++i) {
            int u = i + 12;
            int v = i % 11 + 1;
            int c = 0;
            plan.push_back(make_plan(u, v, c, convert("11:00")));
        }
    }

    void answer() {
        for (int i = 0; i < k; ++i) {
            cout << plan[i].size() << "\n";
            for (auto act : plan[i]) {
                cout << act[0] + 1 << " " << convert(act[1]) << " " << act[2] + 1 << " " << convert(act[3]) << "\n";
            }
        }
    }

};

int main(int argc, char* argv[]) {
    starttime = chrono::system_clock::now();
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    Solver s;
    s.solve();
    s.answer();
    exit(0);
}