提出 #68414518

---

ソースコード 拡げる

// AHC051 A - Probabilistic Waste Sorting
// S-snake + corridor pruning. Devices connect only from recovery lanes (lane%4 in {1,2}).
// If crossings are detected, retry with fewer lanes (wider lanes). Guaranteed valid fallback.
//
// Compile: g++ -O2 -std=gnu++17 main.cpp
#include <bits/stdc++.h>
using namespace std;

static const int WIDTH = 10000;
static const int HEIGHT = 10000;

// ================= Geometry =================
struct P{ int x,y; };
static inline int sgn(long long v){ return (v>0)-(v<0); }
static inline int orient(const P& a,const P& b,const P& c){
    long long cr = 1LL*(b.x-a.x)*(c.y-a.y) - 1LL*(b.y-a.y)*(c.x-a.x);
    return sgn(cr); // >0: left
}
static inline bool on_seg(const P& a,const P& b,const P& c){
    return min(a.x,b.x)<=c.x && c.x<=max(a.x,b.x) &&
           min(a.y,b.y)<=c.y && c.y<=max(a.y,b.y);
}
static inline bool bbox_disjoint(const P& p1,const P& p2,const P& q1,const P& q2){
    if(max(p1.x,p2.x) < min(q1.x,q2.x)) return true;
    if(max(q1.x,q2.x) < min(p1.x,p2.x)) return true;
    if(max(p1.y,p2.y) < min(q1.y,q2.y)) return true;
    if(max(q1.y,q2.y) < min(p1.y,p2.y)) return true;
    return false;
}
static inline bool segments_intersect(const P& p1,const P& q1,const P& p2,const P& q2,bool allow_touch=true){
    if(bbox_disjoint(p1,q1,p2,q2)) return false;
    int o1=orient(p1,q1,p2), o2=orient(p1,q1,q2);
    int o3=orient(p2,q2,p1), o4=orient(p2,q2,q1);
    if(o1*o2<0 && o3*o4<0) return true;
    if(!allow_touch){
        if(o1==0 && on_seg(p1,q1,p2)) return true;
        if(o2==0 && on_seg(p1,q1,q2)) return true;
        if(o3==0 && on_seg(p2,q2,p1)) return true;
        if(o4==0 && on_seg(p2,q2,p1)) return true;
    }
    return false;
}
static inline uint64_t key64(const P& a){ return (uint64_t(uint32_t(a.x))<<32) | uint32_t(a.y); }

// ================= Plan container =================
struct Plan{
    vector<int> d;              // device assignment (0..N-1 identity)
    int s;                      // start destination node id
    vector<string> lines;       // M lines for splitters
    vector<pair<P,P>> segments; // all conveyor segments for validation
    bool ok = false;
};
// ---- reachability (for cycle check) ---------------------------------
static bool path_exists(const vector<vector<int>>& G, int s, int t){
    if(s==t) return true;
    int n=(int)G.size();
    vector<char> vis(n,0);
    std::stack<int> st; st.push(s); vis[s]=1;
    while(!st.empty()){
        int u=st.top(); st.pop();
        for(int v:G[u]){
            if(!vis[v]){
                if(v==t) return true;
                vis[v]=1; st.push(v);
            }
        }
    }
    return false;
}

// ---- add arc if valid: outdeg≤2 / no crossing / no cycle ------------
static bool add_arc_if_valid(
    int u, int v,
    const vector<P>& sor,
    vector<vector<int>>& G,
    vector<int>& outdeg,
    vector<pair<P,P>>& all_segments
){
    if(u==v) return false;
    if(outdeg[u] >= 2) return false;         // splitter 2本まで
    if(path_exists(G, v, u)) return false;   // u<-...-v が既にある → 閉路

    const P pu = sor[u], pv = sor[v];

    // 交差チェック（端点共有はOK）
    auto same = [](const P& a,const P& b){ return a.x==b.x && a.y==b.y; };
    for(const auto& e: all_segments){
        const P& a=e.first; const P& b=e.second;
        if( same(a,pu)||same(a,pv)||same(b,pu)||same(b,pv) ) continue;
        if(segments_intersect(pu,pv,a,b,true)) return false;
    }

    // 採用
    G[u].push_back(v);
    outdeg[u]++;
    all_segments.push_back({pu,pv});
    return true;
}

// ---- 同一レーンを S字で向き付け & レーン間ブリッジ -------------------
static void add_snake_same_lane_and_bridges(
    const vector<vector<int>>& lanes,
    const vector<P>& sor,
    vector<vector<int>>& G,
    vector<int>& outdeg,
    vector<pair<P,P>>& all_segments
){
    const int B = (int)lanes.size();
    // レーン i の並び（i 偶数: 左→右, i 奇数: 右→左）
    vector<vector<int>> dir_ids(B);

    for(int i=0;i<B;i++){
        dir_ids[i] = lanes[i];
        sort(dir_ids[i].begin(), dir_ids[i].end(),
             [&](int a,int b){ return sor[a].x < sor[b].x; });
        if(i%2==1) reverse(dir_ids[i].begin(), dir_ids[i].end()); // S字
    }

    // (1) 同一レーン内：隣接を i の方向に張る
    for(int i=0;i<B;i++){
        auto &ids = dir_ids[i];
        for(int t=0;t+1<(int)ids.size();++t){
            int u = ids[t], v = ids[t+1];
            add_arc_if_valid(u, v, sor, G, outdeg, all_segments);
        }
    }

    // (2) レーン間ブリッジ：i の末端 -> (i+1) の始端（同じ側）を優先して1本
    for(int i=0;i+1<B;i++){
        if(dir_ids[i].empty() || dir_ids[i+1].empty()) continue;
        int u = dir_ids[i].back();     // レーン i の終点
        int v = dir_ids[i+1].front();  // レーン i+1 の始点（折り返し）
        add_arc_if_valid(u, v, sor, G, outdeg, all_segments);
    }
}

// ================= Builder =================

struct Builder {
    // ------- fields -------
    int N, M, K, B;
    const vector<P>& dev;
    const vector<P>& sor;
    const P START{0, 5000};

    // ------- ctor -------
    Builder(int N, int M, int K, int B,
            const vector<P>& d, const vector<P>& s)
        : N(N), M(M), K(K), B(B), dev(d), sor(s) {}

    // ------- lane helpers -------
    inline int band_y(int y) const {
        int denom = max(1, HEIGHT / B);
        int li = y / denom;
        if (li < 0) li = 0;
        if (li >= B) li = B - 1;
        return li;
    }
    inline bool is_recovery(int li) const { return (li % 4) == 1 || (li % 4) == 2; }

  private:
    
