提出 #76877085

---

ソースコード 拡げる

#include <algorithm>
#include <array>
#include <chrono>
#include <cstdint>
#include <functional>
#include <iostream>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;

struct Candidate {
    int level = 0;
    vector<int> path;
    vector<int> edges;
    vector<int> seals;
    int bypass_length = 0;
    int score = 0;
};

struct DoorOut {
    int d, i, j, type;
};

struct SwitchOut {
    int i, j, type;
};

class Solver {
    using Clock = chrono::steady_clock;
    int N, M, K, V;
    vector<string> board;
    vector<vector<int>> adj;
    vector<int> vertices;
    vector<int> all_edges;
    vector<vector<int>> corridors;
    vector<vector<int>> cycles;
    vector<vector<Candidate>> candidates;
    bool debug;
    int start = 0, goal;
    long long search_nodes = 0;
    long long search_limit = 2000;
    Clock::time_point started_at = Clock::now();
    static constexpr double TIME_LIMIT_SEC = 1.55;

    bool time_up() const {
        return chrono::duration<double>(Clock::now() - started_at).count() >=
               TIME_LIMIT_SEC;
    }

    int edge_id(int a, int b) const {
        if (a > b) swap(a, b);
        return a * V + b;
    }
    pair<int, int> edge_vertices(int id) const {
        return {id / V, id % V};
    }
    bool contains_sorted(const vector<int>& a, int x) const {
        return binary_search(a.begin(), a.end(), x);
    }
    static void sort_unique(vector<int>& a) {
        sort(a.begin(), a.end());
        a.erase(unique(a.begin(), a.end()), a.end());
    }
    static bool intersects(const vector<int>& a, const vector<int>& b) {
        size_t i = 0, j = 0;
        while (i < a.size() && j < b.size()) {
            if (a[i] == b[j]) return true;
            if (a[i] < b[j]) ++i;
            else ++j;
        }
        return false;
    }
    static vector<int> united(const vector<int>& a, const vector<int>& b) {
        vector<int> r;
        r.reserve(a.size() + b.size());
        set_union(a.begin(), a.end(), b.begin(), b.end(), back_inserter(r));
        return r;
    }
    vector<char> component(const vector<int>& blocked, int source = 0) const {
        vector<char> seen(V, false);
        queue<int> q;
        seen[source] = true;
        q.push(source);
        while (!q.empty()) {
            int v = q.front();
            q.pop();
            for (int w : adj[v]) {
                if (seen[w] || contains_sorted(blocked, edge_id(v, w))) continue;
                seen[w] = true;
                q.push(w);
            }
        }
        return seen;
    }
    int shortest_without_edges(int source, int target, const vector<int>& blocked) const {
        vector<int> dist(V, -1);
        queue<int> q;
        dist[source] = 0;
        q.push(source);
        while (!q.empty()) {
            int v = q.front();
            q.pop();
            if (v == target) return dist[v];
            for (int w : adj[v]) {
                if (dist[w] >= 0 || contains_sorted(blocked, edge_id(v, w))) continue;
                dist[w] = dist[v] + 1;
                q.push(w);
            }
        }
        return -1;
    }
    vector<int> distances(int source, const vector<int>& blocked = {}) const {
        vector<int> dist(V, -1);
        queue<int> q;
        dist[source] = 0;
        q.push(source);
        while (!q.empty()) {
            int v = q.front();
            q.pop();
            for (int w : adj[v]) {
                if (dist[w] >= 0 || contains_sorted(blocked, edge_id(v, w))) continue;
                dist[w] = dist[v] + 1;
                q.push(w);
            }
        }
        return dist;
    }

    vector<vector<int>> list_corridors() const {
        vector<char> terminal(V, false);
        for (int v : vertices) {
            terminal[v] = (adj[v].size() != 2 || v == start || v == goal);
        }
        unordered_set<int> used;
        vector<vector<int>> result;
        for (int begin : vertices) if (terminal[begin]) {
            for (int first : adj[begin]) {
                int e = edge_id(begin, first);
                if (used.count(e)) continue;
                used.insert(e);
                vector<int> path{begin, first};
                int prev = begin, cur = first;
                while (!terminal[cur]) {
                    int nxt = adj[cur][0] == prev ? adj[cur][1] : adj[cur][0];
                    used.insert(edge_id(cur, nxt));
                    path.push_back(nxt);
                    prev = cur;
                    cur = nxt;
                }
                result.push_back(move(path));
            }
        }
        return result;
    }

