提出 #71292179

---

ソースコード 拡げる

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

// ===================== DSU with component velocities & members =====================
int FILL_NUM = 20;  // when remaining singletons <= this, use exact assignment (min-cost flow)

struct DSU {
    int n;
    vector<int> parent, sz;
    vector<double> vx, vy;                 // velocity of each root component
    vector<vector<int>> members;           // explicit members list per root

    DSU(int n_ = 0) { init(n_); }

    void init(int n_) {
        n = n_;
        parent.resize(n);
        sz.assign(n, 1);
        vx.assign(n, 0.0);
        vy.assign(n, 0.0);
        members.assign(n, {});
        iota(parent.begin(), parent.end(), 0);
        for (int i = 0; i < n; ++i) {
            members[i].clear();
            members[i].push_back(i);
        }
    }

    int find(int x) {
        if (parent[x] == x) return x;
        return parent[x] = find(parent[x]);
    }

    // merge components of a and b, velocities are updated by momentum conservation
    int unite(int a, int b) {
        int ra = find(a);
        int rb = find(b);
        if (ra == rb) return ra;
        if (sz[ra] < sz[rb]) swap(ra, rb); // ra is new root

        parent[rb] = ra;

        // momentum conservation
        double total = (double)sz[ra] + (double)sz[rb];
        double new_vx = (vx[ra] * sz[ra] + vx[rb] * sz[rb]) / total;
        double new_vy = (vy[ra] * sz[ra] + vy[rb] * sz[rb]) / total;
        vx[ra] = new_vx;
        vy[ra] = new_vy;

        // merge members list
        if (!members[rb].empty()) {
            members[ra].insert(members[ra].end(), members[rb].begin(), members[rb].end());
            members[rb].clear();
        }

        sz[ra] += sz[rb];
        return ra;
    }
};

// ===================== Global state =====================

int N_, T_, M_, K_, L_;
double Ld; // L as double

vector<double> posx, posy;        // current positions at global time t
vector<double> init_posx, init_posy;
vector<double> init_vx, init_vy;
DSU dsu;

// torus distance between two points i, j using current positions
inline double torus_dist2_points(int i, int j) {
    double dx = fabs(posx[i] - posx[j]);
    if (dx > Ld - dx) dx = Ld - dx;
    double dy = fabs(posy[i] - posy[j]);
    if (dy > Ld - dy) dy = Ld - dy;
    return dx * dx + dy * dy;
}

// move all points forward by 1 step according to current component velocities
void move_all_1() {
    for (int i = 0; i < N_; ++i) {
        int r = dsu.find(i);
        posx[i] += dsu.vx[r];
        posy[i] += dsu.vy[r];
        posx[i] = fmod(posx[i], Ld);
        if (posx[i] < 0) posx[i] += Ld;
        posy[i] = fmod(posy[i], Ld);
        if (posy[i] < 0) posy[i] += Ld;
    }
}

// find best dt in [0, maxH] when singleton s_root and cluster c_root are closest,
// approximating trajectories with current velocities and using the nearest member
// inside the cluster for the distance definition
struct MeetInfo {
    int dt;
    double d2;
    int member; // index of the closest member in the cluster
};