    // ===== 層間ペア枝ユーティリティ =====
    bool has_path_in_G_(int s, int t, const vector<vector<int>>& G) const {
        vector<char> vis(M, 0);
        stack<int> st;
        st.push(s);
        vis[s] = 1;
        while (!st.empty()) {
            int u = st.top(); st.pop();
            if (u == t) return true;
            for (int v : G[u]) if (!vis[v]) { vis[v] = 1; st.push(v); }
        }
        return false;
    }

    bool try_add_pair_edge_(int u, int v,
                            vector<vector<int>>& G, vector<int>& outdeg,
                            vector<pair<int,int>>& pair_edges,
                            vector<pair<P,P>>& all_segments) const
    {
        if (u == v) return false;
        if (outdeg[u] >= 2) return false;

        const P& pu = sor[u];
        const P& pv = sor[v];

        auto same = [](const P& a, const P& b){ return a.x == b.x && a.y == b.y; };

        // 既存線分と交差しないか
        for (const auto& e : all_segments) {
            const P& a = e.first; const P& b = e.second;
            if (same(a, pu) || same(a, pv) || same(b, pu) || same(b, pv)) continue;
            if (segments_intersect(pu, pv, a, b, true)) return false;
        }
        // 追加済みペア枝とも交差しないか
        for (const auto& pr : pair_edges) {
            const P& a = sor[pr.first];
            const P& b = sor[pr.second];
            if (same(a, pu) || same(a, pv) || same(b, pu) || same(b, pv)) continue;
            if (segments_intersect(pu, pv, a, b, true)) return false;
        }
        // 閉路を作らない（v→…→u があるなら u→v は不可）
        if (has_path_in_G_(v, u, G)) return false;

        // 追加
        pair_edges.push_back({u, v});
        G[u].push_back(v);
        outdeg[u]++;
        all_segments.push_back({pu, pv});
        return true;
    }

    void add_adjacent_lane_pairs_(const vector<vector<int>>& lanes,
                                  vector<vector<int>>& G, vector<int>& outdeg,
                                  vector<pair<int,int>>& pair_edges,
                                  vector<pair<P,P>>& all_segments) const
    {
        auto byX = [&](int a, int b){ return sor[a].x < sor[b].x; };

        for (int li = 0; li + 1 < B; ++li) {
            vector<int> A = lanes[li];
            vector<int> Bn = lanes[li + 1];
            sort(A.begin(), A.end(), byX);
            sort(Bn.begin(), Bn.end(), byX);

            int i = 0, j = 0, cntAB = 0, cntBA = 0;
            while (i < (int)A.size() && j < (int)Bn.size()) {
                int a = A[i], b = Bn[j];

                bool okAB = try_add_pair_edge_(a, b, G, outdeg, pair_edges, all_segments);
                bool okBA = try_add_pair_edge_(b, a, G, outdeg, pair_edges, all_segments);

                if (okAB && okBA) {
                    // バランス優先（次点で距離短い方に偏る）
                    if (cntAB <= cntBA) {
                        // BA を巻き戻す
                        pair_edges.pop_back(); G[b].pop_back(); outdeg[b]--; all_segments.pop_back();
                        j++; cntAB++;
                    } else {
                        // AB を巻き戻す
                        pair_edges.pop_back(); G[a].pop_back(); outdeg[a]--; all_segments.pop_back();
                        i++; cntBA++;
                    }
                } else if (okAB) {
                    j++; cntAB++;
                } else if (okBA) {
                    i++; cntBA++;
                } else {
                    // どちらも不可なら x の小さい方を進める
                    (sor[a].x <= sor[b].x) ? ++i : ++j;
                }
            }
        }
    }