    string cycle_key(const vector<int>& path) const {
        vector<int> es;
        es.reserve(path.size());
        for (int i = 0; i < (int)path.size(); ++i) {
            es.push_back(edge_id(path[i], path[(i + 1) % path.size()]));
        }
        sort(es.begin(), es.end());
        string key;
        key.reserve(es.size() * 5);
        for (int e : es) {
            key += to_string(e);
            key.push_back(',');
        }
        return key;
    }
    void add_cycle(vector<vector<int>>& result, unordered_set<string>& keys,
                   const vector<int>& path) const {
        if (path.size() < 4) return;
        unordered_set<int> vs(path.begin(), path.end());
        if (vs.size() != path.size()) return;
        string key = cycle_key(path);
        if (keys.insert(key).second) result.push_back(path);
    }
    void add_fundamental_cycles(vector<vector<int>>& result, unordered_set<string>& keys,
                                const vector<int>& parent, const vector<int>& depth) const {
        for (int eid : all_edges) {
            auto [u0, v0] = edge_vertices(eid);
            if (parent[u0] == v0 || parent[v0] == u0) continue;
            int a = u0, b = v0;
            vector<int> left{a}, right{b};
            while (depth[a] > depth[b]) {
                a = parent[a];
                left.push_back(a);
            }
            while (depth[b] > depth[a]) {
                b = parent[b];
                right.push_back(b);
            }
            while (a != b) {
                a = parent[a];
                b = parent[b];
                left.push_back(a);
                right.push_back(b);
            }
            vector<int> path = left;
            for (int i = (int)right.size() - 2; i >= 0; --i) path.push_back(right[i]);
            add_cycle(result, keys, path);
        }
    }
    vector<vector<int>> list_cycles() const {
        vector<vector<int>> result;
        unordered_set<string> keys;
        uint64_t seed = 0;
        for (int i = 0; i < N; ++i) for (char c : board[i]) {
            seed = seed * 1000003ULL + (uint64_t)(i + 1) * (unsigned char)c;
        }
        mt19937_64 rng(seed);
        // C++ではPython版より多くのDFS順を安価に試せる。
        for (int trial = 0; trial < 8; ++trial) {
            vector<int> parent(V, -2), depth(V, -1), order_index(V, 0);
            vector<vector<int>> shuffled = adj;
            for (int v : vertices) shuffle(shuffled[v].begin(), shuffled[v].end(), rng);
            parent[start] = -1;
            depth[start] = 0;
            vector<int> stack{start};
            while (!stack.empty()) {
                int v = stack.back();
                if (order_index[v] == (int)shuffled[v].size()) {
                    stack.pop_back();
                    continue;
                }
                int w = shuffled[v][order_index[v]++];
                if (parent[w] != -2) continue;
                parent[w] = v;
                depth[w] = depth[v] + 1;
                stack.push_back(w);
            }
            add_fundamental_cycles(result, keys, parent, depth);
        }
        // 各辺を除いた最短迂回路も残す。
        for (int removed : all_edges) {
            auto [s, t] = edge_vertices(removed);
            vector<int> prev(V, -2);
            queue<int> q;
            prev[s] = -1;
            q.push(s);
            while (!q.empty() && prev[t] == -2) {
                int v = q.front();
                q.pop();
                for (int w : adj[v]) {
                    if (edge_id(v, w) == removed || prev[w] != -2) continue;
                    prev[w] = v;
                    q.push(w);
                }
            }
            if (prev[t] == -2) continue;
            vector<int> path;
            for (int cur = t; cur >= 0; cur = prev[cur]) path.push_back(cur);
            reverse(path.begin(), path.end());
            add_cycle(result, keys, path);
        }
        return result;
    }

    vector<int> minimum_path_seals(const vector<int>& path,
                                   const vector<int>& path_edges) const {
        vector<int> index(V, -1);
        vector<char> in_path(V, false);
        for (int i = 0; i < (int)path.size(); ++i) {
            index[path[i]] = i;
            in_path[path[i]] = true;
        }
        unordered_set<int> seal_set;
        for (int x = 0; x < (int)path.size(); ++x) {
            int v = path[x];
            for (int w : adj[v]) {
                int y = index[w], e = edge_id(v, w);
                if (y < 0 || contains_sorted(path_edges, e)) continue;
                if ((x == 0 && y == (int)path.size() - 1) ||
                    (y == 0 && x == (int)path.size() - 1)) continue;
                seal_set.insert(e);
            }
        }
        vector<char> seen(V, false);
        for (int root : vertices) {
            if (in_path[root] || seen[root]) continue;
            vector<int> comp;
            queue<int> q;
            q.push(root);
            seen[root] = true;
            while (!q.empty()) {
                int v = q.front();
                q.pop();
                comp.push_back(v);
                for (int w : adj[v]) {
                    if (in_path[w] || seen[w]) continue;
                    seen[w] = true;
                    q.push(w);
                }
            }
            vector<vector<int>> attachments(path.size());
            bool has_start = false, has_goal = false;
            for (int v : comp) {
                has_start |= (v == start);
                has_goal |= (v == goal);
                for (int w : adj[v]) if (index[w] >= 0) {
                    attachments[index[w]].push_back(edge_id(v, w));
                }
            }
            vector<int> attached_indices;
            for (int i = 0; i < (int)attachments.size(); ++i) {
                if (!attachments[i].empty()) attached_indices.push_back(i);
            }
            if (attached_indices.empty()) continue;
            vector<char> allowed(path.size(), false);
            bool endpoint_attached = !attachments.front().empty() || !attachments.back().empty();
            if (has_start || has_goal || endpoint_attached) {
                if (!attachments.front().empty()) allowed[0] = true;
                if (!attachments.back().empty()) allowed[path.size() - 1] = true;
            } else {
                int best = attached_indices[0];
                for (int x : attached_indices) {
                    if (attachments[x].size() > attachments[best].size()) best = x;
                }
                allowed[best] = true;
            }
            for (int x : attached_indices) if (!allowed[x]) {
                for (int e : attachments[x]) seal_set.insert(e);
            }
        }
        vector<int> seals(seal_set.begin(), seal_set.end());
        sort(seals.begin(), seals.end());
        return seals;
    }