MeetInfo best_meet_time_single_cluster(int s_root, int c_root, int maxH) {
    // singleton root has exactly one member
    int s_idx;
    if (!dsu.members[s_root].empty()) {
        s_idx = dsu.members[s_root][0];
    } else {
        s_idx = s_root;
    }

    double vsx = dsu.vx[s_root];
    double vsy = dsu.vy[s_root];
    double vcx = dsu.vx[c_root];
    double vcy = dsu.vy[c_root];

    const vector<int>& cm = dsu.members[c_root];

    double best_d2 = 1e100;
    int best_dt = 0;
    int best_member = cm.empty() ? c_root : cm[0];

    for (int dt = 0; dt <= maxH; ++dt) {
        // singleton position after dt steps
        double sx = posx[s_idx] + vsx * dt;
        double sy = posy[s_idx] + vsy * dt;
        sx = fmod(sx, Ld);
        if (sx < 0) sx += Ld;
        sy = fmod(sy, Ld);
        if (sy < 0) sy += Ld;

        double local_best = 1e100;
        int local_member = cm.empty() ? c_root : cm[0];

        if (!cm.empty()) {
            // check all members in the cluster
            for (int p : cm) {
                double cx = posx[p] + vcx * dt;
                double cy = posy[p] + vcy * dt;
                cx = fmod(cx, Ld);
                if (cx < 0) cx += Ld;
                cy = fmod(cy, Ld);
                if (cy < 0) cy += Ld;

                double dx = fabs(sx - cx);
                if (dx > Ld - dx) dx = Ld - dx;
                double dy = fabs(sy - cy);
                if (dy > Ld - dy) dy = Ld - dy;
                double d2 = dx * dx + dy * dy;
                if (d2 < local_best) {
                    local_best = d2;
                    local_member = p;
                }
            }
        } else {
            // fallback: use the root index itself
            double cx = posx[c_root] + vcx * dt;
            double cy = posy[c_root] + vcy * dt;
            cx = fmod(cx, Ld);
            if (cx < 0) cx += Ld;
            cy = fmod(cy, Ld);
            if (cy < 0) cy += Ld;
            double dx = fabs(sx - cx);
            if (dx > Ld - dx) dx = Ld - dx;
            double dy = fabs(sy - cy);
            if (dy > Ld - dy) dy = Ld - dy;
            local_best = dx * dx + dy * dy;
            local_member = c_root;
        }

        if (local_best < best_d2) {
            best_d2 = local_best;
            best_dt = dt;
            best_member = local_member;
        }
    }
    MeetInfo res;
    res.dt = best_dt;
    res.d2 = best_d2;
    res.member = best_member;
    return res;
}

