Submission #71292134

---

Source Code Expand

// greedy_length_pref_merge.cpp
// Python 実装を忠実に C++ に翻訳したもの
#include <bits/stdc++.h>
using namespace std;

struct UF {
    int n;
    vector<int> p, rankv;
    UF(int n=0): n(n), p(n), rankv(n,0) { for (int i=0;i<n;i++) p[i]=i; }
    int find(int x){
        while (p[x] != x) {
            p[x] = p[p[x]];
            x = p[x];
        }
        return x;
    }
    int unite(int a, int b){
        int ra = find(a), rb = find(b);
        if (ra == rb) return ra;
        if (rankv[ra] < rankv[rb]) swap(ra, rb);
        p[rb] = ra;
        if (rankv[ra] == rankv[rb]) rankv[ra] ++;
        return ra;
    }
};

// utilities
inline double torus_dx(double a, double b, int L){
    double d = fabs(a - b);
    return (d <= L - d) ? d : (L - d);
}
inline double torus_dist2_xy(double ax, double ay, double bx, double by, int L){
    double dx = torus_dx(ax, bx, L);
    double dy = torus_dx(ay, by, L);
    return dx*dx + dy*dy;
}

// subset-sum reconstruct indices (returns vector of indices into given sizes), or empty if no solution
vector<int> find_subset_sum_indices(const vector<int>& sizes, int target){
    if (target < 0) return {};
    int m = (int)sizes.size();
    vector<int> dp(target+1, -1);
    vector<int> prev(target+1, -1);
    dp[0] = -2; // marker
    for (int idx=0; idx<m; ++idx){
        int sz = sizes[idx];
        if (sz > target) continue;
        for (int s=target; s>=sz; --s){
            if (dp[s] == -1 && dp[s - sz] != -1){
                dp[s] = idx;
                prev[s] = s - sz;
                if (s == target){
                    vector<int> res;
                    int cur = s;
                    while (cur != 0){
                        int i = dp[cur];
                        res.push_back(i);
                        cur = prev[cur];
                    }
                    return res;
                }
            }
        }
    }
    return {};
}

// pack components into M groups of sum K each. comp_list: tuple(root, members, size)
using CompItem = tuple<int, vector<int>, int>;
vector<vector<int>> pack_components_into_M_groups(const vector<CompItem>& comp_list, int M, int K, int attempts=200){
    int n = (int)comp_list.size();
    vector<int> sizes(n);
    for (int i=0;i<n;i++) sizes[i] = get<2>(comp_list[i]);
    vector<int> order(n);
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [&](int a, int b){ return sizes[a] > sizes[b]; });

    // try deterministic greedy Best-Fit-Decreasing
    vector<vector<int>> groups(M);
    vector<int> gsum(M,0);
    bool ok_greedy = true;
    for (int idx : order){
        int sz = sizes[idx];
        int best_g = -1; int best_space = INT_MAX;
        for (int g = 0; g < M; ++g){
            int rem = K - (gsum[g] + sz);
            if (rem >= 0 && rem < best_space){
                best_space = rem;
                best_g = g;
            }
        }
        if (best_g == -1) { ok_greedy = false; break; }
        groups[best_g].push_back(idx);
        gsum[best_g] += sz;
    }
    if (ok_greedy){
        bool allK = true;
        for (int s: gsum) if (s != K) { allK = false; break; }
        if (allK) return groups;
    }

    // fallback DP repeated
    auto try_order = [&](const vector<int>& ord)->vector<vector<int>>{
        unordered_set<int> remaining(ord.begin(), ord.end());
        vector<vector<int>> gres;
        for (int g=0; g<M; ++g){
            vector<int> rem_list(remaining.begin(), remaining.end());
            vector<int> rem_sizes;
            rem_sizes.reserve(rem_list.size());
            for (int idx : rem_list) rem_sizes.push_back(sizes[idx]);
            vector<int> subset = find_subset_sum_indices(rem_sizes, K);
            if (subset.empty()) return {};
            vector<int> chosen;
            chosen.reserve(subset.size());
            for (int id : subset){
                chosen.push_back(rem_list[id]);
            }
            for (int c : chosen) remaining.erase(c);
            gres.push_back(chosen);
        }
        if (!remaining.empty()) return {};
        return gres;
    };

    vector<int> ord = order;
    vector<vector<int>> g = try_order(ord);
    if (!g.empty()) return g;
    // randomized attempts
    std::mt19937 rng((unsigned)chrono::high_resolution_clock::now().time_since_epoch().count());
    for (int a=0; a<attempts; ++a){
        shuffle(ord.begin(), ord.end(), rng);
        g = try_order(ord);
        if (!g.empty()) return g;
    }
    return {};
}