  public:
    // ====== main builder ======
    Plan build() {
        Plan out;
        out.d.resize(N);
        iota(out.d.begin(), out.d.end(), 0);

        // ---- lanes ----
        vector<vector<int>> lanes(B);
        for (int i = 0; i < M; i++) lanes[band_y(sor[i].y)].push_back(i);
        for (int i = 0; i < B; i++)
            sort(lanes[i].begin(), lanes[i].end(),
                 [&](int a, int b){ return sor[a].x < sor[b].x; });

        if (lanes[0].empty()) {
            int best = 0;
            for (int i = 1; i < M; i++) if (sor[i].y < sor[best].y) best = i;
            lanes[0] = {best};
        }
        int p0_idx = lanes[0][0];
        P p0 = sor[p0_idx];

        // START->p0 の左側は使わない
        auto left_of_start = [&](const P& c){
            long long cr = 1LL * (p0.x - START.x) * (c.y - START.y)
                         - 1LL * (p0.y - START.y) * (c.x - START.x);
            return cr < 0;
        };
        vector<char> valid(M, 1);
        for (int i = 0; i < M; i++) if (left_of_start(sor[i])) valid[i] = 0;

        // lanes を valid で組み直し
        for (int i = 0; i < B; i++) lanes[i].clear();
        for (int i = 0; i < M; i++) if (valid[i]) lanes[band_y(sor[i].y)].push_back(i);
        for (int i = 0; i < B; i++)
            sort(lanes[i].begin(), lanes[i].end(),
                 [&](int a, int b){ return sor[a].x < sor[b].x; });

        // ---- undirected skeleton with crossing guard ----
        vector<pair<P,P>> undirected, crossing;
        auto crosses_any = [&](const P& u, const P& v)->bool{
            for (const auto& e : crossing) {
                const P& a = e.first; const P& b = e.second;
                if ((a.x == u.x && a.y == u.y) || (a.x == v.x && a.y == v.y) ||
                    (b.x == u.x && b.y == u.y) || (b.x == v.x && b.y == v.y)) continue;
                if (segments_intersect(u, v, a, b, true)) return true;
            }
            return false;
        };
        auto add_u = [&](const P& u, const P& v){
            if (u.x == v.x && u.y == v.y) return false;
            if (crosses_any(u, v)) return false;
            undirected.push_back({u, v});
            crossing.push_back({u, v});
            return true;
        };

        // start chain
        add_u(START, p0);
        if (!lanes[1].empty()) add_u(p0, sor[lanes[1][0]]);

        auto is_right = [&](const P& A, const P& Z, const P& C){ return orient(A, Z, C) < 0; };
        auto is_left  = [&](const P& A, const P& Z, const P& C){ return orient(A, Z, C) > 0; };

        // even groups: base=0,4,8,...（右端ブリッジ）
        for (int base = 0; base < B; base += 4) {
            if (base + 3 >= B) break;
            if (lanes[base].empty() || lanes[base + 3].empty()) continue;
            P A = sor[lanes[base].back()], Z = sor[lanes[base + 3].back()];
            if (add_u(A, Z)) {
                for (int L : {base + 1, base + 2}) {
                    vector<int> v;
                    for (int idx : lanes[L]) if (!is_right(A, Z, sor[idx])) v.push_back(idx);
                    lanes[L].swap(v);
                }
                if (!lanes[base + 1].empty() && !lanes[base + 2].empty()) {
                    int u = *max_element(lanes[base + 1].begin(), lanes[base + 1].end(),
                                         [&](int a, int b){ return sor[a].x < sor[b].x; });
                    int v = *max_element(lanes[base + 2].begin(), lanes[base + 2].end(),
                                         [&](int a, int b){ return sor[a].x < sor[b].x; });
                    P U = sor[u], V = sor[v];
                    if (add_u(U, V)) {
                        for (int L : {base + 1, base + 2}) {
                            vector<int> w;
                            for (int idx : lanes[L]) if (!is_right(U, V, sor[idx])) w.push_back(idx);
                            lanes[L].swap(w);
                        }
                    }
                }
            }
        }
        // odd groups: base=2,6,...（左端ブリッジ）
        for (int base = 2; base < B; base += 4) {
            if (base + 3 >= B) break;
            if (lanes[base].empty() || lanes[base + 3].empty()) continue;
            P A = sor[lanes[base].front()], Z = sor[lanes[base + 3].front()];
            if (add_u(A, Z)) {
                for (int L : {base + 1, base + 2}) {
                    vector<int> v;
                    for (int idx : lanes[L]) if (!is_left(A, Z, sor[idx])) v.push_back(idx);
                    lanes[L].swap(v);
                }
                if (!lanes[base + 1].empty() && !lanes[base + 2].empty()) {
                    int u = *min_element(lanes[base + 1].begin(), lanes[base + 1].end(),
                                         [&](int a, int b){ return sor[a].x < sor[b].x; });
                    int v = *min_element(lanes[base + 2].begin(), lanes[base + 2].end(),
                                         [&](int a, int b){ return sor[a].x < sor[b].x; });
                    P U = sor[u], V = sor[v];
                    if (add_u(U, V)) {
                        for (int L : {base + 1, base + 2}) {
                            vector<int> w;
                            for (int idx : lanes[L]) if (!is_left(U, V, sor[idx])) w.push_back(idx);
                            lanes[L].swap(w);
                        }
                    }
                }
            }
        }
        // 各レーン内の単調エッジ
        for (int i = 0; i < B; i++) {
            auto ids = lanes[i];
            if ((int)ids.size() < 2) continue;
            sort(ids.begin(), ids.end(), [&](int a, int b){ return sor[a].x < sor[b].x; });
            for (int t = 0; t + 1 < (int)ids.size(); ++t) add_u(sor[ids[t]], sor[ids[t + 1]]);
        }
        // 最上段 2 レーンの連結
        if (B >= 2 && !lanes[B - 2].empty() && !lanes[B - 1].empty()) {
            int la = *min_element(lanes[B - 2].begin(), lanes[B - 2].end(),
                                  [&](int a, int b){ return sor[a].x < sor[b].x; });
            int lb = *min_element(lanes[B - 1].begin(), lanes[B - 1].end(),
                                  [&](int a, int b){ return sor[a].x < sor[b].x; });
            add_u(sor[la], sor[lb]);
        }

        // ---- undirected -> directed snake ----
        unordered_map<uint64_t,int> id_of;
        vector<P> id_to_pt;
        auto get_id = [&](const P& p){
            uint64_t k = key64(p);
            auto it = id_of.find(k);
            if (it != id_of.end()) return it->second;
            int nid = (int)id_to_pt.size();
            id_of.emplace(k, nid); id_to_pt.push_back(p);
            return nid;
        };
        for (auto &e : undirected) { get_id(e.first); get_id(e.second); }
        vector<vector<int>> adj(id_to_pt.size());
        for (auto &e : undirected) {
            int u = get_id(e.first), v = get_id(e.second);
            adj[u].push_back(v); adj[v].push_back(u);
        }
        auto extract_cycle = [&](int s)->vector<int>{
            vector<int> ord;
            if (s < 0 || s >= (int)adj.size()) return ord;
            if (adj[s].empty()) return ord;
            ord.push_back(s);
            int prev = -1, cur = s; set<pair<int,int>> used;
            for (size_t it = 0; it < adj.size() * 4; ++it) {
                int nxt = -1;
                for (int v : adj[cur]) {
                    if (v == prev) continue;
                    if (used.count({cur, v}) || used.count({v, cur})) continue;
                    nxt = v; used.insert({cur, v}); break;
                }
                if (nxt == -1) break;
                ord.push_back(nxt);
                prev = cur; cur = nxt;
                if (cur == s) break;
            }
            return ord;
        };
        int start_node = id_of.count(key64(p0)) ? id_of[key64(p0)] : -1;
        vector<int> ring = (start_node != -1) ? extract_cycle(start_node) : vector<int>{};
        if ((int)ring.size() < 4) {
            vector<int> bestcyc;
            for (int u = 0; u < (int)adj.size(); ++u) {
                auto tmp = extract_cycle(u);
                if (tmp.size() > bestcyc.size()) bestcyc = std::move(tmp);
            }
            ring = std::move(bestcyc);
        }
        vector<pair<P,P>> directed;
        if (!ring.empty()) {
            int tdi = 0;
            for (int i = 1; i < N; i++)
                if (dev[i].x + dev[i].y > dev[tdi].x + dev[tdi].y) tdi = i;
            P target = dev[tdi];
            auto d2 = [&](const P& a, const P& b)->long long{
                long long dx=a.x-b.x, dy=a.y-b.y; return dx*dx+dy*dy;
            };
            int n = (int)ring.size();
            vector<P> rpts(n);
            for (int i = 0; i < n; i++) rpts[i] = id_to_pt[ring[i]];
            vector<int> cand;
            for (int i = 0; i < n; i++) if (band_y(rpts[i].y) % 2 == 1) cand.push_back(i);
            if (cand.empty()) for (int i = 0; i < n; i++) cand.push_back(i);
            int pivot = cand[0];
            for (int i : cand) if (d2(rpts[i], target) < d2(rpts[pivot], target)) pivot = i;
            auto cyc_dist = [&](int i, int j){ int a=(j-i+n)%n, b=(i-j+n)%n; return min(a,b); };
            vector<int> dval(n);
            for (int i = 0; i < n; i++) dval[i] = cyc_dist(i, pivot);
            for (int i = 0; i < n; i++) {
                int j = (i + 1) % n; P u = rpts[i], v = rpts[j];
                if (dval[i] > dval[j]) directed.push_back({u, v});
                else if (dval[i] < dval[j]) directed.push_back({v, u});
                else directed.push_back((u.x > v.x) ? make_pair(u, v) : make_pair(v, u));
            }
            directed.push_back({rpts[pivot], target});
        }

        // ---- base segments（交差検証用）----
        vector<pair<P,P>> all_segments;
        all_segments.push_back({START, sor[p0_idx]});
        for (auto &e : directed) all_segments.push_back(e);

        // ---- device wiring（近傍＋交差回避、各ソーター最大 outdeg=2 を尊重）----
        vector<int> outdeg(M, 0);
        unordered_map<uint64_t,int> idxS, idxD;
        idxS.reserve(M * 2); idxD.reserve(N * 2);
        for (int i = 0; i < M; i++) idxS.emplace(key64(sor[i]), i);
        for (int i = 0; i < N; i++) idxD.emplace(key64(dev[i]), i);
        for (auto &e : directed) {
            auto it = idxS.find(key64(e.first));
            if (it != idxS.end()) outdeg[it->second]++;
        }
        struct Cand { int si; P sp; };
        vector<Cand> picker;
        for (int i = 0; i < M; i++) if (valid[i]) picker.push_back({i, sor[i]});
        vector<pair<int,int>> dev_edges; // (sorter, device)
        vector<char> usedS(M, 0);
        auto dist2 = [&](const P& a, const P& b)->long long{
            long long dx=a.x-b.x, dy=a.y-b.y; return dx*dx+dy*dy;
        };
        for (int di = 0; di < N; ++di) {
            P dp = dev[di];
            vector<int> ord(picker.size());
            iota(ord.begin(), ord.end(), 0);
            sort(ord.begin(), ord.end(),
                 [&](int a, int b){ return dist2(dp, picker[a].sp) < dist2(dp, picker[b].sp); });
            for (int oi : ord) {
                int si = picker[oi].si;
                if (usedS[si] || outdeg[si] >= 2) continue;
                P sp = picker[oi].sp;
                bool bad = false;
                for (auto &e : all_segments) {
                    if (segments_intersect(dp, sp, e.first, e.second, true)) { bad = true; break; }
                }
                if (bad) continue;
                for (auto &pr : dev_edges) {
                    P sp2 = sor[pr.first], dp2 = dev[pr.second];
                    if (segments_intersect(dp, sp, dp2, sp2, true)) { bad = true; break; }
                }
                if (bad) continue;
                dev_edges.push_back({si, di});
                usedS[si] = 1;
                outdeg[si]++;
                all_segments.push_back({sp, dp});
                break;
            }
        }

        // ---- sorter graph（ソーター間の向き）----
        vector<vector<int>> G(M);
        auto push_from_segments = [&](const vector<pair<P,P>>& segs){
            for (const auto& e : segs) {
                auto itU = idxS.find(key64(e.first));
                auto itV = idxS.find(key64(e.second));
                if (itU != idxS.end() && itV != idxS.end()) {
                    G[itU->second].push_back(itV->second);
                }
            }
        };
        push_from_segments(directed);

        // ---- 層間のペア枝を追加（主題）----
        vector<pair<int,int>> pair_edges;
        
        add_adjacent_lane_pairs_(lanes, G, outdeg, pair_edges, all_segments);
        // add_snake_same_lane_and_bridges(lanes, sor, G, outdeg, all_segments);

        // ---- Compose outputs ----
        auto node_id = [&](const P& p)->int{
            auto itD2 = idxD.find(key64(p)); if (itD2 != idxD.end()) return itD2->second;
            auto itS2 = idxS.find(key64(p)); if (itS2 != idxS.end()) return N + itS2->second;
            return -1;
        };
        vector<vector<int>> outs(M);
        vector<char> installed(M, 0);

        for (auto &e : directed) {
            auto it = idxS.find(key64(e.first));
            if (it != idxS.end()) {
                int u = it->second, v = node_id(e.second);
                if (v != -1) {
                    outs[u].push_back(v); installed[u] = 1;
                    if (v >= N) installed[v - N] = 1;
                }
            }
        }
        for (auto &pr : dev_edges) {
            int si = pr.first, di = pr.second;
            outs[si].push_back(di); installed[si] = 1;
        }
        for (auto &pr : pair_edges) {
            int u = pr.first, v = pr.second;
            outs[u].push_back(N + v);
            installed[u] = 1; installed[v] = 1;
        }

        out.s = N + p0_idx;

        out.lines.assign(M, "-1");
        for (int i = 0; i < M; i++) {
            if (!installed[i]) continue;
            int a, b;
            if (outs[i].empty()) { a = b = 0; }
            else if ((int)outs[i].size() == 1) { a = b = outs[i][0]; }
            else { a = outs[i][0]; b = outs[i][1]; }
            out.lines[i] = "0 " + to_string(a) + " " + to_string(b);
        }

        out.segments.push_back({START, sor[p0_idx]});
        auto point_of_id = [&](int id)->P{
            if (id < N) return dev[id];
            else return sor[id - N];
        };
        for (int i = 0; i < M; i++) {
            if (out.lines[i] == "-1") continue;
            int k, a, b; { stringstream ss(out.lines[i]); ss >> k >> a >> b; }
            P spt = sor[i];
            out.segments.push_back({spt, point_of_id(a)});
            out.segments.push_back({spt, point_of_id(b)});
        }

        out.ok = true;
        return out;
    }
};
  