    vector<Candidate> enumerate_candidates(int level) const {
        int required = 3 * level + 2;
        vector<int> start_dist = distances(start);
        unordered_map<string, pair<vector<int>, int>> raw;
        auto add_raw = [&](const vector<int>& path, int remainder) {
            string key;
            key.reserve(path.size() * 4);
            for (int v : path) {
                key += to_string(v);
                key.push_back(',');
            }
            auto it = raw.find(key);
            if (it == raw.end() || remainder > it->second.second) {
                raw[key] = {path, remainder};
            }
        };
        for (const auto& corridor : corridors) {
            int ec = (int)corridor.size() - 1;
            if (ec < required) continue;
            vector<int> lengths{required, min(ec, required + 4),
                                min(ec, required + 8), ec};
            sort_unique(lengths);
            for (int len : lengths) for (int off = 0; off + len <= ec; ++off) {
                vector<int> path(corridor.begin() + off, corridor.begin() + off + len + 1);
                add_raw(path, 1000);
                reverse(path.begin(), path.end());
                add_raw(path, 1000);
            }
        }
        for (const auto& cyc : cycles) {
            int cs = cyc.size();
            if (cs <= required) continue;
            int mx = cs - 1;
            vector<int> lengths{required, min(mx, required + 4), min(mx, required + 8),
                                max(required, cs / 3), max(required, cs / 2),
                                max(required, cs * 2 / 3), mx};
            sort_unique(lengths);
            for (int len : lengths) for (int begin = 0; begin < cs; ++begin) {
                for (int dir : {-1, 1}) {
                    vector<int> path;
                    path.reserve(len + 1);
                    for (int x = 0; x <= len; ++x) {
                        int p = (begin + dir * x) % cs;
                        if (p < 0) p += cs;
                        path.push_back(cyc[p]);
                    }
                    add_raw(path, cs - len);
                }
            }
        }
        vector<pair<vector<int>, int>> ranked;
        ranked.reserve(raw.size());
        for (auto& [_, value] : raw) ranked.push_back(move(value));
        sort(ranked.begin(), ranked.end(), [&](const auto& a, const auto& b) {
            auto value = [&](const auto& x) {
                const auto& p = x.first;
                return x.second * 16 + ((int)p.size() - 1) * 4 +
                       min(start_dist[p.front()], start_dist[p.back()]);
            };
            return value(a) > value(b);
        });
        vector<Candidate> result;
        int inspect = min<int>(ranked.size(), 1500);
        for (int ri = 0; ri < inspect; ++ri) {
            const vector<int>& path = ranked[ri].first;
            if (find(path.begin() + 1, path.end() - 1, start) != path.end() - 1 ||
                find(path.begin() + 1, path.end() - 1, goal) != path.end() - 1) continue;
            vector<int> path_edges;
            for (int i = 0; i + 1 < (int)path.size(); ++i) {
                path_edges.push_back(edge_id(path[i], path[i + 1]));
            }
            sort_unique(path_edges);
            vector<int> seals = minimum_path_seals(path, path_edges);
            if ((int)seals.size() > M - 2 * (level + 1)) continue;
            vector<int> blocked = united(path_edges, seals);
            vector<char> comp = component(blocked);
            if (!comp[goal] || !comp[path.front()] || !comp[path.back()]) continue;
            int bypass = shortest_without_edges(path.front(), path.back(), blocked);
            if (bypass < 0) continue;
            int remoteness = min(start_dist[path.front()], start_dist[path.back()]);
            int score = bypass * 16 + remoteness +
                        ((int)path.size() - required - 1) * 4 -
                        (int)seals.size() * 80;
            result.push_back(Candidate{level, path, path_edges, seals, bypass, score});
        }
        vector<int> ids(result.size());
        iota(ids.begin(), ids.end(), 0);
        vector<vector<int>> orders;
        auto make_order = [&](auto cmp) {
            vector<int> o = ids;
            sort(o.begin(), o.end(), cmp);
            orders.push_back(move(o));
        };
        make_order([&](int a, int b) { return result[a].score > result[b].score; });
        make_order([&](int a, int b) {
            return tuple(-int(result[a].seals.size()), result[a].bypass_length,
                         int(result[a].path.size())) >
                   tuple(-int(result[b].seals.size()), result[b].bypass_length,
                         int(result[b].path.size()));
        });
        make_order([&](int a, int b) {
            return tuple(result[a].bypass_length, -int(result[a].seals.size()), result[a].score) >
                   tuple(result[b].bypass_length, -int(result[b].seals.size()), result[b].score);
        });
        make_order([&](int a, int b) {
            return tuple(int(result[a].path.size()), -int(result[a].seals.size()), result[a].score) >
                   tuple(int(result[b].path.size()), -int(result[b].seals.size()), result[b].score);
        });
        vector<Candidate> picked;
        unordered_set<string> used;
        for (const auto& order : orders) {
            int take = min<int>(50, order.size());
            for (int z = 0; z < take; ++z) {
                const Candidate& c = result[order[z]];
                string key;
                for (int v : c.path) key += to_string(v) + ",";
                if (used.insert(key).second) picked.push_back(c);
            }
        }
        sort(picked.begin(), picked.end(),
             [](const Candidate& a, const Candidate& b) { return a.score > b.score; });
        if (picked.size() > 160) picked.resize(160);
        return picked;
    }

    vector<int> sg_bridges(const vector<int>& blocked) const {
        vector<char> comp = component(blocked);
        if (!comp[goal]) return {};
        vector<int> tin(V, -1), low(V, -1), parent(V, -1);
        unordered_set<int> bridge_set;
        int timer = 0;
        function<void(int, int)> dfs = [&](int v, int p) {
            tin[v] = low[v] = timer++;
            for (int w : adj[v]) {
                int e = edge_id(v, w);
                if (!comp[w] || contains_sorted(blocked, e) || w == p) continue;
                if (tin[w] >= 0) low[v] = min(low[v], tin[w]);
                else {
                    parent[w] = v;
                    dfs(w, v);
                    low[v] = min(low[v], low[w]);
                    if (low[w] > tin[v]) bridge_set.insert(e);
                }
            }
        };
        dfs(start, -1);
        vector<int> result;
        int cur = goal;
        while (cur != start) {
            if (parent[cur] < 0) return {};
            int e = edge_id(cur, parent[cur]);
            if (bridge_set.count(e)) result.push_back(e);
            cur = parent[cur];
        }
        reverse(result.begin(), result.end());
        return result;
    }
    vector<int> final_gate_edges(const vector<int>& blocked,
                                 const vector<int>& endpoints, int needed) const {
        vector<int> eligible;
        for (int bridge : sg_bridges(blocked)) {
            vector<int> cut = blocked;
            auto it = lower_bound(cut.begin(), cut.end(), bridge);
            cut.insert(it, bridge);
            vector<char> side = component(cut);
            if (side[goal]) continue;
            bool ok = true;
            for (int v : endpoints) ok &= side[v];
            if (ok) eligible.push_back(bridge);
        }
        if ((int)eligible.size() < needed) return {};
        return vector<int>(eligible.end() - needed, eligible.end());
    }