// グローバル DP スケジューリング（min-cost flow）
// cost_sum に実際の結合コスト D を加算するように修正
void run_global_schedule(int t_start,
                         const vector<int>& cluster_roots_in,
                         const vector<int>& single_roots_in,
                         vector<tuple<int,int,int>>& answers,
                         int& merges_done,
                         int merges_needed,
                         long long &cost_sum) {
    int horizon = max(0, T_ - 1 - t_start);
    if (horizon <= 0) return;
    if (single_roots_in.empty()) return;
    if (cluster_roots_in.empty()) return;

    // Recompute current roots for clusters and singles (just in case)
    vector<int> cluster_roots;
    for (int cr : cluster_roots_in) {
        int r = dsu.find(cr);
        if (dsu.sz[r] > 0) {
            cluster_roots.push_back(r);
        }
    }
    vector<int> single_roots;
    for (int sr : single_roots_in) {
        int r = dsu.find(sr);
        if (dsu.sz[r] == 1) {
            single_roots.push_back(r);
        }
    }
    if (single_roots.empty() || cluster_roots.empty()) return;

    int C = (int)cluster_roots.size();
    int S = (int)single_roots.size();

    // capacities for clusters
    vector<int> cap(C);
    int total_cap = 0;
    for (int ci = 0; ci < C; ++ci) {
        int r = dsu.find(cluster_roots[ci]);
        int c = max(0, K_ - dsu.sz[r]);
        cap[ci] = c;
        total_cap += c;
    }
    if (total_cap < S) {
        // not enough capacity to absorb all singles; just cap at total_cap
        S = total_cap;
        if (S == 0) return;
    }

    // Precompute best (dt, d2, member) for each pair (single, cluster)
    vector<vector<int>> best_dt(S, vector<int>(C, 0));
    vector<vector<double>> best_d2(S, vector<double>(C, 0.0));
    vector<vector<int>> best_rep(S, vector<int>(C, -1));
    for (int si = 0; si < S; ++si) {
        int sr = single_roots[si];
        for (int ci = 0; ci < C; ++ci) {
            int cr = cluster_roots[ci];
            MeetInfo res = best_meet_time_single_cluster(sr, cr, horizon);
            best_dt[si][ci] = res.dt;
            best_d2[si][ci] = res.d2;
            best_rep[si][ci] = res.member;
        }
    }

    // Min-cost flow construction
    struct Edge {
        int to, rev, cap;
        long long cost;
    };
    int Nnode = 2 + S + C; // source + sink + singles + clusters
    int SRC = 0;
    int SNK = Nnode - 1;
    int SINGLE_BASE = 1;
    int CLUSTER_BASE = 1 + S;

    vector<vector<Edge>> g(Nnode);

    auto add_edge = [&](int fr, int to, int cap, long long cost) {
        Edge fwd{to, (int)g[to].size(), cap, cost};
        Edge rev{fr, (int)g[fr].size(), 0, -cost};
        g[fr].push_back(fwd);
        g[to].push_back(rev);
    };

    const long long INF_LL = (1LL << 60);

    // source -> singles
    for (int si = 0; si < S; ++si) {
        int sn = SINGLE_BASE + si;
        add_edge(SRC, sn, 1, 0);
    }

    // singles -> clusters
    for (int si = 0; si < S; ++si) {
        int sn = SINGLE_BASE + si;
        for (int ci = 0; ci < C; ++ci) {
            int cn = CLUSTER_BASE + ci;
            // min-cost flow の cost は d^2 の整数丸め
            long long cost = (long long)llround(best_d2[si][ci]);
            add_edge(sn, cn, 1, cost);
        }
    }

    // clusters -> sink
    for (int ci = 0; ci < C; ++ci) {
        int cn = CLUSTER_BASE + ci;
        add_edge(cn, SNK, cap[ci], 0);
    }

    // Successive shortest augmenting path with potentials
    vector<long long> h(Nnode, 0), dist(Nnode);
    vector<int> prevv(Nnode), preve(Nnode);

    int flow = 0;
    int max_flow = S; // we try to assign all singles (or as many as capacity)

    while (flow < max_flow) {
        fill(dist.begin(), dist.end(), INF_LL);
        dist[SRC] = 0;
        using P = pair<long long,int>;
        priority_queue<P, vector<P>, greater<P>> pq;
        pq.emplace(0, SRC);
        while (!pq.empty()) {
            auto [d, v] = pq.top();
            pq.pop();
            if (dist[v] < d) continue;
            for (int i = 0; i < (int)g[v].size(); ++i) {
                Edge &e = g[v][i];
                if (e.cap > 0) {
                    long long nd = d + e.cost + h[v] - h[e.to];
                    if (nd < dist[e.to]) {
                        dist[e.to] = nd;
                        prevv[e.to] = v;
                        preve[e.to] = i;
                        pq.emplace(nd, e.to);
                    }
                }
            }
        }
        if (dist[SNK] == INF_LL) break; // cannot add more

        for (int v = 0; v < Nnode; ++v) {
            if (dist[v] < INF_LL) h[v] += dist[v];
        }

        int d = max_flow - flow;
        for (int v = SNK; v != SRC; v = prevv[v]) {
            d = min(d, g[prevv[v]][preve[v]].cap);
        }
        flow += d;
        for (int v = SNK; v != SRC; v = prevv[v]) {
            Edge &e = g[prevv[v]][preve[v]];
            e.cap -= d;
            g[v][e.rev].cap += d;
        }
    }

    // Recover assignment: for each single node, find which cluster edge has flow
    vector<int> assign(S, -1);
    for (int si = 0; si < S; ++si) {
        int sn = SINGLE_BASE + si;
        for (auto &e : g[sn]) {
            if (e.to >= CLUSTER_BASE && e.to < CLUSTER_BASE + C) {
                int ci = e.to - CLUSTER_BASE;
                // original capacity was 1; if cap == 0, we used this edge
                if (e.cap == 0) {
                    assign[si] = ci;
                    break;
                }
            }
        }
    }

    // Build schedule events: time -> list of (single_root, cluster_member)
    vector<vector<pair<int,int>>> schedule(T_);
    for (int si = 0; si < S; ++si) {
        int ci = assign[si];
        if (ci < 0) continue;
        int sr = single_roots[si];
        int rep = best_rep[si][ci];
        if (rep < 0) continue;
        int dt = best_dt[si][ci];
        int t_merge = t_start + dt;
        if (t_merge < t_start) t_merge = t_start;
        if (t_merge >= T_) t_merge = T_ - 1;
        schedule[t_merge].push_back({sr, rep});
    }

    // Simulate from t_start to T_-1, performing merges according to schedule
    int t = t_start;
    for (; t < T_ && merges_done < merges_needed; ++t) {
        for (auto &pr : schedule[t]) {
            int s_root_seed = pr.first;     // singleton representative
            int rep_seed = pr.second;       // specific member in the cluster picked in DP

            int rs = dsu.find(s_root_seed);
            if (dsu.sz[rs] != 1) continue;  // no longer a singleton

            int rr = dsu.find(rep_seed);
            int rcr = rr;                   // cluster root after find
            if (dsu.sz[rcr] >= K_) continue; // cluster already full
            if (dsu.sz[rs] + dsu.sz[rcr] > K_) continue; // would exceed K

            if (rs == rr) continue;         // already in the same component

            // 実際の結合コストを計算
            double d2 = torus_dist2_points(s_root_seed, rep_seed);
            long long D = (long long)llround(d2);
            cost_sum += D;

            // merge this singleton into the cluster via the chosen member
            dsu.unite(s_root_seed, rep_seed);
            answers.emplace_back(t, s_root_seed, rep_seed);
            merges_done++;
            if (merges_done >= merges_needed) break;
        }
        if (t < T_ - 1) move_all_1();
        if (merges_done >= merges_needed) break;
    }
}