// ================= Validate crossings =================
static bool has_crossing(const vector<pair<P,P>>& segs){
    int E=(int)segs.size();
    for(int i=0;i<E;i++){
        for(int j=i+1;j<E;j++){
            const auto &a=segs[i], &b=segs[j];
            auto same = [](const P& u,const P& v){ return u.x==v.x && u.y==v.y; };
            if( same(a.first,b.first) || same(a.first,b.second) ||
                same(a.second,b.first) || same(a.second,b.second) ) continue;
            if(segments_intersect(a.first,a.second,b.first,b.second,true)) return true;
        }
    }
    return false;
}


// ============ Hungarian (maximization, square) ============
static vector<int> hungarian_max_assign(const vector<vector<double>>& w){ // row=color, col=device
    int n = (int)w.size();
    const double INF = 1e100;
    vector<double> u(n+1,0), v(n+1,0);
    vector<int> p(n+1,0), way(n+1,0);
    for(int i=1;i<=n;i++){
        p[0]=i;
        int j0=0;
        vector<double> minv(n+1, INF);
        vector<char> used(n+1,false);
        do{
            used[j0]=true;
            int i0=p[j0], j1=0;
            double delta=INF;
            for(int j=1;j<=n;j++) if(!used[j]){
                double cur = -(w[i0-1][j-1]) - u[i0] - v[j]; // maximize -> negate
                if(cur < minv[j]){ minv[j]=cur; way[j]=j0; }
                if(minv[j] < delta){ delta=minv[j]; j1=j; }
            }
            for(int j=0;j<=n;j++){
                if(used[j]){ u[p[j]] += delta; v[j] -= delta; }
                else minv[j] -= delta;
            }
            j0=j1;
        }while(p[j0]!=0);
        do{
            int j1=way[j0];
            p[j0]=p[j1]; j0=j1;
        }while(j0);
    }
    vector<int> assign_row_to_col(n,-1); // row i -> col j
    for(int j=1;j<=n;j++) if(p[j]) assign_row_to_col[p[j]-1]=j-1;
    return assign_row_to_col;
}