    bool common_component_ok(const vector<const Candidate*>& selected) const {
        vector<int> blocked, endpoints{start, goal};
        for (const Candidate* c : selected) {
            blocked.insert(blocked.end(), c->edges.begin(), c->edges.end());
            blocked.insert(blocked.end(), c->seals.begin(), c->seals.end());
            endpoints.push_back(c->path.front());
            endpoints.push_back(c->path.back());
        }
        sort_unique(blocked);
        vector<char> comp = component(blocked);
        for (int v : endpoints) if (!comp[v]) return false;
        return true;
    }
    bool try_select(const vector<int>& levels, int at,
                    vector<const Candidate*>& selected,
                    vector<const Candidate*>& answer,
                    vector<int>& answer_final) {
        if (++search_nodes > search_limit) return false;
        if (at == (int)levels.size()) {
            if (!common_component_ok(selected)) return false;
            vector<int> blocked, endpoints;
            int gadget_doors = 0;
            for (const Candidate* c : selected) {
                blocked.insert(blocked.end(), c->edges.begin(), c->edges.end());
                blocked.insert(blocked.end(), c->seals.begin(), c->seals.end());
                endpoints.push_back(c->path.front());
                endpoints.push_back(c->path.back());
                gadget_doors += 2 * (c->level + 1);
            }
            sort_unique(blocked);
            int needed = levels.empty() ? 1 : levels.front() + 1;
            vector<int> final_edges = final_gate_edges(blocked, endpoints, needed);
            unordered_set<int> seal_set;
            for (const Candidate* c : selected) {
                seal_set.insert(c->seals.begin(), c->seals.end());
            }
            if ((int)final_edges.size() == needed &&
                gadget_doors + (int)seal_set.size() + needed <= M) {
                answer = selected;
                answer_final = move(final_edges);
                return true;
            }
            return false;
        }
        int level = levels[at];
        vector<char> existing_internal(V, false), existing_all(V, false);
        vector<int> existing_edges, existing_seals;
        int gadget_doors = 0;
        for (const Candidate* c : selected) {
            gadget_doors += 2 * (c->level + 1);
            for (int v : c->path) existing_all[v] = true;
            for (int i = 1; i + 1 < (int)c->path.size(); ++i) existing_internal[c->path[i]] = true;
            existing_edges.insert(existing_edges.end(), c->edges.begin(), c->edges.end());
            existing_seals.insert(existing_seals.end(), c->seals.begin(), c->seals.end());
        }
        sort_unique(existing_edges);
        sort_unique(existing_seals);
        for (const Candidate& c : candidates[level]) {
            bool bad = false;
            for (int i = 1; i + 1 < (int)c.path.size(); ++i) bad |= existing_all[c.path[i]];
            bad |= existing_internal[c.path.front()] || existing_internal[c.path.back()];
            if (bad || intersects(c.edges, existing_seals) || intersects(c.seals, existing_edges)) continue;
            vector<int> all_seals = united(existing_seals, c.seals);
            int minimum_final = levels.front() + 1;
            if (gadget_doors + 2 * (c.level + 1) +
                    (int)all_seals.size() + minimum_final > M) continue;
            selected.push_back(&c);
            if (try_select(levels, at + 1, selected, answer, answer_final)) return true;
            selected.pop_back();
        }
        return false;
    }

    tuple<int, vector<const Candidate*>, vector<int>> select_layout() {
        int max_level = min(5, K - 1);
        candidates.assign(max_level + 1, {});
        for (int level = 1; level <= max_level; ++level) {
            candidates[level] = enumerate_candidates(level);
        }
        for (int level = max_level; level >= 0; --level) {
            vector<int> levels;
            for (int x = level; x >= 1; --x) levels.push_back(x);
            if (debug) {
                cerr << "target level " << level << " cycles " << cycles.size() << " candidates";
                for (int x : levels) cerr << " " << x << ":" << candidates[x].size();
                cerr << '\n';
            }
            bool missing = false;
            for (int x : levels) missing |= candidates[x].empty();
            if (missing) continue;
            search_nodes = 0;
            vector<const Candidate*> selected, answer;
            vector<int> final_edges;
            if (try_select(levels, 0, selected, answer, final_edges)) {
                if (debug) cerr << "search nodes " << search_nodes << '\n';
                return {level, answer, final_edges};
            }
            if (debug) cerr << "search nodes " << search_nodes << '\n';
        }
        vector<int> bridges = sg_bridges({});
        vector<int> fallback;
        if (!bridges.empty()) fallback.push_back(bridges.back());
        return {0, {}, fallback};
    }