// Prim MST (returns list of edges connecting indices)
vector<pair<int,int>> prim_mst_indices(const vector<int>& indices, const vector<pair<double,double>>& pos, int L){
    int K = (int)indices.size();
    vector<pair<int,int>> edges;
    if (K <= 1) return edges;
    vector<char> in_mst(K, 0);
    vector<double> dist(K, 1e300);
    vector<int> parent(K, -1);
    dist[0] = 0.0;
    for (int it=0; it<K; ++it){
        int u = -1; double best = 1e300;
        for (int i=0;i<K;i++){
            if (!in_mst[i] && dist[i] < best){ best = dist[i]; u = i; }
        }
        if (u == -1) break;
        in_mst[u] = 1;
        if (parent[u] != -1){
            edges.emplace_back(indices[u], indices[parent[u]]);
        }
        auto pu = pos[indices[u]];
        for (int v=0; v<K; ++v){
            if (in_mst[v]) continue;
            auto pv = pos[indices[v]];
            double d = torus_dist2_xy(pu.first, pu.second, pv.first, pv.second, L);
            if (d < dist[v]){ dist[v] = d; parent[v] = u; }
        }
    }
    return edges;
}

// read input
bool read_input(int &N, int &T, int &M, int &K, int &L, vector<pair<double,double>>& pts, vector<pair<double,double>>& vels){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    if (!(cin >> N >> T >> M >> K >> L)) return false;
    pts.assign(N, {0.0,0.0});
    vels.assign(N, {0.0,0.0});
    for (int i=0;i<N;i++){
        int x,y,vx,vy;
        cin >> x >> y >> vx >> vy;
        pts[i].first = (double)x; pts[i].second = (double)y;
        vels[i].first = (double)vx; vels[i].second = (double)vy;
    }
    return true;
}