// ============ reachability & topo (graph fixed) ============
// best.lines[i] : "-1" か "k a b"（a,b は [0..N+M-1]）
static void build_reach_and_topo(
    const Plan& best, int N, int M,
    const vector<string>& lines,
    vector<char>& installed, vector<int>& v1, vector<int>& v2,
    vector<char>& reachS, vector<int>& topo, vector<int>& rtopo
){
    installed.assign(M,0); v1.assign(M,-1); v2.assign(M,-1);
    for(int i=0;i<M;i++){
        if(lines[i]=="-1") continue;
        installed[i]=1;
        int k,a,b; stringstream ss(lines[i]); ss>>k>>a>>b;
        v1[i]=a; v2[i]=b;
    }
    vector<vector<int>> adjS(M), parS(M);
    auto push_edge = [&](int u,int to){
        if(to>=N){
            int v=to-N;
            if(0<=v&&v<M){ adjS[u].push_back(v); parS[v].push_back(u); }
        }
    };
    for(int u=0;u<M;u++) if(installed[u]){
        if(v1[u]!=-1) push_edge(u,v1[u]);
        if(v2[u]!=-1) push_edge(u,v2[u]);
    }
    reachS.assign(M,0);
    if(best.s>=N){
        int s0=best.s-N;
        if(0<=s0&&s0<M&&installed[s0]){
            queue<int> q; reachS[s0]=1; q.push(s0);
            while(!q.empty()){
                int u=q.front(); q.pop();
                for(int v: adjS[u]){
                    if(!installed[v]||reachS[v]) continue;
                    reachS[v]=1; q.push(v);
                }
            }
        }
    }
    vector<int> indeg(M,0);
    for(int v=0;v<M;v++) if(installed[v]&&reachS[v]){
        int c=0; for(int p:parS[v]) if(installed[p]&&reachS[p]) c++; indeg[v]=c;
    }
    topo.clear(); topo.reserve(M);
    {
        queue<int> q;
        for(int i=0;i<M;i++) if(installed[i]&&reachS[i]&&indeg[i]==0) q.push(i);
        while(!q.empty()){
            int u=q.front(); q.pop(); topo.push_back(u);
            for(int v:adjS[u]){
                if(!installed[v]||!reachS[v]) continue;
                if(--indeg[v]==0) q.push(v);
            }
        }
    }
    rtopo=topo; reverse(rtopo.begin(), rtopo.end());
}

// ============ forward flow (given k & swap) ============
struct FlowPack{
    vector<vector<double>> inflS; // [M][N] sorter inflow by color
    vector<vector<double>> flowD; // [N][N] device intake by color
};

static FlowPack forward_flow_allcolors(
    const Plan& best, int N, int M, int K,
    const vector<char>& installed, const vector<int>& v1, const vector<int>& v2,
    const vector<int>& curK, const vector<char>& swapFlag,
    const vector<char>& reachS, const vector<int>& topo,
    const vector<vector<double>>& prob
){
    vector<vector<double>> inflS(M, vector<double>(N,0.0));
    vector<vector<double>> flowD(N, vector<double>(N,0.0));

    if(best.s < N){
        int d=best.s;
        for(int c=0;c<N;c++) flowD[d][c]+=1.0/N;
    }else{
        int s0=best.s-N;
        if(0<=s0&&s0<M&&installed[s0]&&reachS[s0]){
            for(int c=0;c<N;c++) inflS[s0][c]+=1.0/N;
        }
    }

    for(int u: topo){
        if(!installed[u]) continue;
        double sm=0; for(int c=0;c<N;c++) sm+=inflS[u][c];
        if(sm==0) continue;

        int a=v1[u], b=v2[u];
        if(swapFlag[u]) std::swap(a,b);
        int k=curK[u];
        auto push=[&](int id,int c,double mass){
            if(mass==0) return;
            if(id<N) flowD[id][c]+=mass;
            else{
                int v=id-N; if(0<=v&&v<M) inflS[v][c]+=mass;
            }
        };
        for(int c=0;c<N;c++){
            double in=inflS[u][c]; if(in==0) continue;
            double p=prob[k][c];
            push(a,c,in*p);
            push(b,c,in*(1.0-p));
        }
    }
    return {inflS, flowD};
}

// ============ 割当固定で (k, swap) を逆トポ順に更新 ============
static void backward_pick_for_assignment(
    int N, int M, int K,
    const vector<char>& installed, const vector<int>& v1, const vector<int>& v2,
    const vector<vector<double>>& inflS,       // forward の各ソーター入口の色分布
    const vector<char>& reachS, const vector<int>& rtopo,
    const vector<int>& device_of_color,        // サイズ N: color c -> device d*
    vector<int>& curK, vector<char>& swapFlag,
    const vector<vector<double>>& prob
){
    auto Rdev = [&](int d,int c)->double{ return (device_of_color[c]==d)?1.0:0.0; };

    // R[u][c]: sorter u に入った色 c が「割当デバイスへ到達する」確率
    vector<vector<double>> R(M, vector<double>(N,0.0));

    auto childR = [&](int id,int c)->double{
        if(id<N) return Rdev(id,c);
        int v=id-N; if(0<=v&&v<M) return R[v][c];
        return 0.0;
    };

    for(int u: rtopo){
        if(!installed[u] || !reachS[u]) continue;

        int a0=v1[u], b0=v2[u];
        double bestVal=-1e100; int argK=curK[u]; char argS=swapFlag[u];

        // 子のRをキャッシュ
        vector<double> Ra(N), Rb(N);
        for(int c=0;c<N;c++){ Ra[c]=childR(a0,c); Rb[c]=childR(b0,c); }

        for(int k=0;k<K;k++){
            double vKeep=0.0, vSwap=0.0;
            for(int c=0;c<N;c++){
                double in = inflS[u][c];
                if(in==0) continue;
                double p = prob[k][c];
                vKeep += in*( p*Ra[c] + (1.0-p)*Rb[c] );
                vSwap += in*( p*Rb[c] + (1.0-p)*Ra[c] );
            }
            if(vKeep>bestVal){ bestVal=vKeep; argK=k; argS=0; }
            if(vSwap>bestVal){ bestVal=vSwap; argK=k; argS=1; }
        }

        curK[u]=argK; swapFlag[u]=argS;

        // 選んだ (k,swap) で R[u][c] を確定
        int aa=a0, bb=b0; if(argS) std::swap(aa,bb);
        for(int c=0;c<N;c++){
            double p = prob[argK][c];
            R[u][c] = p*childR(aa,c) + (1.0-p)*childR(bb,c);
        }
    }
}