    DoorOut edge_to_output(int eid, int type) const {
        auto [a, b] = edge_vertices(eid);
        int ai = a / N, aj = a % N, bi = b / N, bj = b % N;
        if (aj == bj) return {0, min(ai, bi), aj, type};
        return {1, ai, min(aj, bj), type};
    }
    pair<vector<DoorOut>, vector<SwitchOut>>
    build_gadgets(const vector<const Candidate*>& selected) const {
        vector<DoorOut> doors;
        vector<SwitchOut> switches;
        unordered_set<int> seal_set;
        for (const Candidate* c : selected) {
            int level = c->level, ec = c->path.size() - 1;
            for (int x = 0; x < level; ++x) {
                doors.push_back(edge_to_output(edge_id(c->path[x], c->path[x + 1]), 2 * x + 1));
            }
            doors.push_back(edge_to_output(edge_id(c->path[level], c->path[level + 1]), 2 * level));
            int first_switch = level + 1, last_switch = ec - level - 1;
            for (int bit = 0; bit <= level; ++bit) {
                int index = first_switch + (last_switch - first_switch) * bit / level;
                int v = c->path[index];
                switches.push_back({v / N, v % N, bit});
            }
            int first_post = ec - level - 1;
            for (int x = 0; x < level; ++x) {
                doors.push_back(edge_to_output(
                    edge_id(c->path[first_post + x], c->path[first_post + x + 1]), 2 * x));
            }
            doors.push_back(edge_to_output(
                edge_id(c->path[ec - 1], c->path[ec]), 2 * level + 1));
            seal_set.insert(c->seals.begin(), c->seals.end());
        }
        vector<int> seals(seal_set.begin(), seal_set.end());
        sort(seals.begin(), seals.end());
        for (int e : seals) doors.push_back(edge_to_output(e, 19));
        return {doors, switches};
    }

    int shortest_actions(int used_bits, const vector<DoorOut>& doors,
                         const vector<SwitchOut>& switches) const {
        vector<int> door_map(V * V, -1), switch_map(V, -1);
        for (const auto& d : doors) {
            int a = d.i * N + d.j;
            int b = d.d == 0 ? (d.i + 1) * N + d.j : d.i * N + d.j + 1;
            door_map[edge_id(a, b)] = d.type;
        }
        for (const auto& s : switches) switch_map[s.i * N + s.j] = s.type;
        int masks = 1 << used_bits;
        vector<int> dist(V * masks, -1), q(V * masks);
        int head = 0, tail = 0;
        q[tail++] = start;
        dist[start] = 0;
        while (head < tail) {
            int state = q[head++], mask = state / V, v = state % V;
            if (v == goal) return dist[state];
            if (switch_map[v] >= 0) {
                int ns = (mask ^ (1 << switch_map[v])) * V + v;
                if (dist[ns] < 0) {
                    dist[ns] = dist[state] + 1;
                    q[tail++] = ns;
                }
            }
            for (int w : adj[v]) {
                int type = door_map[edge_id(v, w)];
                if (type >= 0 && ((mask >> (type / 2)) & 1) != type % 2) continue;
                int ns = mask * V + w;
                if (dist[ns] < 0) {
                    dist[ns] = dist[state] + 1;
                    q[tail++] = ns;
                }
            }
        }
        return -1;
    }

    SwitchOut choose_level0(const vector<const Candidate*>& selected,
                            const vector<int>& final_edges,
                            const vector<SwitchOut>& switches) const {
        vector<int> blocked = final_edges;
        for (const Candidate* c : selected) {
            blocked.insert(blocked.end(), c->edges.begin(), c->edges.end());
            blocked.insert(blocked.end(), c->seals.begin(), c->seals.end());
        }
        sort_unique(blocked);
        vector<char> comp = component(blocked);
        vector<char> occupied(V, false);
        for (const auto& s : switches) occupied[s.i * N + s.j] = true;
        vector<int> cells;
        for (int v : vertices) if (comp[v] && !occupied[v] && v != goal) cells.push_back(v);
        if (cells.empty()) cells.push_back(start);
        vector<int> portals{start};
        for (const Candidate* c : selected) {
            portals.push_back(c->path.front());
            portals.push_back(c->path.back());
        }
        vector<vector<int>> portal_dist;
        for (int p : portals) portal_dist.push_back(distances(p, blocked));
        sort(cells.begin(), cells.end(), [&](int a, int b) {
            auto h = [&](int v) {
                int sum = 0, mx = 0;
                for (const auto& d : portal_dist) if (d[v] >= 0) {
                    sum += d[v];
                    mx = max(mx, d[v]);
                }
                return sum + mx * 4;
            };
            return h(a) > h(b);
        });
        int best = cells[0];
        if (debug) cerr << "level0 candidates " << cells.size() << " chosen " << best << '\n';
        return {best / N, best % N, 0};
    }