// ===================== 1 回分の貪欲＋DP を解く関数 =====================

long long solve_once(vector<tuple<int,int,int>>& answers, unsigned long long seed) {
    // 乱数
    std::mt19937_64 rng(seed);

    // 状態リセット
    posx = init_posx;
    posy = init_posy;
    dsu.init(N_);
    for (int i = 0; i < N_; ++i) {
        dsu.vx[i] = init_vx[i];
        dsu.vy[i] = init_vy[i];
    }

    const int merges_needed = N_ - M_;
    int merges_done = 0;
    long long cost_sum = 0;
    answers.clear();
    answers.reserve(merges_needed);

    // ===================== Phase 0: choose M_ core points (乱択あり) =====================
    // farthest-point sampling on initial positions to get well-separated seeds

    vector<int> core_points;
    core_points.reserve(M_);
    vector<char> used(N_, 0);

    // First core: ランダムな点
    int first = (int)(rng() % (unsigned long long)N_);
    core_points.push_back(first);
    used[first] = 1;

    const int TOP_K = 20;
    while ((int)core_points.size() < M_) {
        vector<pair<double, int>> cand;
        for (int i = 0; i < N_; ++i) {
            if (used[i]) continue;
            double mind2 = 1e100;
            for (int c : core_points) {
                double d2 = torus_dist2_points(i, c);
                if (d2 < mind2) mind2 = d2;
            }
            cand.emplace_back(mind2, i);
        }
        if (cand.empty()) break;
        // Sort by decreasing mind2
        std::sort(cand.begin(), cand.end(), [](const pair<double,int>& a, const pair<double,int>& b){
            return a.first > b.first;
        });
        int top = std::min(TOP_K, (int)cand.size());
        int idx = (int)(rng() % (unsigned long long)top);
        int chosen = cand[idx].second;
        used[chosen] = 1;
        core_points.push_back(chosen);
    }

    // mark core points so they are not treated as singletons
    vector<char> is_core(N_, 0);
    for (int c : core_points) is_core[c] = 1;

    // ===================== Greedy + scheduled merging =====================

    const int SCHED_THRESHOLD = 80;   // （今は使っていないが残しておく）
    const int H_SCHED = 25;          // look-ahead horizon in steps for scheduling

    bool waited_last_turn = false;
    int t = 0;
    while (t < T_ && merges_done < merges_needed) {
        // Collect all current roots
        vector<int> roots;
        roots.reserve(N_);
        for (int i = 0; i < N_; ++i) {
            if (dsu.find(i) == i) roots.push_back(i);
        }

        // Separate cluster roots and singleton roots
        vector<int> cluster_roots;
        vector<int> single_roots;
        cluster_roots.reserve(M_);

        // clusters: components that contain a core, or size > 1
        // singletons: size == 1 and not core

        vector<char> is_cluster_root(N_, 0);
        for (int cp : core_points) {
            int r = dsu.find(cp);
            if (!is_cluster_root[r]) {
                is_cluster_root[r] = 1;
                cluster_roots.push_back(r);
            }
        }

        for (int r : roots) {
            if (is_cluster_root[r]) continue;
            if (dsu.sz[r] == 1 && !is_core[r]) {
                single_roots.push_back(r);
            }
        }

        int singles_cnt = (int)single_roots.size();
        if (singles_cnt > 0) {
            // compute remaining capacity across clusters
            int total_cap = 0;
            for (int cr : cluster_roots) {
                int r = dsu.find(cr);
                int c = max(0, K_ - dsu.sz[r]);
                total_cap += c;
            }

            // if the remaining singleton count exactly matches remaining capacity,
            // and is small enough, run exact assignment (min-cost flow)
            if (singles_cnt <= FILL_NUM && singles_cnt == total_cap && (T_ - t) > 1) {
                run_global_schedule(t, cluster_roots, single_roots,
                                    answers, merges_done, merges_needed, cost_sum);
                // after global exact scheduling,終わり
                break;
            }
        }

        // If no singletons left, nothing more to do except advance
        if (single_roots.empty()) {
            move_all_1();
            ++t;
            continue;
        }

        // 今は中盤の look-ahead スケジューリングは使わず、シンプル貪欲のみ
        bool use_schedule = false;
        if (!use_schedule) {
            // ---------- Phase 1: simple greedy at current time ----------
            int cluster_min_sz = INT_MAX;
            for (int cr : cluster_roots) {
                int rcr = dsu.find(cr);
                if (dsu.sz[rcr] < cluster_min_sz) cluster_min_sz = dsu.sz[rcr];
            }
            if (cluster_min_sz == INT_MAX) cluster_min_sz = 1;
            const double ALPHA_BAL = 1.5;

            double best_eff_cost = 1e100;
            int best_single = -1;
            int best_cluster_root = -1;
            int best_rep_in_cluster = -1;

            for (int sr : single_roots) {
                int single_idx = sr;
                for (int cr : cluster_roots) {
                    int rcr = dsu.find(cr);
                    if (dsu.sz[rcr] >= K_) continue; // cluster already full

                    double local_best = 1e100;
                    int rep = -1;
                    for (int p : dsu.members[rcr]) {
                        double d2 = torus_dist2_points(single_idx, p);
                        if (d2 < local_best) {
                            local_best = d2;
                            rep = p;
                        }
                    }
                    if (rep == -1) continue;

                    int szc = dsu.sz[rcr];
                    double bal = 0.0;
                    if (K_ > cluster_min_sz) {
                        bal = (double)(szc - cluster_min_sz) / (double)(K_ - cluster_min_sz);
                        if (bal < 0.0) bal = 0.0;
                    }
                    double eff_cost = local_best * (1.0 + ALPHA_BAL * bal);

                    if (eff_cost < best_eff_cost) {
                        best_eff_cost = eff_cost;
                        best_single = single_idx;
                        best_cluster_root = rcr;
                        best_rep_in_cluster = rep;
                    }
                }
            }

            if (best_single != -1 && best_rep_in_cluster != -1) {
                int rs = dsu.find(best_single);
                int rr = dsu.find(best_rep_in_cluster);
                int rc = dsu.find(best_cluster_root);
                if (rs != rr && dsu.sz[rc] < K_) {
                    // ---- WAIT LOGIC INSERTED HERE ----
                    // d2_now = current distance
                    double d2_now = torus_dist2_points(best_single, best_rep_in_cluster);

                    // compute best 1-turn-ahead distance
                    // temp-move all points by 1 step, compute distance, then revert
                    vector<double> save_x = posx, save_y = posy;
                    vector<double> save_vx = dsu.vx, save_vy = dsu.vy;

                    // move all once
                    for (int i = 0; i < N_; ++i) {
                        int r = dsu.find(i);
                        posx[i] += dsu.vx[r];
                        posy[i] += dsu.vy[r];
                        posx[i] = fmod(posx[i], Ld); if (posx[i] < 0) posx[i] += Ld;
                        posy[i] = fmod(posy[i], Ld); if (posy[i] < 0) posy[i] += Ld;
                    }

                    double d2_next = torus_dist2_points(best_single, best_rep_in_cluster);

                    // revert positions
                    posx = save_x; posy = save_y;
                    dsu.vx = save_vx; dsu.vy = save_vy;

                    const double EPS_WAIT = 1e-9;
                    bool should_wait = (!waited_last_turn && (t + 1 < T_) && (d2_next + EPS_WAIT < d2_now));

                    if (should_wait) {
                        // wait exactly one turn: do not merge this turn
                        waited_last_turn = true;
                    } else {
                        waited_last_turn = false;
                        long long D = (long long)llround(d2_now);
                        cost_sum += D;
                        dsu.unite(best_single, best_rep_in_cluster);
                        answers.emplace_back(t, best_single, best_rep_in_cluster);
                        ++merges_done;
                    }
                }
            }

            move_all_1();
            ++t;
            continue;
        }

        // ---------- Phase 2: scheduling with look-ahead ----------
        int maxH = min(H_SCHED, T_ - 1 - t);
        if (maxH <= 0) {
            move_all_1();
            ++t;
            continue;
        }

        int cluster_min_sz = INT_MAX;
        for (int cr : cluster_roots) {
            int rcr = dsu.find(cr);
            if (dsu.sz[rcr] < cluster_min_sz) cluster_min_sz = dsu.sz[rcr];
        }
        if (cluster_min_sz == INT_MAX) cluster_min_sz = 1;
        const double ALPHA_BAL2 = 1.5;

        double best_eff_cost2 = 1e100;
        int best_single2 = -1;
        int best_cluster_root2 = -1;
        int best_dt = 0;

        for (int sr : single_roots) {
            for (int cr : cluster_roots) {
                int rcr = dsu.find(cr);
                if (dsu.sz[rcr] >= K_) continue;
                auto res = best_meet_time_single_cluster(sr, rcr, maxH);
                int dt = res.dt;
                double d2 = res.d2;

                int szc = dsu.sz[rcr];
                double bal = 0.0;
                if (K_ > cluster_min_sz) {
                    bal = (double)(szc - cluster_min_sz) / (double)(K_ - cluster_min_sz);
                    if (bal < 0.0) bal = 0.0;
                }
                double eff_cost = d2 * (1.0 + ALPHA_BAL2 * bal);

                if (eff_cost < best_eff_cost2) {
                    best_eff_cost2 = eff_cost;
                    best_single2 = sr;
                    best_cluster_root2 = rcr;
                    best_dt = dt;
                }
            }
        }

        if (best_single2 == -1 || best_cluster_root2 == -1) {
            move_all_1();
            ++t;
            continue;
        }

        for (int step = 0; step < best_dt; ++step) {
            move_all_1();
        }
        t += best_dt;

        int rs2 = dsu.find(best_single2);
        int rcr2 = dsu.find(best_cluster_root2);
        if (dsu.sz[rcr2] >= K_) {
            continue;
        }

        double local_best2 = 1e100;
        int rep2 = -1;
        for (int p : dsu.members[rcr2]) {
            double d2 = torus_dist2_points(best_single2, p);
            if (d2 < local_best2) {
                local_best2 = d2;
                rep2 = p;
            }
        }

        if (rep2 != -1) {
            int rr2 = dsu.find(rep2);
            rs2 = dsu.find(best_single2);
            if (rs2 != rr2 && dsu.sz[rcr2] < K_) {
                double d2 = torus_dist2_points(best_single2, rep2);
                long long D = (long long)llround(d2);
                cost_sum += D;

                dsu.unite(best_single2, rep2);
                answers.emplace_back(t, best_single2, rep2);
                ++merges_done;
            }
        }
    }

    // answers が N-M 未満でも、とりあえず cost_sum は返す
    return cost_sum;
}