// best を上書き最適化：分類器番号・出口入替・デバイス割当
// 依存: hungarian_max_assign / build_reach_and_topo / forward_flow_allcolors / backward_pick_for_assignment
// best を上書き最適化：分類器番号・出口入替・デバイス割当（改良版）
// best を上書き最適化：分類器番号・出口入替・デバイス割当（＋余剰時間での軽量ヒルクライム）
static void optimize_plan(
    Plan& best, int N, int M, int K,
    const vector<vector<double>>& prob,
    int iters = 10,
    int restarts = 10,
    int extra_hill_ms = 450,   // ★余剰時間で回すヒルクライムの時間上限（ms）
    int hill_L = 30,           // ★1ラウンドで試すノード数（margin 小い順）
    int hill_rounds = 100        // ★ラウンド数
){
    using namespace std::chrono;

    // ==== グラフ解析（固定配線） ====
    vector<char> installed; vector<int> v1, v2;
    vector<char> reachS; vector<int> topo, rtopo;
    build_reach_and_topo(best, N, M, best.lines,
                         installed, v1, v2, reachS, topo, rtopo);

    // 便利ラムダ
    auto sumv = [&](const vector<double>& a){ double s=0; for(double x:a)s+=x; return s; };
    auto gini = [&](const vector<double>& a){
        double S=sumv(a); if(S<=0) return 0.0; double s2=0; for(double x:a){ double p=x/S; s2+=p*p; }
        return 1.0 - s2;
    };
    auto inc_mix = [&](const vector<double>& before, const vector<double>& add){
        double Sb=0,Mb=0; for(double x:before){ Sb+=x; Mb=max(Mb,x); }
        double Sa=Sb, Ma=Mb;
        for(size_t i=0;i<add.size();++i){ double v=before[i]+add[i]; Sa+=add[i]; Ma=max(Ma,v); }
        return (Sa-Ma) - (Sb-Mb);
    };

    // ========== トップダウン初期化 ==========
    auto seed_topdown_once = [&](double w_branch, double w_dev, double w_sorter){
        vector<vector<double>> histS(M, vector<double>(N,0.0));
        vector<vector<double>> histD(N, vector<double>(N,0.0));

        vector<int>  initK(M,0);
        vector<char> initSwap(M,0);

        auto child_hist = [&](int id)->vector<double>&{
            return (id<N)? histD[id] : histS[id-N];
        };
        auto child_w = [&](int id){ return (id<N)? w_dev : w_sorter; };

        if(best.s >= N){
            int s0=best.s-N;
            if(0<=s0 && s0<M && installed[s0] && reachS[s0]){
                for(int c=0;c<N;c++) histS[s0][c]+=1.0/N;
            }
        }else{
            int d0=best.s;
            for(int c=0;c<N;c++) histD[d0][c]+=1.0/N;
        }

        for(int u: topo){
            if(!(u>=0 && u<M)) continue;
            if(!installed[u] || !reachS[u]) continue;
            auto &fin = histS[u];
            if(sumv(fin)==0) continue;
            int a=v1[u], b=v2[u]; if(a==-1||b==-1) continue;
            auto &HA=child_hist(a); auto &HB=child_hist(b);

            double bestCost=1e100; int argK=0; char argS=0;
            vector<double> fA(N), fB(N);
            for(int k=0;k<K;k++){
                for(int c=0;c<N;c++){ double p=prob[k][c], x=fin[c]; fA[c]=x*p; fB[c]=x*(1.0-p); }
                double SA=sumv(fA), SB=sumv(fB);
                double wA=(SA+SB>0)? SA/(SA+SB):0.0, wB=1.0-wA;
                double branch = w_branch*( wA*gini(fA) + wB*gini(fB) );
                double keep   = branch + child_w(a)*inc_mix(HA,fA) + child_w(b)*inc_mix(HB,fB);
                double swap   = branch + child_w(a)*inc_mix(HA,fB) + child_w(b)*inc_mix(HB,fA);
                if(keep<bestCost){ bestCost=keep; argK=k; argS=0; }
                if(swap<bestCost){ bestCost=swap; argK=k; argS=1; }
            }
            initK[u]=argK; initSwap[u]=argS;

            // 反映
            for(int c=0;c<N;c++){
                double p=prob[argK][c], x=fin[c];
                double L=x*p, R=x*(1.0-p);
                if(!argS){ child_hist(a)[c]+=L; child_hist(b)[c]+=R; }
                else     { child_hist(a)[c]+=R; child_hist(b)[c]+=L; }
            }
        }
        return pair<vector<int>,vector<char>>(std::move(initK), std::move(initSwap));
    };

    // ========== backward：最良＋次善手と margin を返す ==========
    auto backward_best_and_second = [&]( // curK/swap を最適にし、2番手とマージンも返す
        const vector<vector<double>>& inflS,
        const vector<int>& color2dev,
        vector<int>& curK, vector<char>& swapFlag,
        vector<int>& secK, vector<char>& secSwap, vector<double>& margin
    ){
        auto Rdev = [&](int d,int c)->double{ return (color2dev[c]==d)?1.0:0.0; };
        vector<vector<double>> R(M, vector<double>(N,0.0));
        auto childR = [&](int id,int c)->double{
            if(id<N) return Rdev(id,c);
            int v=id-N; if(0<=v&&v<M) return R[v][c];
            return 0.0;
        };
        secK.assign(M,0); secSwap.assign(M,0); margin.assign(M,0.0);

        for(int u: rtopo){
            if(!installed[u] || !reachS[u]) continue;
            int a0=v1[u], b0=v2[u];
            vector<double> Ra(N), Rb(N);
            for(int c=0;c<N;c++){ Ra[c]=childR(a0,c); Rb[c]=childR(b0,c); }

            double bestv=-1e100, second=-1e100; int argK=curK[u], argS=swapFlag[u];
            int argK2=0; char argS2=0;

            auto eval = [&](int k, int sw)->double{
                double val=0.0;
                for(int c=0;c<N;c++){
                    double in=inflS[u][c]; if(in==0) continue;
                    double p=prob[k][c];
                    if(!sw) val += in*( p*Ra[c] + (1.0-p)*Rb[c] );
                    else    val += in*( p*Rb[c] + (1.0-p)*Ra[c] );
                }
                return val;
            };

            for(int k=0;k<K;k++){
                double v0=eval(k,0);
                if(v0>bestv){ second=bestv; argK2=argK; argS2=argS; bestv=v0; argK=k; argS=0; }
                else if(v0>second){ second=v0; argK2=k; argS2=0; }
                double v_sw=eval(k,1); // ← rename: v1 -> v_sw（shadow 回避）
                if(v_sw>bestv){ second=bestv; argK2=argK; argS2=argS; bestv=v_sw; argK=k; argS=1; }
                else if(v_sw>second){ second=v_sw; argK2=k; argS2=1; }
            }
            curK[u]=argK; swapFlag[u]=argS;
            secK[u]=argK2; secSwap[u]=argS2; margin[u]=bestv-second;

            // R[u] を確定（best）
            int aa=a0, bb=b0; if(argS) std::swap(aa,bb);
            for(int c=0;c<N;c++){
                double p=prob[argK][c];
                R[u][c] = p*childR(aa,c) + (1.0-p)*childR(bb,c);
            }
        }
    };

    // ========== 評価 ==========
    auto score_from_flow = [&](const vector<vector<double>>& flowD,
                               const vector<int>& color2dev)->double{
        double s=0.0;
        for(int c=0;c<N;c++){ int d=color2dev[c]; if(0<=d && d<N) s+=flowD[d][c]; }
        return s;
    };
    auto eval_with_hungarian = [&](const vector<int>& curK, const vector<char>& swapFlag,
                                   vector<int>* out_assign=nullptr, vector<vector<double>>* out_flowD=nullptr)->double{
        auto fp = forward_flow_allcolors(best, N, M, K, installed, v1, v2, curK, swapFlag, reachS, topo, prob);
        vector<vector<double>> W(N, vector<double>(N,0.0));
        for(int d=0; d<N; ++d) for(int c=0; c<N; ++c) W[c][d]=fp.flowD[d][c];
        auto col2dev = hungarian_max_assign(W);
        if(out_assign) *out_assign = col2dev;
        if(out_flowD)  *out_flowD  = fp.flowD;
        return score_from_flow(fp.flowD, col2dev);
    };

    // ベスト解の保持
    double bestScore=-1.0; vector<int> best_d(N,-1);
    vector<int>  bestK; vector<char> bestSwap;

    std::mt19937 rng(1234567);

    // ==== シード集合 ====
    vector<pair<vector<int>,vector<char>>> seeds;
    { // 既存 lines
        vector<int> k0(M,0); vector<char> s0(M,0);
        for(int i=0;i<M;i++) if(installed[i]){
            int k,a,b; stringstream ss(best.lines[i]); ss>>k>>a>>b;
            k0[i]=max(0,min(K-1,k));
        }
        seeds.push_back({std::move(k0), std::move(s0)});
    }
    seeds.push_back( seed_topdown_once(0.35,  1.00, 0.25) );
    seeds.push_back( seed_topdown_once(0.35,  1.30, 0.35) );
    while((int)seeds.size()<restarts){
        vector<int> k(M,0); vector<char> s(M,0);
        for(int i=0;i<M;i++) if(installed[i]){
            if(K>1 && (rng()%3==0)) k[i]=rng()%K;
            if(rng()%5==0) s[i]=1;
        }
        seeds.push_back({std::move(k), std::move(s)});
    }

    // ==== 各シードで探索 ====
    for(auto seed : seeds){
        vector<int>  curK = std::move(seed.first);
        vector<char> swapFlag = std::move(seed.second);

        // 小さな初期摂動
        for(int i=0;i<M;i++) if(installed[i] && rng()%12==0){
            if(K>1) curK[i]=(curK[i]+1+(rng()%2))%K;
            if(rng()%2) swapFlag[i]^=1;
        }

        vector<int> color2dev(N,0);

        for(int it=0; it<iters; ++it){
            // forward
            auto fp = forward_flow_allcolors(best, N, M, K,
                                             installed, v1, v2,
                                             curK, swapFlag,
                                             reachS, topo, prob);

            // Hungarian（色→デバイス）
            vector<vector<double>> W(N, vector<double>(N,0.0));
            for(int d=0; d<N; ++d) for(int c=0; c<N; ++c) W[c][d]=fp.flowD[d][c];
            auto col2dev = hungarian_max_assign(W);
            color2dev = col2dev;

            // backward：最良＋次善手と margin
            vector<int> secK; vector<char> secSwap; vector<double> margin;
            backward_best_and_second(fp.inflS, color2dev,
                                     curK, swapFlag,
                                     secK, secSwap, margin);

            // 少数ノードに摂動（マージン小を優先）
            vector<int> idx; idx.reserve(M);
            for(int i=0;i<M;i++) if(installed[i] && reachS[i]) idx.push_back(i);
            int perturb = max(1, (int)(idx.size() * (0.05 + 0.10*(iters-1-it)/max(1,iters-1)))); // 5〜15%
            perturb = min(perturb, (int)idx.size());
            nth_element(idx.begin(), idx.begin()+perturb, idx.end(),
                        [&](int a,int b){ return margin[a] < margin[b]; });
            for(int t=0;t<perturb; ++t){
                int u = idx[t];
                curK[u] = secK[u];
                if( (bool)swapFlag[u] != (bool)secSwap[u] ) swapFlag[u] ^= 1;
            }
        }

        // 仕上げ forward & Hungarian でスコア
        vector<vector<double>> flowD;
        auto fp_score = eval_with_hungarian(curK, swapFlag, nullptr, &flowD);

        if(fp_score > bestScore){
            bestScore = fp_score;
            // 割当を色→デバイスからデバイス→色へ
            vector<vector<double>> W(N, vector<double>(N,0.0));
            for(int d=0; d<N; ++d) for(int c=0; c<N; ++c) W[c][d]=flowD[d][c];
            auto col2dev = hungarian_max_assign(W);
            best_d.assign(N,-1);
            for(int c=0;c<N;c++){ int d=col2dev[c]; if(0<=d && d<N) best_d[d]=c; }
            bestK = curK; bestSwap = swapFlag;
        }
    }

    // ==== ★ 余剰時間ヒルクライム（sec-best ピボット）====
    {
        auto t0 = steady_clock::now();
        vector<int> curK = bestK; vector<char> swapFlag = bestSwap;

        // 現在の割当・流量
        vector<int> color2dev;
        vector<vector<double>> flowD;
        double curScore = eval_with_hungarian(curK, swapFlag, &color2dev, &flowD);

        // inflS を得るため forward を一度（割当は使わない）
        auto fp0 = forward_flow_allcolors(best, N, M, K, installed, v1, v2, curK, swapFlag, reachS, topo, prob);

        for(int rd=0; rd<hill_rounds; ++rd){
            // backward で “2番手” と margin を用意
            vector<int> secK; vector<char> secSwap; vector<double> margin;
            backward_best_and_second(fp0.inflS, color2dev, curK, swapFlag, secK, secSwap, margin);

            // 候補ノード（margin 小さい順 上位 L）
            vector<int> cand; cand.reserve(M);
            for(int u=0;u<M;u++) if(installed[u] && reachS[u]) cand.push_back(u);
            int L = min(hill_L, (int)cand.size());
            nth_element(cand.begin(), cand.begin()+L, cand.end(),
                        [&](int a,int b){ return margin[a] < margin[b]; });
            cand.resize(L);

            bool improved = false;
            for(int u: cand){
                if(duration_cast<milliseconds>(steady_clock::now()-t0).count() > extra_hill_ms) break;

                // ピボットして評価
                int oldK = curK[u]; char oldS = swapFlag[u];
                curK[u] = secK[u];
                if( (bool)swapFlag[u] != (bool)secSwap[u] ) swapFlag[u] ^= 1;

                double sc = eval_with_hungarian(curK, swapFlag);
                if(sc > curScore + 1e-12){
                    curScore = sc; improved = true;
                    // forward も更新（次ラウンドの inflS 用）
                    fp0 = forward_flow_allcolors(best, N, M, K, installed, v1, v2, curK, swapFlag, reachS, topo, prob);
                    // color2dev も更新
                    vector<vector<double>> W(N, vector<double>(N,0.0));
                    for(int d=0; d<N; ++d) for(int c=0; c<N; ++c) W[c][d]=fp0.flowD[d][c];
                    color2dev = hungarian_max_assign(W);
                }else{
                    // 戻す
                    curK[u] = oldK; swapFlag[u] = oldS;
                }
            }
            if(!improved) break;
        }

        if(curScore > bestScore + 1e-12){
            bestScore = curScore;
            // 最終の割当を更新
            auto fp = forward_flow_allcolors(best, N, M, K, installed, v1, v2, curK, swapFlag, reachS, topo, prob);
            vector<vector<double>> W(N, vector<double>(N,0.0));
            for(int d=0; d<N; ++d) for(int c=0; c<N; ++c) W[c][d]=fp.flowD[d][c];
            auto col2dev = hungarian_max_assign(W);
            best_d.assign(N,-1);
            for(int c=0;c<N;c++){ int d=col2dev[c]; if(0<=d && d<N) best_d[d]=c; }
            bestK = std::move(curK); bestSwap = std::move(swapFlag);
        }
    }

    // ==== Plan に書き戻し ====
    if(bestScore >= 0.0){
        best.d = best_d;
        for(int i=0;i<M;i++){
            if(best.lines[i]=="-1") continue;
            int dummy,a,b; { stringstream ss(best.lines[i]); ss>>dummy>>a>>b; }
            int k = (i<(int)bestK.size()? bestK[i] : 0);
            if(i<(int)bestSwap.size() && bestSwap[i]) std::swap(a,b);
            best.lines[i] = to_string(k) + " " + to_string(a) + " " + to_string(b);
        }
    }
}