    int add_extra_common_doors(
        int level,
        const vector<const Candidate*>& selected,
        const vector<int>& final_edges,
        vector<DoorOut>& doors,
        vector<SwitchOut>& switches
    ) const {
        if (selected.empty() || level + 1 >= min(K, 9)) return level;
        struct ExtraOption {
            int controlled_edge;
            vector<int> required_seals;
            int rank;
        };

        vector<char> occupied_switch(V, false);
        for (const auto& s : switches) occupied_switch[s.i * N + s.j] = true;

        vector<char> occupied_edge(V * V, false);
        vector<int> occupied_type(V * V, -1);
        for (const auto& d : doors) {
            int a = d.i * N + d.j;
            int b = d.d == 0 ? (d.i + 1) * N + d.j : d.i * N + d.j + 1;
            occupied_edge[edge_id(a, b)] = true;
            occupied_type[edge_id(a, b)] = d.type;
        }

        // 機構前後の追加扉は、同じ端点へ入る他の本線辺をT19で塞ぐ
        // パッケージとして扱う。これにより追加扉を迂回できない。
        vector<vector<ExtraOption>> options(selected.size());
        for (int c = 0; c < (int)selected.size(); ++c) {
            const auto& path = selected[c]->path;
            int ec = path.size() - 1;
            for (int x = 0; x < ec; ++x) {
                int e = edge_id(path[x], path[x + 1]);
                if (!occupied_edge[e]) {
                    options[c].push_back({e, {}, abs(2 * x + 1 - ec)});
                }
            }
            for (int side : {0, ec}) {
                int v = path[side];
                int path_neighbor = side == 0 ? path[1] : path[ec - 1];
                for (int w : adj[v]) {
                    int e = edge_id(v, w);
                    if (!occupied_edge[e] &&
                        find(path.begin(), path.end(), w) == path.end()) {
                        vector<int> seals;
                        bool valid = true;
                        for (int z : adj[v]) {
                            int other = edge_id(v, z);
                            if (z == path_neighbor || other == e) continue;
                            if (occupied_type[other] >= 0 &&
                                occupied_type[other] != 19) {
                                valid = false;
                                break;
                            }
                            if (occupied_type[other] != 19) seals.push_back(other);
                        }
                        if (valid) {
                            sort_unique(seals);
                            options[c].push_back({e, seals, ec + 4 + (int)seals.size() * 3});
                        }
                    }
                }
            }
            sort(options[c].begin(), options[c].end(), [](const auto& a, const auto& b) {
                return tuple(a.rank, a.required_seals.size(), a.controlled_edge) <
                       tuple(b.rank, b.required_seals.size(), b.controlled_edge);
            });
            options[c].erase(
                unique(options[c].begin(), options[c].end(),
                       [](const auto& a, const auto& b) {
                           return a.controlled_edge == b.controlled_edge;
                       }),
                options[c].end());
        }

        // 新スイッチは、機構を通らず到達できる本線側へ置く。
        vector<int> blocked = final_edges;
        for (const Candidate* c : selected) {
            blocked.insert(blocked.end(), c->edges.begin(), c->edges.end());
            blocked.insert(blocked.end(), c->seals.begin(), c->seals.end());
        }
        sort_unique(blocked);
        vector<char> core = component(blocked);
        vector<int> switch_distance(V, 1 << 20);
        queue<int> switch_queue;
        for (const auto& s : switches) {
            int v = s.i * N + s.j;
            if (!core[v] || switch_distance[v] == 0) continue;
            switch_distance[v] = 0;
            switch_queue.push(v);
        }
        while (!switch_queue.empty()) {
            int v = switch_queue.front();
            switch_queue.pop();
            for (int w : adj[v]) {
                if (!core[w] || switch_distance[w] <= switch_distance[v] + 1) continue;
                switch_distance[w] = switch_distance[v] + 1;
                switch_queue.push(w);
            }
        }
        vector<int> endpoints;
        for (const Candidate* c : selected) {
            endpoints.push_back(c->path.front());
            endpoints.push_back(c->path.back());
        }

        // 全機構端点より玉座側にある未使用橋。追加bitは奇数扉にする。
        vector<int> throne_edges;
        vector<int> gadget_blocked;
        for (const Candidate* c : selected) {
            gadget_blocked.insert(gadget_blocked.end(), c->edges.begin(), c->edges.end());
            gadget_blocked.insert(gadget_blocked.end(), c->seals.begin(), c->seals.end());
        }
        sort_unique(gadget_blocked);
        for (int bridge : sg_bridges(gadget_blocked)) {
            vector<int> cut = gadget_blocked;
            cut.insert(lower_bound(cut.begin(), cut.end(), bridge), bridge);
            vector<char> side = component(cut);
            bool ok = !side[goal];
            for (int v : endpoints) ok &= side[v];
            if (ok && !occupied_edge[bridge]) throne_edges.push_back(bridge);
        }
        reverse(throne_edges.begin(), throne_edges.end());

        vector<int> start_dist = distances(start, blocked);

        int highest_bit = level;
        int edge_slot = 0;
        for (int bit = level + 1; bit < min(K, 9); ++bit) {
            vector<int> active;
            for (int c = 0; c < (int)selected.size(); ++c) {
                if (edge_slot < (int)options[c].size()) active.push_back(c);
            }
            if (active.empty()) break;

            vector<DoorOut> added_doors;
            unordered_set<int> layer_edges;
            unordered_set<int> controlled_edges;
            unordered_set<int> seal_edges;
            for (int c : active) {
                const ExtraOption& option = options[c][edge_slot];
                int e = option.controlled_edge;
                if (occupied_edge[e] || !layer_edges.insert(e).second) continue;
                bool valid = true;
                for (int seal : option.required_seals) {
                    if (controlled_edges.count(seal) ||
                        (occupied_type[seal] >= 0 && occupied_type[seal] != 19)) {
                        valid = false;
                        break;
                    }
                }
                if (!valid) {
                    layer_edges.erase(e);
                    continue;
                }
                int parity = selected[c]->level & 1;
                controlled_edges.insert(e);
                added_doors.push_back(edge_to_output(e, 2 * bit + parity));
                for (int seal : option.required_seals) {
                    if (occupied_type[seal] == 19 || !seal_edges.insert(seal).second) continue;
                    layer_edges.insert(seal);
                    added_doors.push_back(edge_to_output(seal, 19));
                }
            }
            while (!throne_edges.empty()) {
                int e = throne_edges.back();
                throne_edges.pop_back();
                if (occupied_edge[e] || layer_edges.count(e)) continue;
                layer_edges.insert(e);
                controlled_edges.insert(e);
                added_doors.push_back(edge_to_output(e, 2 * bit + 1));
                break;
            }
            if (added_doors.empty()) break;
            if ((int)doors.size() + (int)added_doors.size() > M) break;

            vector<int> cells;
            for (int v : vertices) {
                if (core[v] && !occupied_switch[v] && v != goal) cells.push_back(v);
            }
            sort(cells.begin(), cells.end(),
                 [&](int a, int b) {
                     return pair(switch_distance[a], start_dist[a]) >
                            pair(switch_distance[b], start_dist[b]);
                 });
            if (cells.size() > 24) cells.resize(24);

            vector<DoorOut> trial_doors = doors;
            trial_doors.insert(trial_doors.end(), added_doors.begin(), added_doors.end());
            int chosen = -1;
            for (int v : cells) {
                vector<SwitchOut> trial_switches = switches;
                trial_switches.push_back({v / N, v % N, bit});
                int t = shortest_actions(bit + 1, trial_doors, trial_switches);
                if (t >= 0) {
                    chosen = v;
                    break;
                }
            }
            if (chosen < 0) {
                // この共通bitでは成立しない。辺は消費せず次の種類を試す。
                continue;
            }

            doors.insert(doors.end(), added_doors.begin(), added_doors.end());
            switches.push_back({chosen / N, chosen % N, bit});
            occupied_switch[chosen] = true;
            // 次の追加スイッチは今回の配置からも離す。
            queue<int> update_queue;
            if (switch_distance[chosen] > 0) {
                switch_distance[chosen] = 0;
                update_queue.push(chosen);
            }
            while (!update_queue.empty()) {
                int v = update_queue.front();
                update_queue.pop();
                for (int w : adj[v]) {
                    if (!core[w] || switch_distance[w] <= switch_distance[v] + 1) continue;
                    switch_distance[w] = switch_distance[v] + 1;
                    update_queue.push(w);
                }
            }
            for (int e : layer_edges) occupied_edge[e] = true;
            for (int e : controlled_edges) occupied_type[e] = 2 * bit;
            for (int e : seal_edges) occupied_type[e] = 19;
            ++edge_slot;
            highest_bit = bit;
            if (debug) {
                cerr << "extra common switch " << bit
                     << " doors " << added_doors.size()
                     << " cell " << chosen << '\n';
            }
        }
        return highest_bit;
    }