// main greedy implementation (faithful to Python)
vector<tuple<int,int,int>> greedy_length_pref_merge(int N, int T, int M, int K, int L,
    vector<pair<double,double>>& pts, vector<pair<double,double>>& vels, double THRESH, int NEIGHBORS)
{
    UF uf(N);
    unordered_map<int, pair<double,double>> vel;
    unordered_map<int, int> size;
    vel.reserve(N*2);
    size.reserve(N*2);
    for (int i=0;i<N;i++){
        vel[i] = vels[i];
        size[i] = 1;
    }
    vector<tuple<int,int,int>> merges;
    int merges_needed = N - M;
    bool use_thr = !(std::isnan(THRESH));
    double thr2 = use_thr ? THRESH*THRESH : -1.0;

    auto current_components = [&](void)->unordered_map<int, vector<int>>{
        unordered_map<int, vector<int>> comp;
        comp.reserve(N/2+10);
        for (int i=0;i<N;i++){
            int r = uf.find(i);
            comp[r].push_back(i);
        }
        return comp;
    };

    for (int t=0; t<T; ++t){
        if ((int)merges.size() >= merges_needed) break;

        auto comp = current_components();
        vector<int> roots;
        roots.reserve(comp.size());
        for (auto &kv : comp) roots.push_back(kv.first);

        // candidate list
        struct Cand { double d2; int ra, rb, ai, bi; };
        vector<Cand> candidates;
        candidates.reserve(roots.size() * (size_t)min((int)roots.size(), NEIGHBORS));
        unordered_set<long long> seen;

        for (int ra : roots){
            auto &A = comp[ra];
            vector<Cand> dlist;
            dlist.reserve(roots.size());
            int sa = size.count(ra) ? size[ra] : (int)A.size();
            for (int rb : roots){
                if (rb == ra) continue;
                int sb = size.count(rb) ? size[rb] : (int)comp[rb].size();
                if (sa + sb > K) continue;
                auto &B = comp[rb];
                double min_d2 = 1e300;
                int besta=-1, bestb=-1;
                if (A.size() <= B.size()){
                    for (int a : A){
                        double ax = pts[a].first, ay = pts[a].second;
                        for (int b : B){
                            double bx = pts[b].first, by = pts[b].second;
                            double d2 = torus_dist2_xy(ax, ay, bx, by, L);
                            if (d2 < min_d2){ min_d2 = d2; besta = a; bestb = b; if (min_d2 <= 0.0) break; }
                        }
                        if (min_d2 <= 0.0) break;
                    }
                } else {
                    for (int b : B){
                        double bx = pts[b].first, by = pts[b].second;
                        for (int a : A){
                            double ax = pts[a].first, ay = pts[a].second;
                            double d2 = torus_dist2_xy(ax, ay, bx, by, L);
                            if (d2 < min_d2){ min_d2 = d2; besta = a; bestb = b; if (min_d2 <= 0.0) break; }
                        }
                        if (min_d2 <= 0.0) break;
                    }
                }
                if (use_thr && min_d2 > thr2) continue;
                dlist.push_back({min_d2, ra, rb, besta, bestb});
            }
            if (dlist.empty()) continue;
            sort(dlist.begin(), dlist.end(), [](const Cand &a, const Cand &b){ return a.d2 < b.d2; });
            int limit = min((int)dlist.size(), NEIGHBORS);
            for (int i=0;i<limit;i++){
                const Cand &it = dlist[i];
                int a = it.ra, b = it.rb;
                int x = min(a,b), y = max(a,b);
                long long key = ((long long)x<<32) ^ (long long)y;
                if (seen.find(key) != seen.end()) continue;
                seen.insert(key);
                candidates.push_back(it);
            }
        }

        sort(candidates.begin(), candidates.end(), [](const Cand &a, const Cand &b){
            if (a.d2 != b.d2) return a.d2 < b.d2;
            if (a.ra != b.ra) return a.ra < b.ra;
            return a.rb < b.rb;
        });

        for (auto &c : candidates){
            if ((int)merges.size() >= merges_needed) break;
            int ra = c.ra, rb = c.rb;
            int ia = c.ai, ib = c.bi;
            int r_a = uf.find(ra), r_b = uf.find(rb);
            if (r_a == r_b) continue;
            int sa = size.count(r_a) ? size[r_a] : (int)comp[r_a].size();
            int sb = size.count(r_b) ? size[r_b] : (int)comp[r_b].size();
            if (sa + sb > K) continue;

            int long_root, short_root, long_point, short_point;
            int s_long, s_short;
            if (sa >= sb){ long_root = r_a; short_root = r_b; long_point = ia; short_point = ib; s_long = sa; s_short = sb; }
            else { long_root = r_b; short_root = r_a; long_point = ib; short_point = ia; s_long = sb; s_short = sa; }

            // short-side alternative check
            bool has_better_alt = false;
            if (use_thr){
                auto comp_now = current_components();
                double sx = pts[short_point].first, sy = pts[short_point].second;
                for (auto &kv : comp_now){
                    int r_other = kv.first;
                    if (r_other == long_root || r_other == short_root) continue;
                    int size_other = size.count(r_other) ? size[r_other] : (int)kv.second.size();
                    if (size_other >= s_long) continue;
                    for (int m : kv.second){
                        double mx = pts[m].first, my = pts[m].second;
                        if (torus_dist2_xy(sx, sy, mx, my, L) <= thr2){ has_better_alt = true; break; }
                    }
                    if (has_better_alt) break;
                }
            } else {
                auto comp_now = current_components();
                double sx = pts[short_point].first, sy = pts[short_point].second;
                vector<pair<double,int>> nearest_comps;
                nearest_comps.reserve(comp_now.size());
                for (auto &kv : comp_now){
                    int r_other = kv.first;
                    if (r_other == long_root || r_other == short_root) continue;
                    int size_other = size.count(r_other) ? size[r_other] : (int)kv.second.size();
                    if (size_other >= s_long) continue;
                    double md = 1e300;
                    for (int m : kv.second){
                        double d2 = torus_dist2_xy(sx, sy, pts[m].first, pts[m].second, L);
                        if (d2 < md) md = d2;
                    }
                    nearest_comps.emplace_back(md, r_other);
                }
                if (!nearest_comps.empty()){
                    sort(nearest_comps.begin(), nearest_comps.end());
                    if (nearest_comps[0].first < c.d2 - 1e-9) has_better_alt = true;
                }
            }
            if (has_better_alt) continue;

            // packing check
            auto comp_now = current_components();
            vector<CompItem> comp_items;
            comp_items.reserve(comp_now.size());
            for (auto &kv : comp_now){
                int root = kv.first;
                if (root == r_a || root == r_b) continue;
                int s = size.count(root) ? size[root] : (int)kv.second.size();
                comp_items.emplace_back(root, kv.second, s);
            }
            vector<int> merged_members = comp[r_a];
            auto &v2 = comp[r_b];
            merged_members.insert(merged_members.end(), v2.begin(), v2.end());
            comp_items.emplace_back(-1, merged_members, sa + sb);
            bool bad=false;
            for (auto &it : comp_items){
                if (get<2>(it) > K){ bad = true; break; }
            }
            if (bad) continue;
            auto pack = pack_components_into_M_groups(comp_items, M, K, 50);
            if (pack.empty()) continue;

            // accept merge
            merges.emplace_back(t, long_point, short_point);
            int ra_root = uf.find(long_point), rb_root = uf.find(short_point);
            if (ra_root != rb_root){
                int sa2 = size.count(ra_root) ? size[ra_root] : 1;
                int sb2 = size.count(rb_root) ? size[rb_root] : 1;
                auto vxa_vya = vel.count(ra_root) ? vel[ra_root] : vels[ra_root];
                auto vxb_vyb = vel.count(rb_root) ? vel[rb_root] : vels[rb_root];
                int newroot = uf.unite(ra_root, rb_root);
                int newsize = sa2 + sb2;
                double newvx = (sa2 * vxa_vya.first + sb2 * vxb_vyb.first) / (double)newsize;
                double newvy = (sa2 * vxa_vya.second + sb2 * vxb_vyb.second) / (double)newsize;
                vel[newroot] = {newvx, newvy};
                size[newroot] = newsize;
                if (newroot != ra_root){ vel.erase(ra_root); size.erase(ra_root); }
                if (newroot != rb_root){ vel.erase(rb_root); size.erase(rb_root); }
            }
        }

        // movement phase
        for (int i=0;i<N;i++){
            int r = uf.find(i);
            auto it = vel.find(r);
            double vx, vy;
            if (it != vel.end()){ vx = it->second.first; vy = it->second.second; }
            else { vx = vels[i].first; vy = vels[i].second; }
            double nx = pts[i].first + vx;
            double ny = pts[i].second + vy;
            // normalize 0<= < L
            nx = fmod(nx, (double)L); if (nx < 0) nx += L;
            ny = fmod(ny, (double)L); if (ny < 0) ny += L;
            pts[i].first = nx; pts[i].second = ny;
        }
    }

    // final packing if needed at t=T-1
    if ((int)merges.size() < merges_needed){
        auto comp_now = current_components();
        vector<CompItem> comp_items;
        comp_items.reserve(comp_now.size());
        for (auto &kv : comp_now){
            int root = kv.first;
            int s = size.count(root) ? size[root] : (int)kv.second.size();
            comp_items.emplace_back(root, kv.second, s);
        }
        auto pack = pack_components_into_M_groups(comp_items, M, K, 500);
        if (pack.empty()){
            // fallback naive merging
            vector<int> roots;
            for (auto &kv: comp_now) roots.push_back(kv.first);
            while ((int)merges.size() < merges_needed && (int)roots.size() >= 2){
                int a = roots.front(); roots.erase(roots.begin());
                int b = roots.front(); roots.erase(roots.begin());
                auto &A = comp_now[a]; auto &B = comp_now[b];
                double bestd = 1e300; pair<int,int> bestpair = {A[0], B[0]};
                for (int x : A){
                    for (int y : B){
                        double d2 = torus_dist2_xy(pts[x].first, pts[x].second, pts[y].first, pts[y].second, L);
                        if (d2 < bestd){ bestd = d2; bestpair = {x,y}; }
                    }
                }
                merges.emplace_back(max(0, T-1), bestpair.first, bestpair.second);
                uf.unite(bestpair.first, bestpair.second);
                comp_now = current_components();
                roots.clear();
                for (auto &kv : comp_now) roots.push_back(kv.first);
            }
        } else {
            // connect components within each packed group by nearest merges at t=T-1
            // comp_items index -> comp_items[idx].first is root id
            for (const auto &group : pack){
                vector<int> subs;
                subs.reserve(group.size());
                for (int idx : group) subs.push_back(get<0>(comp_items[idx]));
                comp_now = current_components();
                while ((int)subs.size() > 1 && (int)merges.size() < merges_needed){
                    double bestd = 1e300; pair<int,int> bestpair = {-1,-1};
                    pair<int,int> best_roots = {-1,-1};
                    for (size_t i=0;i<subs.size();++i){
                        int ri = subs[i];
                        auto Ai_it = comp_now.find(ri);
                        if (Ai_it == comp_now.end()) continue;
                        auto &Ai = Ai_it->second;
                        for (size_t j=i+1;j<subs.size();++j){
                            int rj = subs[j];
                            auto Bj_it = comp_now.find(rj);
                            if (Bj_it == comp_now.end()) continue;
                            auto &Bj = Bj_it->second;
                            for (int a : Ai){
                                for (int b : Bj){
                                    double d2 = torus_dist2_xy(pts[a].first, pts[a].second, pts[b].first, pts[b].second, L);
                                    if (d2 < bestd){ bestd = d2; bestpair = {a,b}; best_roots = {ri,rj}; }
                                }
                            }
                        }
                    }
                    if (bestpair.first == -1) break;
                    merges.emplace_back(max(0, T-1), bestpair.first, bestpair.second);
                    uf.unite(bestpair.first, bestpair.second);
                    comp_now = current_components();
                    // filter subs to only roots still representatives
                    vector<int> new_subs;
                    for (int r : subs) if (uf.find(r) == r) new_subs.push_back(r);
                    subs.swap(new_subs);
                }
            }
        }
    }

    return merges;
}