// ===================== main =====================
// 既存の P, Plan, Builder, has_crossing を利用
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N,M,K;
    if(!(cin>>N>>M>>K)) return 0;

    vector<P> dev(N), sor(M);
    for(int i=0;i<N;i++) cin>>dev[i].x>>dev[i].y;
    for(int i=0;i<M;i++) cin>>sor[i].x>>sor[i].y;

    vector<vector<double>> prob(K, vector<double>(N,0.5));
    for(int k=0;k<K;k++) for(int c=0;c<N;c++){ double x; cin>>x; prob[k][c]=x; }

    // 既存ビルダ（グラフは変えない）
    vector<int> Bs = {16,14,12,10,8,6,4,2};
    Plan best; bool found=false;
    int chosen_B = -1;
    for(int B: Bs){
        Builder bd(N,M,K,B,dev,sor);
        Plan p = bd.build();
        if(!has_crossing(p.segments)){ best=std::move(p); found=true; break; }
    }
    if(!found){
        for(int i=0;i<N;i++){ if(i) cout<<' '; cout<<i; } cout<<"\n";
        cout<<0<<"\n";
        for(int i=0;i<M;i++) cout<<-1<<"\n";
        return 0;
    }

    // ★ 交互最適化（Forward→Hungarian→Backward）
    // reorient_edges_bfs_snake_downhill(best, N, M, chosen_B, sor);
    // reorient_edges_by_lane_x(best, N, M, chosen_B, sor);
    optimize_plan(best, N, M, K, prob);

    // 出力
    for(int i=0;i<N;i++){ if(i) cout<<' '; cout<<best.d[i]; } cout<<"\n";
    cout<<best.s<<"\n";
    for(int i=0;i<M;i++) cout<<best.lines[i]<<"\n";
    return 0;
}