    void remove_duplicate_doors(vector<DoorOut>& doors) const {
        vector<DoorOut> unique_doors;
        vector<char> used(V * V, false);
        unique_doors.reserve(doors.size());
        for (const auto& d : doors) {
            int a = d.i * N + d.j;
            int b = d.d == 0 ? (d.i + 1) * N + d.j : d.i * N + d.j + 1;
            int e = edge_id(a, b);
            if (used[e]) {
                if (debug) cerr << "removed duplicate door edge " << e << '\n';
                continue;
            }
            used[e] = true;
            unique_doors.push_back(d);
        }
        doors.swap(unique_doors);
    }

    int improve_exactly(
        int level,
        int highest_bit,
        const vector<const Candidate*>& selected,
        vector<DoorOut>& doors,
        vector<SwitchOut>& switches
    ) const {
        int used_bits = highest_bit + 1;
        int best_t = shortest_actions(used_bits, doors, switches);
        if (best_t < 0 || time_up()) return best_t;

        mt19937 rng(0x67A11CEu + (unsigned)best_t);

        // 追加スイッチだけを移動する。基本リセット機構のスイッチは固定。
        bool improved = true;
        while (improved && !time_up()) {
            improved = false;
            for (int si = 0; si < (int)switches.size() && !time_up(); ++si) {
                if (switches[si].type <= level) continue;

                vector<char> occupied(V, false);
                for (int j = 0; j < (int)switches.size(); ++j) {
                    if (j != si) occupied[switches[j].i * N + switches[j].j] = true;
                }
                vector<int> candidates_cells;
                for (int v : vertices) {
                    if (!occupied[v] && v != goal) candidates_cells.push_back(v);
                }
                shuffle(candidates_cells.begin(), candidates_cells.end(), rng);
                if (candidates_cells.size() > 28) candidates_cells.resize(28);

                SwitchOut original = switches[si];
                SwitchOut best_switch = original;
                int local_best = best_t;
                for (int v : candidates_cells) {
                    if (time_up()) break;
                    switches[si] = {v / N, v % N, original.type};
                    int t = shortest_actions(used_bits, doors, switches);
                    if (t > local_best) {
                        local_best = t;
                        best_switch = switches[si];
                    }
                }
                switches[si] = best_switch;
                if (local_best > best_t) {
                    best_t = local_best;
                    improved = true;
                    if (debug) {
                        cerr << "exact move switch " << original.type
                             << " T " << best_t << '\n';
                    }
                }
            }
        }

        // 余った扉を、効果が確認できたものだけ貪欲追加する。
        vector<char> occupied_edge(V * V, false);
        vector<int> occupied_type(V * V, -1);
        for (const auto& d : doors) {
            int a = d.i * N + d.j;
            int b = d.d == 0 ? (d.i + 1) * N + d.j : d.i * N + d.j + 1;
            occupied_edge[edge_id(a, b)] = true;
            occupied_type[edge_id(a, b)] = d.type;
        }

        // 追加スイッチを小部屋化する。
        // 入口1辺を別bitの扉にし、残りの入口をT19で永久閉鎖する。
        bool guarded = true;
        while (guarded && !time_up() && (int)doors.size() < M) {
            guarded = false;
            vector<DoorOut> best_package;
            int best_guard_t = best_t;
            int best_switch_type = -1;
            for (const auto& sw : switches) {
                if (sw.type <= level || time_up()) continue;
                int v = sw.i * N + sw.j;
                for (int entry_neighbor : adj[v]) {
                    int entry = edge_id(v, entry_neighbor);
                    if (occupied_edge[entry]) continue;

                    vector<int> seals;
                    bool valid = true;
                    for (int w : adj[v]) {
                        int e = edge_id(v, w);
                        if (e == entry) continue;
                        if (occupied_type[e] >= 0 && occupied_type[e] != 19) {
                            valid = false;
                            break;
                        }
                        if (occupied_type[e] < 0) seals.push_back(e);
                    }
                    if (!valid || 1 + (int)seals.size() + (int)doors.size() > M) continue;

                    for (int bit = 0; bit < used_bits && !time_up(); ++bit) {
                        if (bit == sw.type) continue;
                        for (int parity = 0; parity < 2 && !time_up(); ++parity) {
                            vector<DoorOut> package;
                            package.push_back(edge_to_output(entry, 2 * bit + parity));
                            for (int e : seals) package.push_back(edge_to_output(e, 19));
                            doors.insert(doors.end(), package.begin(), package.end());
                            int t = shortest_actions(used_bits, doors, switches);
                            doors.resize(doors.size() - package.size());
                            if (t > best_guard_t) {
                                best_guard_t = t;
                                best_package = move(package);
                                best_switch_type = sw.type;
                            }
                        }
                    }
                }
            }
            if (!best_package.empty()) {
                for (const auto& d : best_package) {
                    int a = d.i * N + d.j;
                    int b = d.d == 0 ? (d.i + 1) * N + d.j : d.i * N + d.j + 1;
                    int e = edge_id(a, b);
                    occupied_edge[e] = true;
                    occupied_type[e] = d.type;
                    doors.push_back(d);
                }
                best_t = best_guard_t;
                guarded = true;
                if (debug) {
                    cerr << "guard switch " << best_switch_type
                         << " package " << best_package.size()
                         << " T " << best_t << '\n';
                }
            }
        }

        vector<int> candidate_edges;
        unordered_set<int> bridge_set;
        unordered_set<int> gadget_edge_set;
        // S-G橋、機構辺、その他の順。
        for (int e : sg_bridges({})) {
            bridge_set.insert(e);
            if (!occupied_edge[e]) candidate_edges.push_back(e);
        }
        for (const Candidate* c : selected) {
            for (int e : c->edges) {
                gadget_edge_set.insert(e);
                if (!occupied_edge[e]) candidate_edges.push_back(e);
            }
        }
        for (int e : all_edges) if (!occupied_edge[e]) candidate_edges.push_back(e);
        sort_unique(candidate_edges);
        stable_sort(candidate_edges.begin(), candidate_edges.end(), [&](int a, int b) {
            auto priority = [&](int e) {
                if (bridge_set.count(e)) return 0;
                if (gadget_edge_set.count(e)) return 1;
                return 2;
            };
            return priority(a) < priority(b);
        });

        while ((int)doors.size() < M && !time_up()) {
            int chosen_edge = -1, chosen_type = -1, chosen_t = best_t;
            for (int e : candidate_edges) {
                if (occupied_edge[e]) continue;
                for (int bit = 0; bit < used_bits && !time_up(); ++bit) {
                    for (int parity = 0; parity < 2 && !time_up(); ++parity) {
                        doors.push_back(edge_to_output(e, 2 * bit + parity));
                        int t = shortest_actions(used_bits, doors, switches);
                        doors.pop_back();
                        if (t > chosen_t) {
                            chosen_t = t;
                            chosen_edge = e;
                            chosen_type = 2 * bit + parity;
                        }
                    }
                }
                if (time_up()) break;
            }
            if (chosen_edge < 0) break;
            doors.push_back(edge_to_output(chosen_edge, chosen_type));
            occupied_edge[chosen_edge] = true;
            best_t = chosen_t;
            if (debug) {
                cerr << "exact add door type " << chosen_type
                     << " T " << best_t << '\n';
            }
        }
        return best_t;
    }

public:
    Solver(int n, int m, int k, vector<string> b, bool dbg)
        : N(n), M(m), K(k), V(n * n), board(move(b)), adj(V), debug(dbg), goal(V - 1) {
        for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j) if (board[i][j] == '.') {
            int v = i * N + j;
            vertices.push_back(v);
            for (auto [di, dj] : array<pair<int, int>, 4>{{{-1,0},{1,0},{0,-1},{0,1}}}) {
                int ni = i + di, nj = j + dj;
                if (0 <= ni && ni < N && 0 <= nj && nj < N && board[ni][nj] == '.') {
                    adj[v].push_back(ni * N + nj);
                }
            }
        }
        for (int v : vertices) for (int w : adj[v]) if (v < w) all_edges.push_back(edge_id(v, w));
        sort(all_edges.begin(), all_edges.end());
        corridors = list_corridors();
        cycles = list_cycles();
    }

    pair<vector<DoorOut>, vector<SwitchOut>> solve() {
        auto [level, selected, final_edges] = select_layout();
        auto [doors, switches] = build_gadgets(selected);
        for (int bit = 0; bit < (int)final_edges.size(); ++bit) {
            doors.push_back(edge_to_output(final_edges[bit], 2 * bit + 1));
        }
        switches.push_back(choose_level0(selected, final_edges, switches));
        int highest_bit = add_extra_common_doors(
            level, selected, final_edges, doors, switches
        );
        remove_duplicate_doors(doors);
        int improved_t = improve_exactly(
            level, highest_bit, selected, doors, switches
        );
        if (debug) {
            cerr << "selected max level " << level << '\n';
            for (const Candidate* c : selected) {
                cerr << "gadget " << c->level << " length " << c->path.size() - 1
                     << " bypass " << c->bypass_length << " seals " << c->seals.size() << '\n';
            }
            cerr << "doors " << doors.size() << " switches " << switches.size() << '\n';
            cerr << "verified T " << improved_t << '\n';
        }
        return {doors, switches};
    }
};

int main(int argc, char** argv) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    bool debug = false;
    for (int i = 1; i < argc; ++i) if (string(argv[i]) == "--debug") debug = true;
    int N, M, K;
    if (!(cin >> N >> M >> K)) return 0;
    vector<string> board(N);
    for (auto& row : board) cin >> row;
    Solver solver(N, M, K, board, debug);
    auto [doors, switches] = solver.solve();
    cout << doors.size() << '\n';
    for (const auto& d : doors) cout << d.d << ' ' << d.i << ' ' << d.j << ' ' << d.type << '\n';
    cout << switches.size() << '\n';
    for (const auto& s : switches) cout << s.i << ' ' << s.j << ' ' << s.type << '\n';
}

提出情報

ジャッジ結果