// ===================== main: 乱択リスタート =====================

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

    if (!(cin >> N_ >> T_ >> M_ >> K_ >> L_)) {
        return 0;
    }
    Ld = (double)L_;

    vector<int> ix(N_), iy(N_), ivx(N_), ivy(N_);
    for (int i = 0; i < N_; ++i) {
        cin >> ix[i] >> iy[i] >> ivx[i] >> ivy[i];
    }

    init_posx.assign(N_, 0.0);
    init_posy.assign(N_, 0.0);
    init_vx.assign(N_, 0.0);
    init_vy.assign(N_, 0.0);
    for (int i = 0; i < N_; ++i) {
        init_posx[i] = (double)ix[i];
        init_posy[i] = (double)iy[i];
        init_vx[i] = (double)ivx[i];
        init_vy[i] = (double)ivy[i];
    }

    posx = init_posx;
    posy = init_posy;
    dsu.init(N_);
    for (int i = 0; i < N_; ++i) {
        dsu.vx[i] = init_vx[i];
        dsu.vy[i] = init_vy[i];
    }

    using Clock = std::chrono::steady_clock;
    auto time_start = Clock::now();
    const double TIME_LIMIT = 1.8; // 秒

    std::mt19937_64 rng_global(1234567);

    long long best_cost = (1LL << 60);
    vector<tuple<int,int,int>> best_ans;

    vector<int> fill_candidates = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
    while (true) {
        auto now = Clock::now();
        double elapsed = std::chrono::duration<double>(now - time_start).count();
        if (elapsed > TIME_LIMIT) break;
        for (int f : fill_candidates) {
            auto now2 = Clock::now();
            double elapsed2 = std::chrono::duration<double>(now2 - time_start).count();
            if (elapsed2 > TIME_LIMIT) break;
            FILL_NUM = f;
            vector<tuple<int,int,int>> cur_ans;
            unsigned long long seed = rng_global();   // クラスタ初期点の乱択用 seed
            long long cur_cost = solve_once(cur_ans, seed);
            if (!cur_ans.empty() && cur_cost < best_cost) {
                best_cost = cur_cost;
                best_ans = cur_ans;
            }
        }
    }

    // もし best_ans が空なら、最後に 1 回 deterministic に解く
    if (best_ans.empty()) {
        vector<tuple<int,int,int>> cur_ans;
        long long cur_cost = solve_once(cur_ans, 1);
        best_ans = cur_ans;
    }

    for (auto &tp : best_ans) {
        int tt, a, b;
        tie(tt, a, b) = tp;
        if (tt < 0) tt = 0;
        if (tt >= T_) tt = T_ - 1;
        if (a < 0 || a >= N_ || b < 0 || b >= N_ || a == b) continue;
        cout << tt << ' ' << a << ' ' << b << '\n';
    }

    return 0;
}

提出情報

コンパイルエラー

./Main.cpp:467:15: warning: unused variable 'SCHED_THRESHOLD' [-Wunused-variable]
  467 |     const int SCHED_THRESHOLD = 80;   // （今は使っていないが残しておく）
      |               ^~~~~~~~~~~~~~~
./Main.cpp:792:19: warning: unused variable 'cur_cost' [-Wunused-variable]
  792 |         long long cur_cost = solve_once(cur_ans, 1);
      |                   ^~~~~~~~
2 warnings generated.

ジャッジ結果