提出情報

コンパイルエラー

Main.cpp: In function ‘FlowPack forward_flow_allcolors(const Plan&, int, int, int, const std::vector<char>&, const std::vector<int>&, const std::vector<int>&, const std::vector<int>&, const std::vector<char>&, const std::vector<char>&, const std::vector<int>&, const std::vector<std::vector<double> >&)’:
Main.cpp:715:41: warning: unused parameter ‘K’ [-Wunused-parameter]
  715 |     const Plan& best, int N, int M, int K,
      |                                     ~~~~^
Main.cpp: In function ‘int main()’:
Main.cpp:1165:9: warning: unused variable ‘chosen_B’ [-Wunused-variable]
 1165 |     int chosen_B = -1;
      |         ^~~~~~~~
Main.cpp: At global scope:
Main.cpp:760:13: warning: ‘void backward_pick_for_assignment(int, int, int, const std::vector<char>&, const std::vector<int>&, const std::vector<int>&, const std::vector<std::vector<double> >&, const std::vector<char>&, const std::vector<int>&, const std::vector<int>&, std::vector<int>&, std::vector<char>&, const std::vector<std::vector<double> >&)’ defined but not used [-Wunused-function]
  760 | static void backward_pick_for_assignment(
      |             ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:101:13: warning: ‘void add_snake_same_lane_and_bridges(const std::vector<std::vector<int> >&, const std::vector<P>&, std::vector<std::vector<int> >&, std::vector<int>&, std::vector<std::pair<P, P> >&)’ defined but not used [-Wunused-function]
  101 | static void add_snake_same_lane_and_bridges(
      |             ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

ジャッジ結果