int main(int argc, char** argv){
    double THRESH = 2000.0;
    int NEIGHBORS = 5;
    if (argc >= 2){
        string s = argv[1];
        if (s == "None" || s == "null" || s == "none" || s == "NULL") THRESH = numeric_limits<double>::quiet_NaN();
        else {
            try { THRESH = stod(s); } catch(...) { THRESH = numeric_limits<double>::quiet_NaN(); }
        }
    }
    if (argc >= 3){
        try { NEIGHBORS = stoi(argv[2]); } catch(...) { NEIGHBORS = 5; }
    }

    int N, T, M, K, L;
    vector<pair<double,double>> pts, vels;
    if (!read_input(N, T, M, K, L, pts, vels)) return 0;

    vector<tuple<int,int,int>> merges = greedy_length_pref_merge(N,T,M,K,L,pts,vels,THRESH,NEIGHBORS);
    int need = N - M;
    int cnt = 0;
    for (auto &m : merges){
        if (cnt >= need) break;
        int t,i,j;
        tie(t,i,j) = m;
        cout << t << " " << i << " " << j << "\n";
        cnt++;
    }

    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function 'std::vector<std::tuple<int, int, int> > greedy_length_pref_merge(int, int, int, int, int, std::vector<std::pair<double, double> >&, std::vector<std::pair<double, double> >&, double, int)':
./Main.cpp:293:25: warning: variable 's_short' set but not used [-Wunused-but-set-variable]
  293 |             int s_long, s_short;
      |                         ^~~~~~~

Judge Result