提出 #76878873
ソースコード 拡げる
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
static constexpr double TIME_LIMIT = 1.85;
struct Timer {
chrono::steady_clock::time_point st = chrono::steady_clock::now();
double elapsed() const {
return chrono::duration<double>(chrono::steady_clock::now() - st).count();
}
bool time_up(double limit = TIME_LIMIT) const {
return elapsed() >= limit;
}
};
mt19937_64 rng(0);
struct Door {
int d, i, j, g;
};
struct Switch {
int i, j, k;
};
struct Edge {
int u, v;
int d, i, j;
};
struct Solver {
Timer timer;
int N = 0;
int M = 0;
int K = 0;
vector<string> c;
vector<Edge> edges;
vector<vector<pair<int, int>>> graph;
vector<Door> best_doors;
vector<Switch> best_switches;
vector<Door> best_corridor_doors;
vector<Switch> best_corridor_switches;
int best_T = 0;
int best_corridor_T = 0;
ll score = 0;
string best_strategy = "base";
void input() {
cin >> N >> M >> K;
c.resize(N);
for (auto& row : c) cin >> row;
}
int id(int i, int j) const {
return i * N + j;
}
pair<int, int> pos(int v) const {
return {v / N, v % N};
}
bool is_open_cell(int v) const {
auto [i, j] = pos(v);
return c[i][j] == '.';
}
void build_graph() {
edges.clear();
graph.assign(N * N, {});
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (c[i][j] == '#') continue;
if (i + 1 < N && c[i + 1][j] == '.') add_edge(id(i, j), id(i + 1, j), 0, i, j);
if (j + 1 < N && c[i][j + 1] == '.') add_edge(id(i, j), id(i, j + 1), 1, i, j);
}
}
}
void add_edge(int u, int v, int d, int i, int j) {
int eid = (int)edges.size();
edges.push_back({u, v, d, i, j});
graph[u].push_back({v, eid});
graph[v].push_back({u, eid});
}
int shortest_without_doors() const {
static constexpr int DI[4] = {-1, 1, 0, 0};
static constexpr int DJ[4] = {0, 0, -1, 1};
vector<vector<int>> dist(N, vector<int>(N, -1));
queue<pair<int, int>> q;
dist[0][0] = 0;
q.push({0, 0});
while (!q.empty()) {
auto [i, j] = q.front();
q.pop();
if (i == N - 1 && j == N - 1) return dist[i][j];
for (int dir = 0; dir < 4; dir++) {
int ni = i + DI[dir];
int nj = j + DJ[dir];
if (ni < 0 || ni >= N || nj < 0 || nj >= N) continue;
if (c[ni][nj] == '#') continue;
if (dist[ni][nj] != -1) continue;
dist[ni][nj] = dist[i][j] + 1;
q.push({ni, nj});
}
}
return 0;
}
bool door_open(int g, int mask) const {
if (g < 0) return true;
return ((mask >> (g >> 1)) & 1) == (g & 1);
}
int calc_T(const vector<Door>& doors, const vector<Switch>& switches) const {
vector<vector<int>> door_h(N - 1, vector<int>(N, -1));
vector<vector<int>> door_v(N, vector<int>(N - 1, -1));
for (const auto& e : doors) {
if (e.d == 0) {
door_h[e.i][e.j] = e.g;
} else {
door_v[e.i][e.j] = e.g;
}
}
vector<int> sw(N * N, -1);
for (const auto& s : switches) sw[id(s.i, s.j)] = s.k;
const int states = 1 << K;
const int cells = N * N;
vector<int> dist(states * cells, -1);
queue<int> q;
dist[0] = 0;
q.push(0);
static constexpr int DI[4] = {-1, 1, 0, 0};
static constexpr int DJ[4] = {0, 0, -1, 1};
while (!q.empty()) {
int code = q.front();
q.pop();
int mask = code / cells;
int v = code % cells;
int i = v / N;
int j = v % N;
int d0 = dist[code];
if (i == N - 1 && j == N - 1) return d0;
for (int dir = 0; dir < 4; dir++) {
int ni = i + DI[dir];
int nj = j + DJ[dir];
if (ni < 0 || ni >= N || nj < 0 || nj >= N) continue;
if (c[ni][nj] == '#') continue;
int g = -1;
if (dir == 0) g = door_h[ni][nj];
if (dir == 1) g = door_h[i][j];
if (dir == 2) g = door_v[i][nj];
if (dir == 3) g = door_v[i][j];
if (!door_open(g, mask)) continue;
int nv = id(ni, nj);
int ncode = mask * cells + nv;
if (dist[ncode] == -1) {
dist[ncode] = d0 + 1;
q.push(ncode);
}
}
if (sw[v] != -1) {
int nmask = mask ^ (1 << sw[v]);
int ncode = nmask * cells + v;
if (dist[ncode] == -1) {
dist[ncode] = d0 + 1;
q.push(ncode);
}
}
}
return 0;
}
struct TraceInfo {
int T = 0;
vector<int> press_count;
vector<int> edge_pass;
vector<int> cell_visit;
};
TraceInfo calc_trace(const vector<Door>& doors, const vector<Switch>& switches) const {
TraceInfo info;
info.press_count.assign(K, 0);
info.edge_pass.assign(edges.size(), 0);
info.cell_visit.assign(N * N, 0);
vector<vector<int>> door_h(N - 1, vector<int>(N, -1));
vector<vector<int>> door_v(N, vector<int>(N - 1, -1));
vector<vector<int>> eid_h(N - 1, vector<int>(N, -1));
vector<vector<int>> eid_v(N, vector<int>(N - 1, -1));
for (int eid = 0; eid < (int)edges.size(); eid++) {
const auto& e = edges[eid];
if (e.d == 0) {
eid_h[e.i][e.j] = eid;
} else {
eid_v[e.i][e.j] = eid;
}
}
for (const auto& e : doors) {
if (e.d == 0) {
door_h[e.i][e.j] = e.g;
} else {
door_v[e.i][e.j] = e.g;
}
}
vector<int> sw(N * N, -1);
for (const auto& s : switches) sw[id(s.i, s.j)] = s.k;
const int states = 1 << K;
const int cells = N * N;
const int total = states * cells;
vector<int> dist(total, -1), parent(total, -1);
vector<short> action(total, 0);
queue<int> q;
dist[0] = 0;
parent[0] = 0;
q.push(0);
static constexpr int DI[4] = {-1, 1, 0, 0};
static constexpr int DJ[4] = {0, 0, -1, 1};
int goal_code = -1;
while (!q.empty()) {
int code = q.front();
q.pop();
int mask = code / cells;
int v = code % cells;
int i = v / N;
int j = v % N;
int d0 = dist[code];
if (i == N - 1 && j == N - 1) {
goal_code = code;
break;
}
for (int dir = 0; dir < 4; dir++) {
int ni = i + DI[dir];
int nj = j + DJ[dir];
if (ni < 0 || ni >= N || nj < 0 || nj >= N) continue;
if (c[ni][nj] == '#') continue;
int g = -1;
int eid = -1;
if (dir == 0) {
g = door_h[ni][nj];
eid = eid_h[ni][nj];
}
if (dir == 1) {
g = door_h[i][j];
eid = eid_h[i][j];
}
if (dir == 2) {
g = door_v[i][nj];
eid = eid_v[i][nj];
}
if (dir == 3) {
g = door_v[i][j];
eid = eid_v[i][j];
}
if (!door_open(g, mask)) continue;
int nv = id(ni, nj);
int ncode = mask * cells + nv;
if (dist[ncode] == -1) {
dist[ncode] = d0 + 1;
parent[ncode] = code;
action[ncode] = (short)(eid + 1);
q.push(ncode);
}
}
if (sw[v] != -1) {
int k = sw[v];
int nmask = mask ^ (1 << k);
int ncode = nmask * cells + v;
if (dist[ncode] == -1) {
dist[ncode] = d0 + 1;
parent[ncode] = code;
action[ncode] = (short)(-(k + 1));
q.push(ncode);
}
}
}
if (goal_code == -1) return info;
info.T = dist[goal_code];
for (int code = goal_code; code != 0; code = parent[code]) {
int v = code % cells;
info.cell_visit[v]++;
short act = action[code];
if (act < 0) {
int k = -act - 1;
if (0 <= k && k < K) info.press_count[k]++;
} else if (act > 0) {
int eid = act - 1;
if (0 <= eid && eid < (int)info.edge_pass.size()) info.edge_pass[eid]++;
}
}
info.cell_visit[0]++;
return info;
}
ll calc_score_from_T(int T) const {
if (T == 0) return 1;
return llround(1e6 * log2((double)T / (double)N));
}
void normalize_switches(vector<Switch>& switches) const {
vector<int> used(N * N, -1);
vector<Switch> res;
for (const auto& s : switches) {
int v = id(s.i, s.j);
if (used[v] != -1) continue;
used[v] = s.k;
res.push_back(s);
}
switches.swap(res);
}
void try_candidate(vector<Door> doors, vector<Switch> switches, const string& strategy = "candidate") {
if ((int)doors.size() > M) doors.resize(M);
normalize_switches(switches);
int T = calc_T(doors, switches);
if (strategy == "counter_relay_hanoi" && T < 420) return;
if ((strategy.find("corridor") != string::npos || strategy.find("hanoi") != string::npos) && T > best_corridor_T) {
best_corridor_T = T;
best_corridor_doors = doors;
best_corridor_switches = switches;
}
if (T > best_T) {
best_T = T;
best_doors = move(doors);
best_switches = move(switches);
score = calc_score_from_T(best_T);
best_strategy = strategy;
}
}
vector<pair<int, int>> shortest_path_edges_random(bool weighted) {
const int S = 0;
const int G = N * N - 1;
const int INF = 1e9;
vector<int> dist(N * N, INF), pre_v(N * N, -1), pre_e(N * N, -1);
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
dist[S] = 0;
pq.push({0, S});
while (!pq.empty()) {
auto [du, u] = pq.top();
pq.pop();
if (du != dist[u]) continue;
if (u == G) break;
for (auto [v, eid] : graph[u]) {
int w = weighted ? 1 + (int)(rng() % 1000) : 1;
int nd = du + w;
if (nd < dist[v]) {
dist[v] = nd;
pre_v[v] = u;
pre_e[v] = eid;
pq.push({nd, v});
}
}
}
vector<pair<int, int>> path;
if (dist[G] == INF) return path;
for (int v = G; v != S; v = pre_v[v]) {
path.push_back({pre_e[v], pre_v[v]});
}
reverse(path.begin(), path.end());
return path;
}
vector<pair<int, int>> shortest_path_edges_noisy(int noise, const vector<int>* edge_penalty = nullptr) {
const int S = 0;
const int G = N * N - 1;
const int INF = 1e9;
vector<int> dist(N * N, INF), pre_v(N * N, -1), pre_e(N * N, -1);
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
dist[S] = 0;
pq.push({0, S});
while (!pq.empty()) {
auto [du, u] = pq.top();
pq.pop();
if (du != dist[u]) continue;
if (u == G) break;
for (auto [v, eid] : graph[u]) {
int w = 1000 + (noise > 0 ? (int)(rng() % noise) : 0);
if (edge_penalty) w += (*edge_penalty)[eid];
int nd = du + w;
if (nd < dist[v]) {
dist[v] = nd;
pre_v[v] = u;
pre_e[v] = eid;
pq.push({nd, v});
}
}
}
vector<pair<int, int>> path;
if (dist[G] == INF) return path;
for (int v = G; v != S; v = pre_v[v]) {
path.push_back({pre_e[v], pre_v[v]});
}
reverse(path.begin(), path.end());
return path;
}
vector<pair<int, int>> shortest_path_between(int S, int G, const vector<int>* edge_penalty = nullptr) {
const int INF = 1e9;
vector<int> dist(N * N, INF), pre_v(N * N, -1), pre_e(N * N, -1);
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
dist[S] = 0;
pq.push({0, S});
while (!pq.empty()) {
auto [du, u] = pq.top();
pq.pop();
if (du != dist[u]) continue;
if (u == G) break;
for (auto [v, eid] : graph[u]) {
int w = 1000;
if (edge_penalty) w += (*edge_penalty)[eid];
int nd = du + w;
if (nd < dist[v]) {
dist[v] = nd;
pre_v[v] = u;
pre_e[v] = eid;
pq.push({nd, v});
}
}
}
vector<pair<int, int>> path;
if (dist[G] == INF) return path;
for (int v = G; v != S; v = pre_v[v]) {
path.push_back({pre_e[v], pre_v[v]});
}
reverse(path.begin(), path.end());
return path;
}
vector<pair<int, int>> shortest_path_between_banned(int S, int G, const vector<char>& banned_edge) const {
vector<int> dist(N * N, -1), pre_v(N * N, -1), pre_e(N * N, -1);
queue<int> q;
dist[S] = 0;
q.push(S);
while (!q.empty()) {
int u = q.front();
q.pop();
if (u == G) break;
for (auto [v, eid] : graph[u]) {
if ((eid >= 0 && eid < (int)banned_edge.size() && banned_edge[eid]) || dist[v] != -1) continue;
dist[v] = dist[u] + 1;
pre_v[v] = u;
pre_e[v] = eid;
q.push(v);
}
}
vector<pair<int, int>> path;
if (dist[G] == -1) return path;
for (int v = G; v != S; v = pre_v[v]) {
path.push_back({pre_e[v], pre_v[v]});
}
reverse(path.begin(), path.end());
return path;
}
vector<pair<int, int>> corridor_path(int side_penalty, int extra_len_penalty) {
const int S = 0;
const int G = N * N - 1;
const int INF = 1e9;
vector<int> dist(N * N, INF), pre_v(N * N, -1), pre_e(N * N, -1);
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
dist[S] = 0;
pq.push({0, S});
while (!pq.empty()) {
auto [du, u] = pq.top();
pq.pop();
if (du != dist[u]) continue;
if (u == G) break;
for (auto [v, eid] : graph[u]) {
int side = max(0, (int)graph[v].size() - 2);
int w = 1000 + side_penalty * side + extra_len_penalty * ((v / N + v % N) & 1);
int nd = du + w;
if (nd < dist[v]) {
dist[v] = nd;
pre_v[v] = u;
pre_e[v] = eid;
pq.push({nd, v});
}
}
}
vector<pair<int, int>> path;
if (dist[G] == INF) return path;
for (int v = G; v != S; v = pre_v[v]) {
path.push_back({pre_e[v], pre_v[v]});
}
reverse(path.begin(), path.end());
return path;
}
vector<int> bfs_dist(int start, const vector<int>& banned_eids = {}) const {
vector<char> banned(edges.size(), false);
for (int eid : banned_eids) {
if (0 <= eid && eid < (int)edges.size()) banned[eid] = true;
}
vector<int> dist(N * N, -1);
queue<int> q;
dist[start] = 0;
q.push(start);
while (!q.empty()) {
int u = q.front();
q.pop();
for (auto [v, eid] : graph[u]) {
if (banned[eid] || dist[v] != -1) continue;
dist[v] = dist[u] + 1;
q.push(v);
}
}
return dist;
}
int abstract_cycle_time(const vector<int>& edge_g, const vector<int>& sw, int exit_mask, int exit_target) const {
int L = (int)edge_g.size();
if (L == 0) return 0;
const int states = 1 << K;
vector<int> dist(states * L, -1);
queue<int> q;
dist[0] = 0;
q.push(0);
while (!q.empty()) {
int code = q.front();
q.pop();
int mask = code / L;
int p = code % L;
int d0 = dist[code];
if (d0 > 0 && p == 0 && ((mask & exit_mask) == exit_target)) return d0;
for (int dir : {-1, 1}) {
int np = (p + dir + L) % L;
int ei = (dir == 1 ? p : np);
int g = edge_g[ei];
if (!door_open(g, mask)) continue;
int ncode = mask * L + np;
if (dist[ncode] == -1) {
dist[ncode] = d0 + 1;
q.push(ncode);
}
}
if (sw[p] != -1) {
int nmask = mask ^ (1 << sw[p]);
int ncode = nmask * L + p;
if (dist[ncode] == -1) {
dist[ncode] = d0 + 1;
q.push(ncode);
}
}
}
return 0;
}
bool build_cycle_through_hub(int hub, vector<pair<int, int>>& cycle_edges, vector<int>& cycle_vertices, vector<pair<int, int>>& exit_path) {
vector<int> order;
order.reserve(N * N);
for (int v = 0; v < N * N; v++) {
if (is_open_cell(v) && v != hub && v != N * N - 1) order.push_back(v);
}
shuffle(order.begin(), order.end(), rng);
int best_len = -1;
vector<pair<int, int>> best_p1, best_p2;
int tries = 0;
for (int y : order) {
if (++tries > 45) break;
auto p1 = shortest_path_between(hub, y);
int l1 = (int)p1.size();
if (l1 < 5 || l1 > 24) continue;
vector<char> banned(edges.size(), false);
for (auto [eid, from] : p1) {
(void)from;
banned[eid] = true;
}
auto p2 = shortest_path_between_banned(hub, y, banned);
int l2 = (int)p2.size();
int cyc_len = l1 + l2;
if (l2 < 5 || cyc_len < 14 || cyc_len > 42) continue;
if (cyc_len > best_len) {
best_len = cyc_len;
best_p1 = move(p1);
best_p2 = move(p2);
}
}
if (best_len == -1) return false;
vector<char> cycle_used(edges.size(), false);
cycle_edges.clear();
cycle_vertices.clear();
cycle_vertices.push_back(hub);
int cur = hub;
for (auto [eid, from] : best_p1) {
(void)from;
cycle_edges.push_back({eid, cur});
cycle_used[eid] = true;
cur = edges[eid].u ^ edges[eid].v ^ cur;
cycle_vertices.push_back(cur);
}
for (int idx = (int)best_p2.size() - 1; idx >= 0; idx--) {
int eid = best_p2[idx].first;
cycle_edges.push_back({eid, cur});
cycle_used[eid] = true;
cur = edges[eid].u ^ edges[eid].v ^ cur;
if (cur != hub) cycle_vertices.push_back(cur);
}
if (cur != hub || (int)cycle_edges.size() != best_len) return false;
exit_path = shortest_path_between_banned(hub, N * N - 1, cycle_used);
if (exit_path.empty()) exit_path = shortest_path_between(hub, N * N - 1);
return !exit_path.empty();
}
void add_abstract_cycle_machine_candidates(double limit) {
vector<int> dist0 = bfs_dist(0);
vector<int> hubs;
for (int v = 0; v < N * N; v++) {
if (!is_open_cell(v) || v == N * N - 1) continue;
if (dist0[v] < 0 || dist0[v] > 24) continue;
if ((int)graph[v].size() < 3) continue;
hubs.push_back(v);
}
sort(hubs.begin(), hubs.end(), [&](int a, int b) {
return graph[a].size() > graph[b].size();
});
if ((int)hubs.size() > 18) hubs.resize(18);
shuffle(hubs.begin(), hubs.end(), rng);
for (int hi = 0; hi < (int)hubs.size() && !timer.time_up(limit); hi++) {
int hub = hubs[hi];
vector<pair<int, int>> cycle_edges, exit_path;
vector<int> cycle_vertices;
if (!build_cycle_through_hub(hub, cycle_edges, cycle_vertices, exit_path)) continue;
int L = (int)cycle_edges.size();
if (L < 10 || (int)cycle_vertices.size() != L) continue;
int exit_bits = min({K, (int)exit_path.size(), max(1, M - L)});
if (exit_bits <= 0) continue;
int exit_mask = (1 << exit_bits) - 1;
int best_abs_T = 0;
vector<int> best_edge_g, best_sw;
int best_target = 0;
int attempts = 0;
while (attempts < 900 && !timer.time_up(limit)) {
int door_budget = M - exit_bits;
vector<int> edge_g(L, -1), sw(L, -1);
vector<int> idx(L);
iota(idx.begin(), idx.end(), 0);
shuffle(idx.begin(), idx.end(), rng);
int dcnt = min(L, max(1, door_budget));
int low_bits = min(K, 4 + (attempts % 4));
for (int t = 0; t < dcnt; t++) {
int epos = idx[t];
int bit;
if ((attempts + t) & 1) bit = __builtin_ctz((unsigned)(t + 1)) % low_bits;
else bit = (t + (t >> 1) + attempts) % low_bits;
int parity = (attempts >> (bit % 6)) & 1;
if ((rng() & 3) == 0) parity ^= 1;
edge_g[epos] = 2 * bit + parity;
}
for (int p = 0; p < L; p++) {
if ((rng() % 100) < 78) {
int bit = (p + (p >> 1) + attempts + (int)(rng() % low_bits)) % low_bits;
sw[p] = bit;
}
}
int target = 1 + (attempts % max(1, (1 << exit_bits) - 1));
int at = abstract_cycle_time(edge_g, sw, exit_mask, target);
if (at > best_abs_T) {
best_abs_T = at;
best_edge_g = move(edge_g);
best_sw = move(sw);
best_target = target;
}
attempts++;
}
if (best_abs_T < 120) continue;
vector<Door> doors;
vector<Switch> switches;
vector<char> used_edge(edges.size(), false);
for (int i = 0; i < L && (int)doors.size() < M - exit_bits; i++) {
if (best_edge_g[i] == -1) continue;
add_unique_door(doors, used_edge, cycle_edges[i].first, best_edge_g[i]);
}
for (int b = 0; b < exit_bits && (int)doors.size() < M; b++) {
add_unique_door(doors, used_edge, exit_path[b].first, 2 * b + ((best_target >> b) & 1));
}
vector<char> used_cell(N * N, false);
for (int i = 0; i < L; i++) {
if (best_sw[i] == -1) continue;
int v = cycle_vertices[i];
if (used_cell[v] || v == N * N - 1) continue;
used_cell[v] = true;
auto [r, c0] = pos(v);
switches.push_back({r, c0, best_sw[i]});
}
try_candidate(move(doors), move(switches), "abstract_cycle_machine");
}
}
void add_alternating_path_candidate(const vector<pair<int, int>>& path, int mode, int stride, int offset) {
vector<int> idx;
int L = (int)path.size();
if (L == 0) return;
if (mode == 0) {
for (int i = 0; i < L && (int)idx.size() < M; i++) idx.push_back(i);
} else if (mode == 1) {
for (int i = max(0, L - M); i < L; i++) idx.push_back(i);
} else if (mode == 2) {
int take = min(M, L);
for (int t = 0; t < take; t++) idx.push_back((long long)t * L / take);
} else {
for (int i = offset; i < L && (int)idx.size() < M; i += stride) idx.push_back(i);
}
vector<Door> doors;
vector<Switch> switches;
int cnt = 0;
for (int pi : idx) {
auto [eid, from] = path[pi];
const Edge& e = edges[eid];
doors.push_back({e.d, e.i, e.j, (cnt + 1) & 1});
auto [si, sj] = pos(from);
switches.push_back({si, sj, 0});
cnt++;
}
try_candidate(move(doors), move(switches), "alternating_path");
}
vector<pair<int, int>> bridge_path_edges() {
int V = N * N;
vector<int> tin(V, -1), low(V, -1), parent(V, -1), parent_edge(V, -1), tout(V, -1);
vector<char> is_bridge(edges.size(), false);
int timer_dfs = 0;
auto dfs = [&](auto&& self, int u, int pe) -> void {
tin[u] = low[u] = timer_dfs++;
for (auto [v, eid] : graph[u]) {
if (eid == pe) continue;
if (tin[v] != -1) {
low[u] = min(low[u], tin[v]);
} else {
parent[v] = u;
parent_edge[v] = eid;
self(self, v, eid);
low[u] = min(low[u], low[v]);
if (low[v] > tin[u]) is_bridge[eid] = true;
}
}
tout[u] = timer_dfs;
};
dfs(dfs, 0, -1);
int goal = N * N - 1;
vector<pair<int, int>> res;
for (int v = goal; v != 0 && v != -1; v = parent[v]) {
int eid = parent_edge[v];
if (eid != -1 && is_bridge[eid]) res.push_back({eid, parent[v]});
}
reverse(res.begin(), res.end());
return res;
}
int farthest_in_component(int start, int banned_eid) const {
vector<int> banned;
if (banned_eid >= 0) banned.push_back(banned_eid);
return farthest_in_component(start, banned);
}
int farthest_in_component(int start, const vector<int>& banned_eids) const {
vector<char> banned(edges.size(), false);
for (int eid : banned_eids) {
if (0 <= eid && eid < (int)edges.size()) banned[eid] = true;
}
vector<int> dist(N * N, -1);
queue<int> q;
dist[start] = 0;
q.push(start);
int best = start;
while (!q.empty()) {
int u = q.front();
q.pop();
if (dist[u] > dist[best]) best = u;
for (auto [v, eid] : graph[u]) {
if (banned[eid] || dist[v] != -1) continue;
dist[v] = dist[u] + 1;
q.push(v);
}
}
return best;
}
void add_distinct_bridge_detour_candidate(const vector<pair<int, int>>& bridges) {
vector<Door> doors;
vector<Switch> switches;
int take = min(K, (int)bridges.size());
for (int t = 0; t < take; t++) {
auto [eid, from] = bridges[t];
const Edge& e = edges[eid];
doors.push_back({e.d, e.i, e.j, 2 * t + 1});
int sv = farthest_in_component(from, eid);
auto [si, sj] = pos(sv);
switches.push_back({si, sj, t});
}
try_candidate(move(doors), move(switches), "bridge_distinct_detour");
}
void add_alternating_bridge_detour_candidate(const vector<pair<int, int>>& bridges) {
vector<Door> doors;
vector<Switch> switches;
int take = min(M, (int)bridges.size());
for (int t = 0; t < take; t++) {
auto [eid, from] = bridges[t];
const Edge& e = edges[eid];
doors.push_back({e.d, e.i, e.j, (t + 1) & 1});
vector<int> banned = {eid};
if (t > 0) banned.push_back(bridges[t - 1].first);
int sv = farthest_in_component(from, banned);
auto [si, sj] = pos(sv);
switches.push_back({si, sj, 0});
}
try_candidate(move(doors), move(switches), "bridge_alternating_detour");
}
void add_gray_bridge_candidate(const vector<pair<int, int>>& bridges, int shift) {
if (bridges.empty()) return;
vector<Door> doors;
vector<Switch> switches;
int take = min(M, (int)bridges.size());
for (int t = 0; t < take; t++) {
int a = (t + shift) ^ ((t + shift) >> 1);
int b = (t + shift + 1) ^ ((t + shift + 1) >> 1);
int diff = a ^ b;
int bit = __builtin_ctz((unsigned)diff) % K;
int need = (b >> bit) & 1;
auto [eid, from] = bridges[t];
const Edge& e = edges[eid];
doors.push_back({e.d, e.i, e.j, 2 * bit + need});
vector<int> banned = {eid};
if (t > 0) banned.push_back(bridges[t - 1].first);
int sv = farthest_in_component(from, banned);
auto [si, sj] = pos(sv);
switches.push_back({si, sj, bit});
}
try_candidate(move(doors), move(switches), "bridge_gray");
}
int choose_low_heat_switch(int start, const vector<int>& banned_eids, const vector<int>& cell_heat, const vector<char>& used_cell) const {
auto dist = bfs_dist(start, banned_eids);
int best = start;
long long best_score = LLONG_MIN;
for (int v = 0; v < N * N; v++) {
if (dist[v] < 0 || used_cell[v]) continue;
if (!is_open_cell(v) || v == N * N - 1) continue;
long long s = 1000LL * dist[v] - 180LL * cell_heat[v];
if (cell_heat[v] == 0) s += 5000;
if (v == 0) s -= 3000;
if (s > best_score) {
best_score = s;
best = v;
}
}
return best;
}
void add_heatmap_distinct_candidate(const vector<int>& sorted_edges, const vector<int>& cell_heat, const vector<int>& dist0, int pool, int offset) {
if (sorted_edges.empty()) return;
vector<Door> doors;
vector<Switch> switches;
vector<char> used_cell(N * N, false);
int take = min(K, min(M, min(pool, (int)sorted_edges.size())));
for (int t = 0; t < take; t++) {
int rank = offset + (long long)t * max(1, pool - offset) / take;
if (rank >= (int)sorted_edges.size()) break;
int eid = sorted_edges[rank];
const Edge& e = edges[eid];
int from = dist0[e.u] <= dist0[e.v] ? e.u : e.v;
int sv = choose_low_heat_switch(from, {eid}, cell_heat, used_cell);
used_cell[sv] = true;
auto [si, sj] = pos(sv);
doors.push_back({e.d, e.i, e.j, 2 * t + 1});
switches.push_back({si, sj, t});
}
try_candidate(move(doors), move(switches), "heatmap_distinct");
}
void add_heatmap_alternating_candidate(const vector<int>& sorted_edges, const vector<int>& cell_heat, const vector<int>& dist0, int take, int pool) {
if (sorted_edges.empty()) return;
vector<Door> doors;
vector<Switch> switches;
vector<char> used_cell(N * N, false);
take = min({take, M, pool, (int)sorted_edges.size()});
for (int t = 0; t < take; t++) {
int rank = (long long)t * pool / take;
int eid = sorted_edges[rank];
const Edge& e = edges[eid];
int from = dist0[e.u] <= dist0[e.v] ? e.u : e.v;
int sv = choose_low_heat_switch(from, {eid}, cell_heat, used_cell);
used_cell[sv] = true;
auto [si, sj] = pos(sv);
doors.push_back({e.d, e.i, e.j, (t + 1) & 1});
switches.push_back({si, sj, 0});
}
try_candidate(move(doors), move(switches), "heatmap_alternating");
}
void add_heatmap_random_type_candidates(const vector<int>& sorted_edges, const vector<int>& cell_heat, const vector<int>& dist0, double limit) {
if ((int)sorted_edges.size() < 10) return;
vector<int> open_cells;
open_cells.reserve(N * N);
for (int v = 0; v < N * N; v++) {
if (is_open_cell(v) && v != 0 && v != N * N - 1) open_cells.push_back(v);
}
sort(open_cells.begin(), open_cells.end(), [&](int a, int b) {
int sa = 5 * dist0[a] - cell_heat[a];
int sb = 5 * dist0[b] - cell_heat[b];
if (sa != sb) return sa > sb;
return a < b;
});
int edge_pool = min(120, (int)sorted_edges.size());
int cell_pool = min(120, (int)open_cells.size());
int attempts = 0;
while (!timer.time_up(limit)) {
vector<Door> doors;
vector<Switch> switches;
vector<char> used_edge(edges.size(), false), used_cell(N * N, false);
bool reserve_wall = attempts % 3 == 0 && K >= 2;
int active_bits = reserve_wall ? K - 1 : K;
int wall_bit = K - 1;
int wall_count = reserve_wall ? 4 + (attempts % 13) : 0;
int door_count = min(M, min(edge_pool, 50));
int start = attempts % max(1, min(12, edge_pool));
for (int t = 0, rank = start; t < door_count && rank < edge_pool; rank++) {
int eid = sorted_edges[rank];
if (used_edge[eid]) continue;
used_edge[eid] = true;
const Edge& e = edges[eid];
int g;
if (reserve_wall && t < wall_count) {
g = 2 * wall_bit + 1;
} else {
int k = (t + attempts + (int)(rng() % active_bits)) % active_bits;
int parity = (int)(rng() & 1);
if ((rng() & 3) == 0) parity ^= 1;
g = 2 * k + parity;
}
doors.push_back({e.d, e.i, e.j, g});
t++;
}
for (int k = 0; k < active_bits; k++) {
int base = (attempts * 17 + k * 11) % max(1, cell_pool);
int chosen = -1;
for (int step = 0; step < cell_pool; step++) {
int v = open_cells[(base + step) % cell_pool];
if (used_cell[v]) continue;
chosen = v;
break;
}
if (chosen == -1) break;
used_cell[chosen] = true;
auto [i, j] = pos(chosen);
switches.push_back({i, j, k});
}
try_candidate(move(doors), move(switches), reserve_wall ? "heatmap_wall_type" : "heatmap_random_types");
attempts++;
}
}
int door_key(const Door& e) const {
return (e.d * N + e.i) * N + e.j;
}
bool has_duplicate_doors(const vector<Door>& doors) const {
vector<int> keys;
keys.reserve(doors.size());
for (const auto& e : doors) keys.push_back(door_key(e));
sort(keys.begin(), keys.end());
for (int i = 1; i < (int)keys.size(); i++) {
if (keys[i - 1] == keys[i]) return true;
}
return false;
}
bool add_unique_door(vector<Door>& doors, vector<char>& used_edge, int eid, int g) const {
if ((int)doors.size() >= M) return false;
if (eid < 0 || eid >= (int)edges.size() || used_edge[eid]) return false;
used_edge[eid] = true;
const Edge& e = edges[eid];
doors.push_back({e.d, e.i, e.j, g});
return true;
}
vector<int> path_vertices_from_edges(const vector<pair<int, int>>& path) const {
vector<int> vs;
if (path.empty()) return vs;
vs.push_back(path[0].second);
for (auto [eid, from] : path) {
const Edge& e = edges[eid];
int to = e.u ^ e.v ^ from;
vs.push_back(to);
}
return vs;
}
int farthest_branch_cell(int start, const vector<char>& on_path) const {
vector<int> dist(N * N, -1);
queue<int> q;
dist[start] = 0;
q.push(start);
int best = start;
while (!q.empty()) {
int u = q.front();
q.pop();
if (dist[u] > dist[best]) best = u;
for (auto [v, eid] : graph[u]) {
(void)eid;
if (on_path[v] || dist[v] != -1) continue;
dist[v] = dist[u] + 1;
q.push(v);
}
}
return best;
}
vector<int> branch_candidate_cells(int start, const vector<char>& on_path, int limit) const {
vector<int> dist(N * N, -1);
queue<int> q;
dist[start] = 0;
q.push(start);
vector<int> cells;
while (!q.empty()) {
int u = q.front();
q.pop();
cells.push_back(u);
for (auto [v, eid] : graph[u]) {
(void)eid;
if (on_path[v] || dist[v] != -1) continue;
dist[v] = dist[u] + 1;
q.push(v);
}
}
sort(cells.begin(), cells.end(), [&](int a, int b) {
if (dist[a] != dist[b]) return dist[a] > dist[b];
if (graph[a].size() != graph[b].size()) return graph[a].size() < graph[b].size();
return a < b;
});
if ((int)cells.size() > limit) cells.resize(limit);
return cells;
}
vector<pair<int, int>> branch_path_avoiding_main(int start, int goal, const vector<char>& on_path) const {
vector<int> pre_v(N * N, -1), pre_e(N * N, -1);
queue<int> q;
pre_v[start] = start;
q.push(start);
while (!q.empty()) {
int u = q.front();
q.pop();
if (u == goal) break;
for (auto [v, eid] : graph[u]) {
if (v != start && on_path[v]) continue;
if (pre_v[v] != -1) continue;
pre_v[v] = u;
pre_e[v] = eid;
q.push(v);
}
}
vector<pair<int, int>> path;
if (pre_v[goal] == -1) return path;
for (int v = goal; v != start; v = pre_v[v]) {
path.push_back({pre_e[v], pre_v[v]});
}
reverse(path.begin(), path.end());
return path;
}
void add_nested_switch_chain_candidate(const vector<pair<int, int>>& path, int variant) {
const int wall_bit = K - 1;
const int max_active = min(K - 1, 9);
if (max_active < 4 || path.empty()) return;
vector<int> pv = path_vertices_from_edges(path);
int L = (int)path.size();
if ((int)pv.size() != L + 1 || L < 14) return;
vector<int> path_idx(N * N, -1), edge_pos(edges.size(), -1), comp(N * N, -1);
vector<char> on_path(N * N, false);
for (int i = 0; i < (int)pv.size(); i++) {
path_idx[pv[i]] = i;
on_path[pv[i]] = true;
}
for (int i = 0; i < L; i++) edge_pos[path[i].first] = i;
int comp_count = 0;
for (int v = 0; v < N * N; v++) {
if (!is_open_cell(v) || on_path[v] || comp[v] != -1) continue;
queue<int> q;
comp[v] = comp_count;
q.push(v);
while (!q.empty()) {
int u = q.front();
q.pop();
for (auto [to, eid] : graph[u]) {
(void)eid;
if (on_path[to] || comp[to] != -1) continue;
comp[to] = comp_count;
q.push(to);
}
}
comp_count++;
}
if (comp_count == 0) return;
vector<vector<int>> comp_side_edges(comp_count);
vector<int> all_side_edges;
vector<char> seen_side(edges.size(), false);
struct Room {
int pos, cell, depth, comp_id;
vector<pair<int, int>> branch_path;
};
vector<Room> rooms;
int final_margin = max_active + 2 + (variant % 4);
int max_attach_pos = max(1, L - final_margin);
for (int idx = 0; idx + 1 < (int)pv.size(); idx++) {
int u = pv[idx];
for (auto [v, eid] : graph[u]) {
if (edge_pos[eid] != -1) continue;
if (!seen_side[eid]) {
seen_side[eid] = true;
all_side_edges.push_back(eid);
}
if (on_path[v] || comp[v] < 0) continue;
comp_side_edges[comp[v]].push_back(eid);
if (idx > max_attach_pos) continue;
int far = farthest_branch_cell(v, on_path);
auto bp = branch_path_avoiding_main(u, far, on_path);
if (bp.empty()) continue;
rooms.push_back({idx, far, (int)bp.size(), comp[v], move(bp)});
}
}
for (auto& xs : comp_side_edges) {
sort(xs.begin(), xs.end());
xs.erase(unique(xs.begin(), xs.end()), xs.end());
}
if (rooms.empty()) return;
auto room_score = [&](const Room& r, int b) {
int side_count = (0 <= r.comp_id && r.comp_id < comp_count) ? (int)comp_side_edges[r.comp_id].size() : 9;
int center_bonus = -abs(r.pos - max_attach_pos / 2);
int early_bonus = -r.pos;
long long sc = 1000LL * r.depth - 700LL * side_count;
if (variant & 1) sc += 9LL * center_bonus;
else sc += 4LL * early_bonus;
sc += 120LL * min(r.depth, b + 4);
return sc;
};
vector<Room> picked;
int picked_B = 0;
for (int B = max_active; B >= 4; B--) {
int needed_doors = B * (B - 1) / 2 + B;
if (needed_doors > M) continue;
vector<Room> cand(B);
vector<char> used_comp(comp_count, false), used_cell(N * N, false);
bool ok = true;
for (int b = B - 1; b >= 0; b--) {
int need_depth = max(1, b);
int best = -1;
long long best_sc = LLONG_MIN;
for (int i = 0; i < (int)rooms.size(); i++) {
const Room& r = rooms[i];
if (r.depth < need_depth || used_cell[r.cell]) continue;
if (used_comp[r.comp_id]) continue;
long long sc = room_score(r, b);
if (sc > best_sc) {
best_sc = sc;
best = i;
}
}
if (best == -1) {
ok = false;
break;
}
cand[b] = rooms[best];
used_comp[cand[b].comp_id] = true;
used_cell[cand[b].cell] = true;
}
if (ok) {
picked = move(cand);
picked_B = B;
break;
}
}
if (picked_B == 0) return;
int B = picked_B;
vector<Door> doors;
vector<Switch> switches;
vector<char> used_edge(edges.size(), false), used_cell(N * N, false);
for (int b = 0; b < B; b++) {
int cell = picked[b].cell;
if (used_cell[cell]) continue;
used_cell[cell] = true;
auto [si, sj] = pos(cell);
switches.push_back({si, sj, b});
}
for (int b = 1; b < B; b++) {
vector<pair<int, int>> conds;
for (int x = 0; x <= b - 2; x++) conds.push_back({x, 0});
conds.push_back({b - 1, 1});
const auto& bp = picked[b].branch_path;
int D = (int)bp.size();
if (D < (int)conds.size()) return;
for (int t = 0; t < (int)conds.size(); t++) {
int pi;
if (variant & 2) pi = min(D - 1, t);
else pi = min(D - 1, (int)((long long)(t + 1) * D / ((int)conds.size() + 1)));
int bit = conds[t].first;
int val = conds[t].second;
add_unique_door(doors, used_edge, bp[pi].first, 2 * bit + val);
}
}
int final_start = L - B - (variant % 3);
final_start = max(0, min(final_start, L - B));
if (final_start < 0 || final_start + B > L) return;
for (int t = 0; t < B; t++) {
int bit, val;
if (t == 0) {
bit = B - 1;
val = 1;
} else {
bit = t - 1;
val = 0;
}
add_unique_door(doors, used_edge, path[final_start + t].first, 2 * bit + val);
}
vector<int> wall_candidates;
vector<char> seen_wall(edges.size(), false);
for (int b = 0; b < B; b++) {
int cid = picked[b].comp_id;
if (cid < 0 || cid >= comp_count) continue;
for (int eid : comp_side_edges[cid]) {
if (seen_wall[eid]) continue;
bool on_own_path = false;
for (auto [peid, from] : picked[b].branch_path) {
(void)from;
if (peid == eid) {
on_own_path = true;
break;
}
}
if (on_own_path) continue;
seen_wall[eid] = true;
wall_candidates.push_back(eid);
}
}
for (int eid : all_side_edges) {
if (seen_wall[eid]) continue;
int pu = path_idx[edges[eid].u];
int pv2 = path_idx[edges[eid].v];
int p = max(pu, pv2);
if (p >= final_start - 2) {
seen_wall[eid] = true;
wall_candidates.push_back(eid);
}
}
sort(wall_candidates.begin(), wall_candidates.end(), [&](int a, int b) {
int au = max(path_idx[edges[a].u], path_idx[edges[a].v]);
int bu = max(path_idx[edges[b].u], path_idx[edges[b].v]);
if (au != bu) return au > bu;
return a < b;
});
for (int eid : wall_candidates) {
if ((int)doors.size() >= M) break;
add_unique_door(doors, used_edge, eid, 2 * wall_bit + 1);
}
try_candidate(move(doors), move(switches), "nested_switch_chain");
}
void add_full_counter_chain_candidate(const vector<pair<int, int>>& path, int variant) {
const int max_active = min(K, 10);
if (max_active < 6 || path.empty()) return;
vector<int> pv = path_vertices_from_edges(path);
int L = (int)path.size();
if ((int)pv.size() != L + 1 || L < 14) return;
vector<int> path_idx(N * N, -1), edge_pos(edges.size(), -1), comp(N * N, -1);
vector<char> on_path(N * N, false);
for (int i = 0; i < (int)pv.size(); i++) {
path_idx[pv[i]] = i;
on_path[pv[i]] = true;
}
for (int i = 0; i < L; i++) edge_pos[path[i].first] = i;
int comp_count = 0;
for (int v = 0; v < N * N; v++) {
if (!is_open_cell(v) || on_path[v] || comp[v] != -1) continue;
queue<int> q;
comp[v] = comp_count;
q.push(v);
while (!q.empty()) {
int u = q.front();
q.pop();
for (auto [to, eid] : graph[u]) {
(void)eid;
if (on_path[to] || comp[to] != -1) continue;
comp[to] = comp_count;
q.push(to);
}
}
comp_count++;
}
if (comp_count == 0) return;
vector<vector<int>> comp_side_edges(comp_count);
vector<int> all_side_edges;
vector<char> seen_side(edges.size(), false);
struct Room {
int pos, cell, depth, comp_id;
vector<pair<int, int>> branch_path;
};
vector<Room> rooms;
int final_margin = max_active + 2 + (variant % 5);
int max_attach_pos = max(1, L - final_margin);
for (int idx = 0; idx + 1 < (int)pv.size(); idx++) {
int u = pv[idx];
for (auto [v, eid] : graph[u]) {
if (edge_pos[eid] != -1) continue;
if (!seen_side[eid]) {
seen_side[eid] = true;
all_side_edges.push_back(eid);
}
if (on_path[v] || comp[v] < 0) continue;
comp_side_edges[comp[v]].push_back(eid);
if (idx > max_attach_pos) continue;
int far = farthest_branch_cell(v, on_path);
auto bp = branch_path_avoiding_main(u, far, on_path);
if (bp.empty()) continue;
rooms.push_back({idx, far, (int)bp.size(), comp[v], move(bp)});
}
}
for (auto& xs : comp_side_edges) {
sort(xs.begin(), xs.end());
xs.erase(unique(xs.begin(), xs.end()), xs.end());
}
if (rooms.empty()) return;
auto room_score = [&](const Room& r, int b, const vector<char>& used_comp) {
int side_count = (0 <= r.comp_id && r.comp_id < comp_count) ? (int)comp_side_edges[r.comp_id].size() : 9;
long long sc = 1300LL * r.depth - 650LL * side_count + 180LL * min(r.depth, b + 5);
sc += 70LL * b * min(r.depth, 12);
if (0 <= r.comp_id && r.comp_id < comp_count && used_comp[r.comp_id]) sc -= 1800;
if (variant & 1) sc -= 5LL * abs(r.pos - max_attach_pos / 2);
else sc -= 3LL * r.pos;
if (variant & 4) sc += (long long)(rng() % 900);
return sc;
};
for (int B = max_active; B >= 8; B--) {
int guard_doors = B * (B - 1) / 2;
int reserve_walls = min(8, max(0, M - guard_doors - 1));
if (B == max_active) reserve_walls = min(reserve_walls, 4 + (variant % 3) * 2);
int final_doors = min(B, M - guard_doors - reserve_walls);
if (final_doors <= 0) continue;
vector<Room> picked(B);
vector<char> used_cell(N * N, false), used_comp(comp_count, false), used_guard_edge(edges.size(), false);
bool ok = true;
for (int b = B - 1; b >= 0; b--) {
int need_depth = max(1, b);
int best = -1;
long long best_sc = LLONG_MIN;
for (int i = 0; i < (int)rooms.size(); i++) {
const Room& r = rooms[i];
if (r.depth < need_depth || used_cell[r.cell]) continue;
bool conflict = false;
for (int t = 0; t < b; t++) {
int eid = r.branch_path[t].first;
if (used_guard_edge[eid]) {
conflict = true;
break;
}
}
if (conflict) continue;
long long sc = room_score(r, b, used_comp);
if (sc > best_sc) {
best_sc = sc;
best = i;
}
}
if (best == -1) {
ok = false;
break;
}
picked[b] = rooms[best];
used_cell[picked[b].cell] = true;
if (0 <= picked[b].comp_id && picked[b].comp_id < comp_count) used_comp[picked[b].comp_id] = true;
for (int t = 0; t < b; t++) used_guard_edge[picked[b].branch_path[t].first] = true;
}
if (!ok) continue;
vector<Door> doors;
vector<Switch> switches;
vector<char> used_edge(edges.size(), false);
used_cell.assign(N * N, false);
for (int b = 0; b < B; b++) {
int cell = picked[b].cell;
if (used_cell[cell]) continue;
used_cell[cell] = true;
auto [si, sj] = pos(cell);
switches.push_back({si, sj, b});
}
bool build_ok = true;
for (int b = 1; b < B && build_ok; b++) {
const auto& bp = picked[b].branch_path;
if ((int)bp.size() < b) {
build_ok = false;
break;
}
for (int x = 0; x <= b - 2; x++) {
if (!add_unique_door(doors, used_edge, bp[x].first, 2 * x + 0)) {
build_ok = false;
break;
}
}
if (!build_ok) break;
if (!add_unique_door(doors, used_edge, bp[b - 1].first, 2 * (b - 1) + 1)) {
build_ok = false;
break;
}
}
if (!build_ok) continue;
vector<pair<int, int>> final_conds;
final_conds.push_back({B - 1, 1});
for (int b = 0; b < B - 1 && (int)final_conds.size() < final_doors; b++) {
final_conds.push_back({b, 0});
}
int final_start = L - (int)final_conds.size() - (variant % 4);
final_start = max(0, min(final_start, L - (int)final_conds.size()));
for (int t = 0; t < (int)final_conds.size(); t++) {
int bit = final_conds[t].first;
int val = final_conds[t].second;
add_unique_door(doors, used_edge, path[final_start + t].first, 2 * bit + val);
}
int wall_bit = B - 1;
vector<int> wall_candidates;
vector<char> seen_wall(edges.size(), false);
for (int b = 0; b < B; b++) {
int cid = picked[b].comp_id;
if (cid < 0 || cid >= comp_count) continue;
for (int eid : comp_side_edges[cid]) {
if (seen_wall[eid]) continue;
bool on_own_path = false;
for (auto [peid, from] : picked[b].branch_path) {
(void)from;
if (peid == eid) {
on_own_path = true;
break;
}
}
if (on_own_path) continue;
seen_wall[eid] = true;
wall_candidates.push_back(eid);
}
}
for (int eid : all_side_edges) {
if (seen_wall[eid]) continue;
int pu = path_idx[edges[eid].u];
int pv2 = path_idx[edges[eid].v];
int p = max(pu, pv2);
if (p >= final_start - 2) {
seen_wall[eid] = true;
wall_candidates.push_back(eid);
}
}
sort(wall_candidates.begin(), wall_candidates.end(), [&](int a, int b) {
int au = max(path_idx[edges[a].u], path_idx[edges[a].v]);
int bu = max(path_idx[edges[b].u], path_idx[edges[b].v]);
if (au != bu) return au > bu;
return a < b;
});
for (int eid : wall_candidates) {
if ((int)doors.size() >= M) break;
add_unique_door(doors, used_edge, eid, 2 * wall_bit + 1);
}
try_candidate(move(doors), move(switches), "full_counter_chain");
return;
}
}
void add_prefix_ladder_counter_candidate(const vector<pair<int, int>>& path, int variant) {
const int max_active = min(K, 10);
if (max_active < 7 || path.empty()) return;
vector<int> pv = path_vertices_from_edges(path);
int L = (int)path.size();
if ((int)pv.size() != L + 1 || L < 18) return;
vector<int> path_idx(N * N, -1), edge_pos(edges.size(), -1), comp(N * N, -1);
vector<char> on_path(N * N, false);
for (int i = 0; i < (int)pv.size(); i++) {
path_idx[pv[i]] = i;
on_path[pv[i]] = true;
}
for (int i = 0; i < L; i++) edge_pos[path[i].first] = i;
int comp_count = 0;
for (int v = 0; v < N * N; v++) {
if (!is_open_cell(v) || on_path[v] || comp[v] != -1) continue;
queue<int> q;
comp[v] = comp_count;
q.push(v);
while (!q.empty()) {
int u = q.front();
q.pop();
for (auto [to, eid] : graph[u]) {
(void)eid;
if (on_path[to] || comp[to] != -1) continue;
comp[to] = comp_count;
q.push(to);
}
}
comp_count++;
}
if (comp_count == 0) return;
struct Room {
int pos, cell, depth, first_eid, comp_id;
vector<pair<int, int>> branch_path;
};
vector<Room> rooms;
vector<vector<int>> comp_side_edges(comp_count);
vector<int> all_side_edges;
vector<char> seen_side(edges.size(), false);
int max_attach_pos = max(1, L - 4 - (variant % 5));
for (int idx = 0; idx + 1 < (int)pv.size(); idx++) {
int u = pv[idx];
for (auto [v, eid] : graph[u]) {
if (edge_pos[eid] != -1) continue;
if (!seen_side[eid]) {
seen_side[eid] = true;
all_side_edges.push_back(eid);
}
if (on_path[v] || comp[v] < 0) continue;
comp_side_edges[comp[v]].push_back(eid);
if (idx > max_attach_pos) continue;
int far = farthest_branch_cell(v, on_path);
auto bp = branch_path_avoiding_main(u, far, on_path);
if (bp.empty()) continue;
rooms.push_back({idx, far, (int)bp.size(), bp[0].first, comp[v], move(bp)});
}
}
for (auto& xs : comp_side_edges) {
sort(xs.begin(), xs.end());
xs.erase(unique(xs.begin(), xs.end()), xs.end());
}
if (rooms.empty()) return;
auto base_room_score = [&](const Room& r, int t, int B, bool used_comp) {
int side_count = (0 <= r.comp_id && r.comp_id < comp_count) ? (int)comp_side_edges[r.comp_id].size() : 9;
int weight_shift = max(0, B - 2 - t);
long long weight = 1LL << min(weight_shift, 9);
long long sc = weight * min(r.depth, 20) * 40LL + 900LL * r.depth - 700LL * side_count;
if (used_comp) sc -= 2500;
if (variant & 1) sc -= 5LL * r.pos;
else sc -= 4LL * abs(r.pos - (t + 1) * L / max(1, B));
if (variant & 8) sc += (long long)(rng() % 1200);
return sc;
};
// variant の 256 bit が立っているときだけ、スイッチ部屋の分散を評価する。
// 既存の prefix_ladder_counter 候補を壊さず、追加候補として試すための実装。
// 距離は厳密 BFS ではなく「主経路上の距離 + 枝の深さ」で近似している。
auto room_dist = [&](const Room& a, const Room& b) {
return abs(a.pos - b.pos) + a.depth + b.depth;
};
auto switch_spread_bonus = [&](const Room& r, const vector<int>& selected, int upto) {
if ((variant & 256) == 0 || upto <= 0) return 0LL;
int min_d = 1e9;
int sum_d = 0;
int max_d = 0;
for (int x = 0; x < upto; x++) {
if (selected[x] < 0) continue;
int d = room_dist(r, rooms[selected[x]]);
min_d = min(min_d, d);
max_d = max(max_d, d);
sum_d += min(d, 45);
}
if (min_d == (int)1e9) return 0LL;
// 256+0.., 256+16.., 256+32.. で距離の効かせ方を少し変える。
int mode = (variant >> 4) & 3;
long long bonus = 0;
if (mode == 0) {
bonus += 55LL * min(min_d, 30);
bonus += 8LL * sum_d;
} else if (mode == 1) {
bonus += 95LL * min(min_d, 34);
bonus += 5LL * sum_d;
} else if (mode == 2) {
bonus += 35LL * min(min_d, 30);
bonus += 18LL * sum_d;
} else {
bonus += 60LL * min(min_d, 32);
bonus += 10LL * sum_d;
bonus += 30LL * min(max_d, 45);
}
return bonus;
};
for (int B = max_active; B >= 7; B--) {
int stages = B - 1;
int skeleton_doors = stages * 2 + 1;
if (skeleton_doors > M) continue;
vector<int> selected(stages, -1);
vector<char> used_cell(N * N, false), used_comp(comp_count, false);
int prev_pos = -1;
bool ok = true;
for (int t = 0; t < stages; t++) {
int best = -1;
long long best_sc = LLONG_MIN;
int remaining = stages - 1 - t;
for (int ri = 0; ri < (int)rooms.size(); ri++) {
const Room& r = rooms[ri];
if (r.pos <= prev_pos) continue;
if (r.pos >= L - 1 - remaining) continue;
if (used_cell[r.cell]) continue;
if (!(variant & 2) && 0 <= r.comp_id && r.comp_id < comp_count && used_comp[r.comp_id]) continue;
long long sc = base_room_score(r, t, B, 0 <= r.comp_id && r.comp_id < comp_count && used_comp[r.comp_id]);
sc += switch_spread_bonus(r, selected, t);
if (sc > best_sc) {
best_sc = sc;
best = ri;
}
}
if (best == -1) {
ok = false;
break;
}
selected[t] = best;
prev_pos = rooms[best].pos;
used_cell[rooms[best].cell] = true;
if (0 <= rooms[best].comp_id && rooms[best].comp_id < comp_count) used_comp[rooms[best].comp_id] = true;
}
if (!ok) continue;
int sw0_room = -1;
long long best_sw0 = LLONG_MIN;
int first_pos = rooms[selected[0]].pos;
for (int ri = 0; ri < (int)rooms.size(); ri++) {
const Room& r = rooms[ri];
if (r.pos > first_pos) continue;
if (used_cell[r.cell]) continue;
bool uc = 0 <= r.comp_id && r.comp_id < comp_count && used_comp[r.comp_id];
long long sc = 22000LL * min(r.depth, 24) - 800LL * ((0 <= r.comp_id && r.comp_id < comp_count) ? (int)comp_side_edges[r.comp_id].size() : 9);
if (uc) sc -= 3500;
sc -= 15LL * r.pos;
if (variant & 256) {
int min_d0 = 1e9;
int sum_d0 = 0;
for (int idx : selected) {
if (idx < 0) continue;
int d = room_dist(r, rooms[idx]);
min_d0 = min(min_d0, d);
sum_d0 += min(d, 45);
}
if (min_d0 != (int)1e9) {
sc += 45LL * min(min_d0, 32) + 5LL * sum_d0;
}
}
if (sc > best_sw0) {
best_sw0 = sc;
sw0_room = ri;
}
}
vector<Door> doors;
vector<Switch> switches;
vector<char> used_edge(edges.size(), false), selected_side(edges.size(), false);
int sw0_cell = pv[0];
if (sw0_room != -1) {
sw0_cell = rooms[sw0_room].cell;
for (auto [eid, from] : rooms[sw0_room].branch_path) {
(void)from;
selected_side[eid] = true;
}
}
auto [s0i, s0j] = pos(sw0_cell);
switches.push_back({s0i, s0j, 0});
bool build_ok = true;
for (int t = 0; t < stages && build_ok; t++) {
const Room& r = rooms[selected[t]];
int gate_bit = t;
int switch_bit = t + 1;
if (!add_unique_door(doors, used_edge, r.first_eid, 2 * gate_bit + 1)) {
build_ok = false;
break;
}
selected_side[r.first_eid] = true;
auto [si, sj] = pos(r.cell);
switches.push_back({si, sj, switch_bit});
int ladder_eid = path[r.pos].first;
if (!add_unique_door(doors, used_edge, ladder_eid, 2 * gate_bit + 0)) {
build_ok = false;
break;
}
}
if (!build_ok) continue;
int final_pos = -1;
for (int p = L - 1 - (variant % 3); p > rooms[selected.back()].pos; p--) {
if (0 <= p && p < L && !used_edge[path[p].first]) {
final_pos = p;
break;
}
}
if (final_pos == -1) {
for (int p = rooms[selected.back()].pos + 1; p < L; p++) {
if (!used_edge[path[p].first]) {
final_pos = p;
break;
}
}
}
if (final_pos == -1) continue;
add_unique_door(doors, used_edge, path[final_pos].first, 2 * (B - 1) + 1);
vector<int> wall_candidates;
vector<char> seen_wall(edges.size(), false);
auto add_wall_from_comp = [&](int cid) {
if (cid < 0 || cid >= comp_count) return;
for (int eid : comp_side_edges[cid]) {
if (seen_wall[eid] || selected_side[eid]) continue;
seen_wall[eid] = true;
wall_candidates.push_back(eid);
}
};
if (sw0_room != -1) add_wall_from_comp(rooms[sw0_room].comp_id);
for (int idx : selected) add_wall_from_comp(rooms[idx].comp_id);
for (int eid : all_side_edges) {
if (seen_wall[eid] || selected_side[eid]) continue;
int pu = path_idx[edges[eid].u];
int pv2 = path_idx[edges[eid].v];
int p = max(pu, pv2);
if (p >= rooms[selected[0]].pos - 1) {
seen_wall[eid] = true;
wall_candidates.push_back(eid);
}
}
sort(wall_candidates.begin(), wall_candidates.end(), [&](int a, int b) {
int au = max(path_idx[edges[a].u], path_idx[edges[a].v]);
int bu = max(path_idx[edges[b].u], path_idx[edges[b].v]);
if (au != bu) return au > bu;
return a < b;
});
int wall_bit = B - 1;
for (int eid : wall_candidates) {
if ((int)doors.size() >= M) break;
add_unique_door(doors, used_edge, eid, 2 * wall_bit + 1);
}
try_candidate(move(doors), move(switches), "prefix_ladder_counter");
return;
}
}
void add_double_prefix_ladder_candidate(const vector<pair<int, int>>& path, int variant) {
const int B = 8;
const int stages = B - 1;
const int phase_bit = 8;
const int wall_bit = 9;
if (K < 10 || path.empty()) return;
vector<int> pv = path_vertices_from_edges(path);
int L = (int)path.size();
if ((int)pv.size() != L + 1 || L < 34) return;
vector<int> path_idx(N * N, -1), edge_pos(edges.size(), -1), comp(N * N, -1);
vector<char> on_path(N * N, false);
for (int i = 0; i < (int)pv.size(); i++) {
path_idx[pv[i]] = i;
on_path[pv[i]] = true;
}
for (int i = 0; i < L; i++) edge_pos[path[i].first] = i;
int comp_count = 0;
for (int v = 0; v < N * N; v++) {
if (!is_open_cell(v) || on_path[v] || comp[v] != -1) continue;
queue<int> q;
comp[v] = comp_count;
q.push(v);
while (!q.empty()) {
int u = q.front();
q.pop();
for (auto [to, eid] : graph[u]) {
(void)eid;
if (on_path[to] || comp[to] != -1) continue;
comp[to] = comp_count;
q.push(to);
}
}
comp_count++;
}
if (comp_count == 0) return;
struct Room {
int pos, cell, depth, first_eid, comp_id;
vector<pair<int, int>> branch_path;
};
vector<Room> rooms;
vector<vector<int>> comp_side_edges(comp_count);
vector<int> all_side_edges;
vector<char> seen_side(edges.size(), false);
int margin = 3 + (variant % 3);
for (int idx = 0; idx + 1 < (int)pv.size(); idx++) {
int u = pv[idx];
for (auto [v, eid] : graph[u]) {
if (edge_pos[eid] != -1) continue;
if (!seen_side[eid]) {
seen_side[eid] = true;
all_side_edges.push_back(eid);
}
if (on_path[v] || comp[v] < 0) continue;
comp_side_edges[comp[v]].push_back(eid);
if (idx < margin || idx > L - 2 - margin) continue;
int room_limit = (variant & 4) ? 3 : 2;
for (int cell : branch_candidate_cells(v, on_path, room_limit)) {
auto bp = branch_path_avoiding_main(u, cell, on_path);
if (bp.empty()) continue;
rooms.push_back({idx, cell, (int)bp.size(), bp[0].first, comp[v], move(bp)});
}
}
}
for (auto& xs : comp_side_edges) {
sort(xs.begin(), xs.end());
xs.erase(unique(xs.begin(), xs.end()), xs.end());
}
if ((int)rooms.size() < stages * 2) return;
int split = L * (54 + (variant % 6) * 4) / 100;
split = max(12, min(L - 13, split));
int first_lo = 1;
int first_hi = split - 4;
int second_lo = split + 3;
int second_hi = L - 3;
if (first_hi - first_lo + 1 < stages || second_hi - second_lo + 1 < stages) return;
vector<char> used_cell(N * N, false), used_comp(comp_count, false);
vector<int> selected1, selected2;
auto room_score = [&](const Room& r, int t, int lo, int hi, bool already_comp, bool first_segment) {
int side_count = (0 <= r.comp_id && r.comp_id < comp_count) ? (int)comp_side_edges[r.comp_id].size() : 9;
int weight_shift = max(0, B - 2 - t);
long long weight = 1LL << min(weight_shift, 8);
long long sc = weight * min(r.depth, 18) * 42LL + 850LL * r.depth - 620LL * side_count;
if (first_segment && !(variant & 4) && r.depth < 2) sc -= 25000;
if (already_comp) sc -= 1800;
int target = lo + (long long)(t + 1) * max(1, hi - lo + 1) / B;
if (variant & 1) sc -= 5LL * r.pos;
else sc -= 5LL * abs(r.pos - target);
if (variant & 16) sc += (long long)(rng() % 1500);
return sc;
};
auto select_segment = [&](int lo, int hi, bool first_segment, vector<int>& selected) {
int prev = lo - 1;
selected.assign(stages, -1);
for (int t = 0; t < stages; t++) {
int remaining = stages - 1 - t;
int best = -1;
long long best_sc = LLONG_MIN;
for (int ri = 0; ri < (int)rooms.size(); ri++) {
const Room& r = rooms[ri];
if (r.pos < lo || r.pos > hi) continue;
if (r.pos <= prev) continue;
if (r.pos > hi - remaining) continue;
if (used_cell[r.cell]) continue;
int future_positions = 0;
int last_future_pos = -1;
for (int rj = 0; rj < (int)rooms.size(); rj++) {
const Room& nr = rooms[rj];
if (nr.pos <= r.pos || nr.pos > hi) continue;
if (used_cell[nr.cell]) continue;
if (nr.pos == last_future_pos) continue;
last_future_pos = nr.pos;
future_positions++;
}
if (future_positions < remaining) continue;
bool already_comp = 0 <= r.comp_id && r.comp_id < comp_count && used_comp[r.comp_id];
long long sc = room_score(r, t, lo, hi, already_comp, first_segment);
if (sc > best_sc) {
best_sc = sc;
best = ri;
}
}
if (best == -1) return false;
selected[t] = best;
prev = rooms[best].pos;
used_cell[rooms[best].cell] = true;
if (0 <= rooms[best].comp_id && rooms[best].comp_id < comp_count) used_comp[rooms[best].comp_id] = true;
}
return true;
};
if (!select_segment(first_lo, first_hi, true, selected1)) return;
if (!select_segment(second_lo, second_hi, false, selected2)) return;
vector<Door> doors;
vector<Switch> switches;
vector<char> used_edge(edges.size(), false), selected_side(edges.size(), false), used_switch_cell(N * N, false);
vector<char> reserved_gate_edge(edges.size(), false);
for (int idx : selected1) reserved_gate_edge[rooms[idx].first_eid] = true;
for (int idx : selected2) reserved_gate_edge[rooms[idx].first_eid] = true;
auto mark_branch = [&](const Room& r) {
selected_side[r.first_eid] = true;
};
auto add_switch_at = [&](int cell, int bit) {
if (cell < 0 || cell >= N * N || used_switch_cell[cell]) return false;
used_switch_cell[cell] = true;
auto [i, j] = pos(cell);
switches.push_back({i, j, bit});
return true;
};
auto add_sw0 = [&](int lo, int hi, int first_selected_pos) {
int best_room = -1;
long long best_sc = LLONG_MIN;
for (int ri = 0; ri < (int)rooms.size(); ri++) {
const Room& r = rooms[ri];
if (r.pos < lo || r.pos > min(hi, first_selected_pos)) continue;
if (used_switch_cell[r.cell]) continue;
if (used_cell[r.cell]) continue;
if (reserved_gate_edge[r.first_eid]) continue;
int side_count = (0 <= r.comp_id && r.comp_id < comp_count) ? (int)comp_side_edges[r.comp_id].size() : 9;
long long sc = 18000LL * min(r.depth, 22) - 750LL * side_count - 8LL * abs(r.pos - lo);
if (sc > best_sc) {
best_sc = sc;
best_room = ri;
}
}
if (best_room != -1) {
const Room& r = rooms[best_room];
mark_branch(r);
return add_switch_at(r.cell, 0);
}
int cell = pv[max(0, min(L, lo))];
return add_switch_at(cell, 0);
};
if (!add_sw0(first_lo, first_hi, rooms[selected1[0]].pos)) return;
auto build_ladder = [&](const vector<int>& selected, int final_bit_value, bool first_segment) {
for (int t = 0; t < stages; t++) {
const Room& r = rooms[selected[t]];
int gate_bit = t;
int switch_bit = t + 1;
if (!add_unique_door(doors, used_edge, r.first_eid, 2 * gate_bit + 1)) return false;
mark_branch(r);
if (!add_switch_at(r.cell, switch_bit)) return false;
if (!add_unique_door(doors, used_edge, path[r.pos].first, 2 * gate_bit + 0)) return false;
if (first_segment && r.branch_path.size() >= 2) {
add_unique_door(doors, used_edge, r.branch_path[1].first, 2 * phase_bit + 0);
}
}
int last_pos = rooms[selected.back()].pos;
int final_limit = first_segment ? split - 2 : L - 1;
int final_pos = -1;
for (int p = final_limit; p > last_pos; p--) {
if (0 <= p && p < L && !used_edge[path[p].first]) {
final_pos = p;
break;
}
}
if (final_pos == -1) return false;
return add_unique_door(doors, used_edge, path[final_pos].first, 2 * (B - 1) + final_bit_value);
};
if (!build_ladder(selected1, 1, true)) return;
int phase_pos = -1;
int phase_lo = max(split - 1, rooms[selected1.back()].pos + 1);
int phase_hi = rooms[selected2.front()].pos - 1;
for (int p = phase_lo; p <= phase_hi; p++) {
if (0 <= p && p < L && !used_edge[path[p].first]) {
phase_pos = p;
break;
}
}
if (phase_pos == -1) return;
if (!add_switch_at(pv[phase_pos], phase_bit)) return;
if (!add_unique_door(doors, used_edge, path[phase_pos].first, 2 * phase_bit + 1)) return;
if (!add_sw0(max(second_lo, phase_pos + 1), second_hi, rooms[selected2[0]].pos)) return;
if (!build_ladder(selected2, 0, false)) return;
vector<int> wall_candidates;
vector<char> seen_wall(edges.size(), false);
auto add_wall_from_comp = [&](int cid) {
if (cid < 0 || cid >= comp_count) return;
for (int eid : comp_side_edges[cid]) {
if (seen_wall[eid] || selected_side[eid] || used_edge[eid]) continue;
seen_wall[eid] = true;
wall_candidates.push_back(eid);
}
};
for (int idx : selected1) add_wall_from_comp(rooms[idx].comp_id);
for (int idx : selected2) add_wall_from_comp(rooms[idx].comp_id);
for (int eid : all_side_edges) {
if (seen_wall[eid] || selected_side[eid] || used_edge[eid]) continue;
int pu = path_idx[edges[eid].u];
int pv2 = path_idx[edges[eid].v];
int p = max(pu, pv2);
if (p >= rooms[selected1[0]].pos - 1) {
seen_wall[eid] = true;
wall_candidates.push_back(eid);
}
}
sort(wall_candidates.begin(), wall_candidates.end(), [&](int a, int b) {
int au = max(path_idx[edges[a].u], path_idx[edges[a].v]);
int bu = max(path_idx[edges[b].u], path_idx[edges[b].v]);
if (au != bu) return au > bu;
return a < b;
});
for (int eid : wall_candidates) {
if ((int)doors.size() >= M) break;
add_unique_door(doors, used_edge, eid, 2 * wall_bit + 1);
}
try_candidate(move(doors), move(switches), "double_prefix_ladder");
}
void add_banked_switch_chain_candidate(const vector<pair<int, int>>& path, int variant) {
const int bank_bit = 5;
const int counter_bits = 8;
const int banked_low = 2 + (variant % 3);
const int wall_bit = K - 1;
if (counter_bits >= K || bank_bit >= K || wall_bit == bank_bit || path.empty()) return;
vector<int> pv = path_vertices_from_edges(path);
int L = (int)path.size();
if ((int)pv.size() != L + 1 || L < 14) return;
vector<int> path_idx(N * N, -1), edge_pos(edges.size(), -1), comp(N * N, -1);
vector<char> on_path(N * N, false);
for (int i = 0; i < (int)pv.size(); i++) {
path_idx[pv[i]] = i;
on_path[pv[i]] = true;
}
for (int i = 0; i < L; i++) edge_pos[path[i].first] = i;
int comp_count = 0;
for (int v = 0; v < N * N; v++) {
if (!is_open_cell(v) || on_path[v] || comp[v] != -1) continue;
queue<int> q;
comp[v] = comp_count;
q.push(v);
while (!q.empty()) {
int u = q.front();
q.pop();
for (auto [to, eid] : graph[u]) {
(void)eid;
if (on_path[to] || comp[to] != -1) continue;
comp[to] = comp_count;
q.push(to);
}
}
comp_count++;
}
if (comp_count == 0) return;
vector<vector<int>> comp_side_edges(comp_count);
vector<int> all_side_edges;
vector<char> seen_side(edges.size(), false);
struct Room {
int pos, cell, depth, comp_id;
vector<pair<int, int>> branch_path;
};
vector<Room> rooms;
int final_margin = 8 + (variant % 4);
int max_attach_pos = max(1, L - final_margin);
for (int idx = 0; idx + 1 < (int)pv.size(); idx++) {
int u = pv[idx];
for (auto [v, eid] : graph[u]) {
if (edge_pos[eid] != -1) continue;
if (!seen_side[eid]) {
seen_side[eid] = true;
all_side_edges.push_back(eid);
}
if (on_path[v] || comp[v] < 0) continue;
comp_side_edges[comp[v]].push_back(eid);
if (idx > max_attach_pos) continue;
int far = farthest_branch_cell(v, on_path);
auto bp = branch_path_avoiding_main(u, far, on_path);
if (bp.empty()) continue;
rooms.push_back({idx, far, (int)bp.size(), comp[v], move(bp)});
}
}
for (auto& xs : comp_side_edges) {
sort(xs.begin(), xs.end());
xs.erase(unique(xs.begin(), xs.end()), xs.end());
}
if (rooms.empty()) return;
struct Task {
int bit, page, weight, room = -1;
vector<pair<int, int>> conds;
};
vector<Task> tasks;
auto counter_cond = [&](int b) {
vector<pair<int, int>> conds;
for (int x = 0; x <= b - 2; x++) conds.push_back({x, 0});
if (b >= 1) conds.push_back({b - 1, 1});
return conds;
};
for (int b = 0; b < counter_bits; b++) {
auto conds = counter_cond(b);
if (b < banked_low) conds.insert(conds.begin(), {bank_bit, 0});
tasks.push_back({b, 0, 1 << max(0, counter_bits - 1 - b), -1, conds});
}
for (int b = 0; b < banked_low; b++) {
auto conds = counter_cond(b);
conds.insert(conds.begin(), {bank_bit, 1});
tasks.push_back({b, 1, 1 << max(0, counter_bits - 1 - b), -1, conds});
}
int fixed_doors = counter_bits;
for (const auto& t : tasks) fixed_doors += (int)t.conds.size();
if (fixed_doors > M) {
if (variant % 3 != 2) return;
return;
}
vector<int> order(tasks.size());
iota(order.begin(), order.end(), 0);
sort(order.begin(), order.end(), [&](int a, int b) {
const Task& A = tasks[a];
const Task& B = tasks[b];
if ((variant & 3) == 0) {
if ((int)A.conds.size() != (int)B.conds.size()) return A.conds.size() > B.conds.size();
return A.weight > B.weight;
}
if ((variant & 3) == 1) {
if (A.weight != B.weight) return A.weight > B.weight;
return A.conds.size() > B.conds.size();
}
long long sa = 100LL * A.weight + 17LL * (int)A.conds.size() + A.page;
long long sb = 100LL * B.weight + 17LL * (int)B.conds.size() + B.page;
if (sa != sb) return sa > sb;
return a < b;
});
vector<char> used_cell(N * N, false), used_comp(comp_count, false);
auto room_score = [&](const Room& r, const Task& t) {
int side_count = (0 <= r.comp_id && r.comp_id < comp_count) ? (int)comp_side_edges[r.comp_id].size() : 9;
long long sc = 120LL * t.weight * min(r.depth, 18) + 900LL * r.depth - 650LL * side_count;
int target_pos = (t.page == 0 ? max_attach_pos / 3 : max_attach_pos * 2 / 3);
sc -= 3LL * abs(r.pos - target_pos);
if (variant & 4) sc += (long long)(rng() % 700);
return sc;
};
for (int pass_allow_comp = 0; pass_allow_comp < 2; pass_allow_comp++) {
bool progress = false;
for (int ti : order) {
if (tasks[ti].room != -1) continue;
int best = -1;
long long best_sc = LLONG_MIN;
int need_depth = (int)tasks[ti].conds.size();
for (int ri = 0; ri < (int)rooms.size(); ri++) {
const Room& r = rooms[ri];
if (r.depth < need_depth || used_cell[r.cell]) continue;
if (!pass_allow_comp && used_comp[r.comp_id]) continue;
long long sc = room_score(r, tasks[ti]);
if (sc > best_sc) {
best_sc = sc;
best = ri;
}
}
if (best == -1) continue;
tasks[ti].room = best;
used_cell[rooms[best].cell] = true;
if (0 <= rooms[best].comp_id && rooms[best].comp_id < comp_count) used_comp[rooms[best].comp_id] = true;
progress = true;
}
if (!progress) break;
}
for (const auto& t : tasks) {
if (t.room == -1) return;
}
vector<Door> doors;
vector<Switch> switches;
vector<char> used_edge(edges.size(), false);
used_cell.assign(N * N, false);
auto add_guarded_room = [&](const Task& t) -> bool {
const Room& r = rooms[t.room];
if ((int)r.branch_path.size() < (int)t.conds.size()) return false;
if (!used_cell[r.cell]) {
used_cell[r.cell] = true;
auto [si, sj] = pos(r.cell);
switches.push_back({si, sj, t.bit});
}
for (int i = 0; i < (int)t.conds.size(); i++) {
int eid = r.branch_path[i].first;
int bit = t.conds[i].first;
int val = t.conds[i].second;
if (!add_unique_door(doors, used_edge, eid, 2 * bit + val)) return false;
}
return true;
};
for (const auto& t : tasks) {
if (!add_guarded_room(t)) return;
}
vector<pair<int, int>> final_conds;
final_conds.push_back({counter_bits - 1, 1});
for (int b = 0; b < counter_bits - 1; b++) final_conds.push_back({b, 0});
int final_start = L - (int)final_conds.size() - (variant % 3);
final_start = max(0, min(final_start, L - (int)final_conds.size()));
for (int i = 0; i < (int)final_conds.size(); i++) {
int bit = final_conds[i].first;
int val = final_conds[i].second;
add_unique_door(doors, used_edge, path[final_start + i].first, 2 * bit + val);
}
vector<unordered_set<int>> allowed_eids(comp_count);
for (const auto& t : tasks) {
const Room& r = rooms[t.room];
if (r.comp_id < 0 || r.comp_id >= comp_count) continue;
for (auto [eid, from] : r.branch_path) {
(void)from;
allowed_eids[r.comp_id].insert(eid);
}
}
vector<int> wall_candidates;
vector<char> seen_wall(edges.size(), false);
for (const auto& t : tasks) {
const Room& r = rooms[t.room];
int cid = r.comp_id;
if (cid < 0 || cid >= comp_count) continue;
for (int eid : comp_side_edges[cid]) {
if (seen_wall[eid]) continue;
if (allowed_eids[cid].count(eid)) continue;
seen_wall[eid] = true;
wall_candidates.push_back(eid);
}
}
for (int eid : all_side_edges) {
if (seen_wall[eid]) continue;
int pu = path_idx[edges[eid].u];
int pv2 = path_idx[edges[eid].v];
int p = max(pu, pv2);
if (p >= final_start - 2) {
seen_wall[eid] = true;
wall_candidates.push_back(eid);
}
}
sort(wall_candidates.begin(), wall_candidates.end(), [&](int a, int b) {
int au = max(path_idx[edges[a].u], path_idx[edges[a].v]);
int bu = max(path_idx[edges[b].u], path_idx[edges[b].v]);
if (au != bu) return au > bu;
return a < b;
});
for (int eid : wall_candidates) {
if ((int)doors.size() >= M) break;
add_unique_door(doors, used_edge, eid, 2 * wall_bit + 1);
}
try_candidate(move(doors), move(switches), "banked_switch_chain");
}
void add_switch_room_hanoi_candidate(const vector<pair<int, int>>& path, int variant) {
const int wall_bit = K - 1;
const int active_bits = K - 1;
if (active_bits <= 0 || path.empty()) return;
vector<int> pv = path_vertices_from_edges(path);
int L = (int)path.size();
if (L < active_bits + 4) return;
vector<int> path_idx(N * N, -1), edge_pos(edges.size(), -1);
vector<char> on_path(N * N, false);
for (int i = 0; i < (int)pv.size(); i++) {
path_idx[pv[i]] = i;
on_path[pv[i]] = true;
}
for (int i = 0; i < L; i++) edge_pos[path[i].first] = i;
struct Room {
int pos, cell, depth;
vector<pair<int, int>> branch_path;
};
vector<Room> rooms;
vector<int> side_edges;
for (int idx = 0; idx < (int)pv.size(); idx++) {
int u = pv[idx];
for (auto [v, eid] : graph[u]) {
if (edge_pos[eid] != -1) continue;
side_edges.push_back(eid);
if (on_path[v]) continue;
int far = farthest_branch_cell(v, on_path);
auto bp = branch_path_avoiding_main(u, far, on_path);
if (bp.empty()) continue;
rooms.push_back({idx, far, (int)bp.size(), move(bp)});
}
}
sort(side_edges.begin(), side_edges.end());
side_edges.erase(unique(side_edges.begin(), side_edges.end()), side_edges.end());
if (rooms.empty()) return;
sort(rooms.begin(), rooms.end(), [&](const Room& a, const Room& b) {
if (a.depth != b.depth) return a.depth > b.depth;
return a.pos < b.pos;
});
vector<Room> picked;
vector<char> used_cell(N * N, false);
int min_gap = max(1, L / (active_bits + 2));
for (const auto& r : rooms) {
if ((int)picked.size() >= active_bits) break;
if (used_cell[r.cell]) continue;
bool ok = true;
for (const auto& p : picked) {
if (abs(p.pos - r.pos) < min_gap / 2) {
ok = false;
break;
}
}
if (!ok && (int)rooms.size() >= active_bits * 2) continue;
used_cell[r.cell] = true;
picked.push_back(r);
}
for (const auto& r : rooms) {
if ((int)picked.size() >= active_bits) break;
if (used_cell[r.cell]) continue;
used_cell[r.cell] = true;
picked.push_back(r);
}
if (picked.empty()) return;
sort(picked.begin(), picked.end(), [&](const Room& a, const Room& b) {
return a.pos < b.pos;
});
vector<Door> doors;
vector<Switch> switches;
vector<char> used_edge(edges.size(), false);
int usable = min(active_bits, (int)picked.size());
for (int k = 0; k < usable; k++) {
auto [si, sj] = pos(picked[k].cell);
switches.push_back({si, sj, k});
}
auto need_bit = [&](int k, int b) {
int mode = variant % 6;
if (mode == 0) return 1;
if (mode == 1) return 0;
if (mode == 2) return (k >> b) & 1;
if (mode == 3) return (((k + 1) ^ ((k + 1) >> 1)) >> b) & 1;
if (mode == 4) return (b + k) & 1;
return ((variant >> (b % 5)) ^ k ^ b) & 1;
};
for (int k = 1; k < usable; k++) {
const auto& bp = picked[k].branch_path;
int need_count = k;
int B = (int)bp.size();
for (int b = 0; b < need_count && (int)doors.size() < M; b++) {
int pi = min(B - 1, max(0, (int)((long long)(b + 1) * B / (need_count + 1))));
add_unique_door(doors, used_edge, bp[pi].first, 2 * b + need_bit(k, b));
}
}
for (int k = 0; k < usable && (int)doors.size() < M; k++) {
int gate_pos = min(L - 1, max(0, picked[k].pos + max(1, L / (usable + 3))));
int eid = path[gate_pos].first;
int target = 1;
if (variant & 8) target = (k + 1) & 1;
if (variant & 16) target ^= (variant >> (k % 4)) & 1;
add_unique_door(doors, used_edge, eid, 2 * k + target);
}
int wall_budget = max(0, M - (int)doors.size());
vector<int> wall_candidates = side_edges;
sort(wall_candidates.begin(), wall_candidates.end(), [&](int a, int b) {
int pa = min(path_idx[edges[a].u] == -1 ? 100000 : path_idx[edges[a].u],
path_idx[edges[a].v] == -1 ? 100000 : path_idx[edges[a].v]);
int pb = min(path_idx[edges[b].u] == -1 ? 100000 : path_idx[edges[b].u],
path_idx[edges[b].v] == -1 ? 100000 : path_idx[edges[b].v]);
return pa < pb;
});
int walls = 0;
for (int eid : wall_candidates) {
if (walls >= wall_budget) break;
bool keep = false;
for (int k = 0; k < usable; k++) {
if (!picked[k].branch_path.empty() && picked[k].branch_path[0].first == eid) {
keep = true;
break;
}
}
if (keep) continue;
if (add_unique_door(doors, used_edge, eid, 2 * wall_bit + 1)) walls++;
}
try_candidate(move(doors), move(switches), "switch_room_hanoi");
}
void add_counter_relay_hanoi_candidate(const vector<pair<int, int>>& path, int variant) {
const int wall_bit = K - 1;
const int active_bits = K - 1;
if (active_bits <= 0 || path.empty()) return;
vector<int> pv = path_vertices_from_edges(path);
int L = (int)path.size();
if (L < 10) return;
vector<int> path_idx(N * N, -1), edge_pos(edges.size(), -1), comp(N * N, -1);
vector<char> on_path(N * N, false);
for (int i = 0; i < (int)pv.size(); i++) {
path_idx[pv[i]] = i;
on_path[pv[i]] = true;
}
for (int i = 0; i < L; i++) edge_pos[path[i].first] = i;
int comp_count = 0;
for (int v = 0; v < N * N; v++) {
if (!is_open_cell(v) || on_path[v] || comp[v] != -1) continue;
queue<int> q;
comp[v] = comp_count;
q.push(v);
while (!q.empty()) {
int u = q.front();
q.pop();
for (auto [to, eid] : graph[u]) {
(void)eid;
if (on_path[to] || comp[to] != -1) continue;
comp[to] = comp_count;
q.push(to);
}
}
comp_count++;
}
if (comp_count == 0) return;
struct Room {
int pos, cell, depth, first_eid, comp_id;
};
vector<Room> rooms;
vector<int> side_edges;
for (int idx = 0; idx + 1 < (int)pv.size(); idx++) {
int u = pv[idx];
for (auto [v, eid] : graph[u]) {
if (edge_pos[eid] != -1) continue;
side_edges.push_back(eid);
if (on_path[v] || comp[v] < 0) continue;
int far = farthest_branch_cell(v, on_path);
auto bp = branch_path_avoiding_main(u, far, on_path);
if (bp.empty()) continue;
rooms.push_back({idx, far, (int)bp.size(), bp[0].first, comp[v]});
}
}
sort(side_edges.begin(), side_edges.end());
side_edges.erase(unique(side_edges.begin(), side_edges.end()), side_edges.end());
if (rooms.empty()) return;
int wall_budget = min((int)side_edges.size(), 8 + (variant % 4) * 3);
int gate_budget = min(M - wall_budget, 30 + (variant % 3) * 4);
if (gate_budget <= 0) return;
sort(rooms.begin(), rooms.end(), [&](const Room& a, const Room& b) {
long long sa = 120LL * a.depth + 3LL * min(a.pos, L - a.pos);
long long sb = 120LL * b.depth + 3LL * min(b.pos, L - b.pos);
if (sa != sb) return sa > sb;
return a.pos < b.pos;
});
vector<Room> picked;
vector<char> used_comp(comp_count, false), used_cell(N * N, false);
int min_gap = max(1, L / max(6, gate_budget / 2));
for (int pass = 0; pass < 2; pass++) {
for (const auto& r : rooms) {
if ((int)picked.size() >= gate_budget) break;
if (used_comp[r.comp_id] || used_cell[r.cell]) continue;
if (pass == 0) {
bool ok = true;
for (const auto& p : picked) {
if (abs(p.pos - r.pos) < min_gap) {
ok = false;
break;
}
}
if (!ok) continue;
}
used_comp[r.comp_id] = true;
used_cell[r.cell] = true;
picked.push_back(r);
}
if ((int)picked.size() >= max(4, gate_budget / 3)) break;
}
if (picked.empty()) return;
sort(picked.begin(), picked.end(), [&](const Room& a, const Room& b) {
return a.pos < b.pos;
});
vector<Door> doors;
vector<Switch> switches;
vector<char> used_edge(edges.size(), false), selected_side(edges.size(), false);
vector<int> cur(active_bits, 0);
int low_bits = min(active_bits, 4 + (variant % 3));
auto choose_bit = [&](int t) {
int mode = (variant / 3) % 4;
if (mode == 0) return __builtin_ctz((unsigned)(t + 1)) % low_bits;
if (mode == 1) return __builtin_ctz((unsigned)((t + 1) ^ (t + 2))) % low_bits;
if (mode == 2) return (t + (t >> 1) + variant) % low_bits;
static const int seq[16] = {0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4};
return seq[t & 15] % low_bits;
};
int gates = 0;
for (int t = 0; t < (int)picked.size() && gates < gate_budget; t++) {
const Room& r = picked[t];
int gate_pos = r.pos;
if (gate_pos < 0 || gate_pos >= L) continue;
int bit = choose_bit(gates);
int target = cur[bit] ^ 1;
if (!add_unique_door(doors, used_edge, path[gate_pos].first, 2 * bit + target)) continue;
cur[bit] = target;
selected_side[r.first_eid] = true;
auto [si, sj] = pos(r.cell);
switches.push_back({si, sj, bit});
gates++;
}
if (gates < 3) return;
vector<int> wall_candidates = side_edges;
sort(wall_candidates.begin(), wall_candidates.end(), [&](int a, int b) {
int pa = min(path_idx[edges[a].u] == -1 ? 100000 : path_idx[edges[a].u],
path_idx[edges[a].v] == -1 ? 100000 : path_idx[edges[a].v]);
int pb = min(path_idx[edges[b].u] == -1 ? 100000 : path_idx[edges[b].u],
path_idx[edges[b].v] == -1 ? 100000 : path_idx[edges[b].v]);
int ca = abs(pa - L / 2);
int cb = abs(pb - L / 2);
if (ca != cb) return ca < cb;
return a < b;
});
for (int eid : wall_candidates) {
if ((int)doors.size() >= M) break;
if (selected_side[eid]) continue;
add_unique_door(doors, used_edge, eid, 2 * wall_bit + 1);
}
try_candidate(move(doors), move(switches), "counter_relay_hanoi");
}
void add_corridor_hanoi_candidate(const vector<pair<int, int>>& path, int variant) {
const int wall_bit = K - 1;
const int active_bits = K - 1;
if (active_bits <= 0 || path.empty()) return;
vector<int> pv = path_vertices_from_edges(path);
int L = (int)path.size();
if (L < 8) return;
vector<int> path_idx(N * N, -1), edge_pos(edges.size(), -1);
vector<char> on_path(N * N, false), used_edge(edges.size(), false);
for (int i = 0; i < (int)pv.size(); i++) {
path_idx[pv[i]] = i;
on_path[pv[i]] = true;
}
for (int i = 0; i < L; i++) edge_pos[path[i].first] = i;
struct Branch {
int pos, eid, cell, depth;
};
vector<Branch> branches;
vector<int> side_edges;
for (int idx = 0; idx < (int)pv.size(); idx++) {
int u = pv[idx];
for (auto [v, eid] : graph[u]) {
if (edge_pos[eid] != -1) continue;
side_edges.push_back(eid);
if (on_path[v]) continue;
int far = farthest_branch_cell(v, on_path);
auto bp = branch_path_avoiding_main(u, far, on_path);
if (bp.empty()) continue;
branches.push_back({idx, bp[0].first, far, (int)bp.size()});
}
}
sort(side_edges.begin(), side_edges.end());
side_edges.erase(unique(side_edges.begin(), side_edges.end()), side_edges.end());
if (branches.empty()) return;
int early_limit = max(2, L * (45 + (variant % 4) * 10) / 100);
sort(branches.begin(), branches.end(), [&](const Branch& a, const Branch& b) {
bool ae = a.pos <= early_limit;
bool be = b.pos <= early_limit;
if (ae != be) return ae > be;
if (a.depth != b.depth) return a.depth > b.depth;
return a.pos < b.pos;
});
vector<Door> doors;
vector<Switch> switches;
vector<char> selected_side(edges.size(), false);
vector<char> used_cell(N * N, false);
int sw_count = 0;
for (const auto& br : branches) {
if (sw_count >= active_bits) break;
if (used_cell[br.cell]) continue;
selected_side[br.eid] = true;
used_cell[br.cell] = true;
auto [i, j] = pos(br.cell);
switches.push_back({i, j, sw_count});
sw_count++;
}
for (; sw_count < active_bits; sw_count++) {
int idx = min((int)pv.size() - 2, 1 + sw_count * max(1, L / active_bits));
auto [i, j] = pos(pv[idx]);
if (used_cell[pv[idx]]) continue;
used_cell[pv[idx]] = true;
switches.push_back({i, j, sw_count});
}
int wall_budget = min((int)side_edges.size(), 18 + (variant % 5) * 6);
vector<int> wall_candidates = side_edges;
sort(wall_candidates.begin(), wall_candidates.end(), [&](int a, int b) {
int pa = min(path_idx[edges[a].u] == -1 ? 100000 : path_idx[edges[a].u],
path_idx[edges[a].v] == -1 ? 100000 : path_idx[edges[a].v]);
int pb = min(path_idx[edges[b].u] == -1 ? 100000 : path_idx[edges[b].u],
path_idx[edges[b].v] == -1 ? 100000 : path_idx[edges[b].v]);
int ca = abs(pa - L / 2);
int cb = abs(pb - L / 2);
if (ca != cb) return ca < cb;
return a < b;
});
int walls = 0;
for (int eid : wall_candidates) {
if (walls >= wall_budget) break;
if (selected_side[eid]) continue;
if (add_unique_door(doors, used_edge, eid, 2 * wall_bit + 1)) walls++;
}
int gate_budget = M - (int)doors.size();
if (gate_budget <= 0) {
try_candidate(move(doors), move(switches), "corridor_wall_only");
return;
}
int first_gate = max(1, L / 8);
int last_gate = max(first_gate + 1, L - 1);
for (int t = 0; t < gate_budget; t++) {
int pi = first_gate + (long long)(t + 1) * (last_gate - first_gate) / (gate_budget + 1);
pi = min(L - 1, max(0, pi));
int eid = path[pi].first;
int bit;
if (variant & 1) {
bit = __builtin_ctz((unsigned)(t + 1)) % active_bits;
} else if (variant & 2) {
bit = __builtin_ctz((unsigned)((t + 1) ^ (t + 2))) % active_bits;
} else {
bit = (t + (t >> 1) + variant) % active_bits;
}
int counter = t + 1 + (variant / 4);
int need = (counter >> bit) & 1;
if (variant & 8) need ^= (t & 1);
add_unique_door(doors, used_edge, eid, 2 * bit + need);
}
try_candidate(move(doors), move(switches), "corridor_hanoi");
}
void add_hanoi_role_candidates(const vector<int>& sorted_edges, const vector<int>& cell_heat, const vector<int>& dist0) {
const int wall_bit = K - 1;
const int bits = K - 1;
if (bits <= 0 || sorted_edges.empty()) return;
vector<int> open_cells;
for (int v = 0; v < N * N; v++) {
if (is_open_cell(v) && v != 0 && v != N * N - 1) open_cells.push_back(v);
}
sort(open_cells.begin(), open_cells.end(), [&](int a, int b) {
long long sa = 100LL * dist0[a] - 35LL * cell_heat[a];
long long sb = 100LL * dist0[b] - 35LL * cell_heat[b];
if (sa != sb) return sa > sb;
return a < b;
});
if ((int)open_cells.size() < bits) return;
vector<int> switch_cells(bits);
for (int k = 0; k < bits; k++) {
int idx = min((int)open_cells.size() - 1, k * max(1, (int)open_cells.size() / (bits + 3)));
switch_cells[k] = open_cells[idx];
}
vector<int> penalty(edges.size(), 0);
for (int variant = 0; variant < 16; variant++) {
for (int wall_count : {0, 6, 12, 20}) {
vector<Door> doors;
vector<Switch> switches;
vector<char> used_edge(edges.size(), false);
for (int k = 0; k < bits; k++) {
auto [i, j] = pos(switch_cells[k]);
switches.push_back({i, j, k});
}
for (int k = 1; k < bits; k++) {
auto path = shortest_path_between(0, switch_cells[k], &penalty);
int L = (int)path.size();
if (L == 0) continue;
for (int b = 0; b < k && (int)doors.size() < M; b++) {
int pi = min(L - 1, max(0, (int)((long long)(b + 1) * L / (k + 1))));
int need;
if (variant & 1) {
need = ((k >> b) & 1);
} else if (variant & 2) {
need = (((k + 1) ^ ((k + 1) >> 1)) >> b) & 1;
} else {
need = ((b + k + variant) & 1);
}
add_unique_door(doors, used_edge, path[pi].first, 2 * b + need);
}
}
auto goal_path = shortest_path_between(0, N * N - 1, &penalty);
int GL = (int)goal_path.size();
if (GL > 0) {
for (int b = 0; b < bits && (int)doors.size() < M; b++) {
int pi = min(GL - 1, max(0, (int)((long long)(b + 1) * GL / (bits + 1))));
int need = ((variant >> (b % 4)) & 1) ^ (b & 1);
add_unique_door(doors, used_edge, goal_path[pi].first, 2 * b + need);
}
}
int added_walls = 0;
for (int eid : sorted_edges) {
if ((int)doors.size() >= M || added_walls >= wall_count) break;
if (used_edge[eid]) continue;
add_unique_door(doors, used_edge, eid, 2 * wall_bit + 1);
added_walls++;
}
try_candidate(move(doors), move(switches), wall_count == 0 ? "hanoi_roles" : "hanoi_roles_wall");
}
for (int eid : sorted_edges) {
penalty[eid] += 1 + ((eid + 17 * variant) % 20);
}
}
}
void add_local_search_candidate(const vector<int>& sorted_edges, const vector<int>& cell_heat, const vector<int>& dist0, double limit, bool corridor_seed = false) {
if (corridor_seed && (best_corridor_doors.empty() || best_corridor_switches.empty())) return;
if (!corridor_seed && (best_doors.empty() || best_switches.empty())) return;
vector<int> open_cells;
open_cells.reserve(N * N);
for (int v = 0; v < N * N; v++) {
if (is_open_cell(v) && v != N * N - 1) open_cells.push_back(v);
}
sort(open_cells.begin(), open_cells.end(), [&](int a, int b) {
int sa = 8 * dist0[a] - cell_heat[a];
int sb = 8 * dist0[b] - cell_heat[b];
if (sa != sb) return sa > sb;
return a < b;
});
int edge_pool = min(140, (int)sorted_edges.size());
int cell_pool = min(140, (int)open_cells.size());
if (edge_pool == 0 || cell_pool == 0) return;
vector<Door> cur_d = corridor_seed ? best_corridor_doors : best_doors;
vector<Switch> cur_s = corridor_seed ? best_corridor_switches : best_switches;
int cur_T = corridor_seed ? best_corridor_T : best_T;
string local_name = corridor_seed ? "corridor_local" : "local_heatmap";
int iter = 0;
while (!timer.time_up(limit)) {
vector<Door> nd = cur_d;
vector<Switch> ns = cur_s;
int op = (int)(rng() % 6);
if (op == 0 && !nd.empty()) {
int x = (int)(rng() % nd.size());
nd[x].g = (int)(rng() % (2 * K));
} else if (op == 1 && !nd.empty()) {
int reps = 2 + (int)(rng() % 5);
while (reps--) {
int x = (int)(rng() % nd.size());
int k = (nd[x].g / 2 + 1 + (int)(rng() % (K - 1))) % K;
int p = nd[x].g & 1;
if (rng() & 1) p ^= 1;
nd[x].g = 2 * k + p;
}
} else if (op == 2 && !ns.empty()) {
int x = (int)(rng() % ns.size());
ns[x].k = (int)(rng() % K);
} else if (op == 3 && !ns.empty()) {
int x = (int)(rng() % ns.size());
int v = open_cells[(iter * 13 + (int)(rng() % cell_pool)) % cell_pool];
auto [i, j] = pos(v);
ns[x].i = i;
ns[x].j = j;
} else if (op == 4 && !nd.empty()) {
int x = (int)(rng() % nd.size());
int eid = sorted_edges[(iter * 7 + (int)(rng() % edge_pool)) % edge_pool];
const Edge& e = edges[eid];
nd[x].d = e.d;
nd[x].i = e.i;
nd[x].j = e.j;
if (has_duplicate_doors(nd)) continue;
} else if (op == 5) {
int reps = 1 + (int)(rng() % 4);
while (reps-- && !nd.empty()) {
int x = (int)(rng() % nd.size());
nd[x].g = (int)(rng() % (2 * K));
}
if (!ns.empty()) {
int x = (int)(rng() % ns.size());
int v = open_cells[(iter * 19 + (int)(rng() % cell_pool)) % cell_pool];
auto [i, j] = pos(v);
ns[x].i = i;
ns[x].j = j;
}
} else if (!ns.empty()) {
int x = (int)(rng() % ns.size());
int v = open_cells[(iter * 19 + (int)(rng() % cell_pool)) % cell_pool];
auto [i, j] = pos(v);
ns[x].i = i;
ns[x].j = j;
}
normalize_switches(ns);
int nt = calc_T(nd, ns);
double progress = min(1.0, timer.elapsed() / max(0.001, limit));
double temp = 10.0 * (1.0 - progress) + 1.0;
bool accept = nt >= cur_T;
if (!accept) {
double p = exp((double)(nt - cur_T) / temp);
accept = (double)(rng() % 1000000) < p * 1000000.0;
}
if (accept) {
cur_T = nt;
cur_d.swap(nd);
cur_s.swap(ns);
try_candidate(cur_d, cur_s, local_name);
}
iter++;
}
}
void add_heatmap_candidates() {
vector<int> edge_heat(edges.size(), 0), cell_heat(N * N, 0), penalty(edges.size(), 0);
int samples = 0;
while (samples < 260 && !timer.time_up(0.55)) {
auto path = shortest_path_edges_noisy(160, &penalty);
if (path.empty()) break;
cell_heat[0]++;
for (auto [eid, from] : path) {
edge_heat[eid]++;
cell_heat[from]++;
penalty[eid] += 18;
const Edge& e = edges[eid];
int to = e.u ^ e.v ^ from;
cell_heat[to]++;
}
samples++;
}
vector<int> sorted_edges;
for (int eid = 0; eid < (int)edges.size(); eid++) {
if (edge_heat[eid] > 0) sorted_edges.push_back(eid);
}
sort(sorted_edges.begin(), sorted_edges.end(), [&](int a, int b) {
if (edge_heat[a] != edge_heat[b]) return edge_heat[a] > edge_heat[b];
return a < b;
});
if (sorted_edges.empty()) return;
auto dist0 = bfs_dist(0);
int pool = min(90, (int)sorted_edges.size());
add_heatmap_distinct_candidate(sorted_edges, cell_heat, dist0, min(25, pool), 0);
add_heatmap_distinct_candidate(sorted_edges, cell_heat, dist0, pool, 0);
add_heatmap_distinct_candidate(sorted_edges, cell_heat, dist0, pool, min(8, max(0, pool - 1)));
add_heatmap_alternating_candidate(sorted_edges, cell_heat, dist0, 20, pool);
add_heatmap_alternating_candidate(sorted_edges, cell_heat, dist0, 50, pool);
add_hanoi_role_candidates(sorted_edges, cell_heat, dist0);
add_heatmap_random_type_candidates(sorted_edges, cell_heat, dist0, 1.08);
add_local_search_candidate(sorted_edges, cell_heat, dist0, 1.42, true);
add_local_search_candidate(sorted_edges, cell_heat, dist0, 1.86, false);
}
void init() {
build_graph();
best_T = shortest_without_doors();
best_corridor_T = 0;
score = calc_score_from_T(best_T);
best_doors.clear();
best_switches.clear();
best_corridor_doors.clear();
best_corridor_switches.clear();
}
void improve() {
try_candidate({}, {});
auto bridges = bridge_path_edges();
if (!bridges.empty()) {
add_alternating_path_candidate(bridges, 0, 1, 0);
add_alternating_path_candidate(bridges, 1, 1, 0);
add_alternating_path_candidate(bridges, 2, 1, 0);
add_distinct_bridge_detour_candidate(bridges);
add_alternating_bridge_detour_candidate(bridges);
for (int shift = 0; shift < 16; shift++) add_gray_bridge_candidate(bridges, shift);
}
auto base_path = shortest_path_edges_random(false);
for (int variant = 0; variant < 8; variant++) add_prefix_ladder_counter_candidate(base_path, variant);
// スイッチ分散版を試す場合は以下を有効化する。
// for (int variant = 0; variant < 4; variant++) add_prefix_ladder_counter_candidate(base_path, 256 + 16 + variant);
for (int variant = 0; variant < 8; variant++) add_full_counter_chain_candidate(base_path, variant);
for (int variant = 0; variant < 8; variant++) add_nested_switch_chain_candidate(base_path, variant);
add_counter_relay_hanoi_candidate(base_path, 0);
for (int variant = 0; variant < 24; variant++) add_switch_room_hanoi_candidate(base_path, variant);
for (int variant = 0; variant < 16; variant++) add_corridor_hanoi_candidate(base_path, variant);
for (int p = 0; p < 5; p++) {
auto cpath = corridor_path(180 + p * 90, p * 17);
for (int variant = 0; variant < 4; variant++) add_prefix_ladder_counter_candidate(cpath, 32 + p * 8 + variant);
for (int variant = 0; variant < 5; variant++) add_full_counter_chain_candidate(cpath, 32 + p * 8 + variant);
for (int variant = 0; variant < 6; variant++) add_nested_switch_chain_candidate(cpath, 32 + p * 8 + variant);
if (p < 3) add_counter_relay_hanoi_candidate(cpath, 16 + p);
for (int variant = 0; variant < 16; variant++) add_switch_room_hanoi_candidate(cpath, 64 + p * 16 + variant);
for (int variant = 0; variant < 12; variant++) add_corridor_hanoi_candidate(cpath, 64 + p * 12 + variant);
}
for (int r = 0; r < 8; r++) {
auto path = shortest_path_edges_random(true);
if (r < 4) add_prefix_ladder_counter_candidate(path, 96 + r);
if (r < 5) add_full_counter_chain_candidate(path, 96 + r);
if (r < 5) add_nested_switch_chain_candidate(path, 96 + r);
for (int variant = 0; variant < 4; variant++) add_switch_room_hanoi_candidate(path, 160 + r * 4 + variant);
for (int variant = 0; variant < 4; variant++) add_corridor_hanoi_candidate(path, 16 + r * 4 + variant);
}
for (int mode = 0; mode < 3; mode++) add_alternating_path_candidate(base_path, mode, 1, 0);
for (int stride = 2; stride <= 6; stride++) {
for (int offset = 0; offset < stride; offset++) {
add_alternating_path_candidate(base_path, 3, stride, offset);
}
}
add_heatmap_candidates();
for (int variant = 0; variant < 8; variant++) add_double_prefix_ladder_candidate(base_path, variant);
int loops = 0;
while (!timer.time_up(1.88)) {
auto path = shortest_path_edges_random(true);
if (!path.empty()) {
add_alternating_path_candidate(path, loops % 3, 1, 0);
int stride = 1 + (int)(rng() % 6);
int offset = (int)(rng() % stride);
add_alternating_path_candidate(path, 3, stride, offset);
}
loops++;
}
TraceInfo final_trace = calc_trace(best_doors, best_switches);
cerr << "BestT: " << best_T << '\n';
cerr << "BestStrategy: " << best_strategy << '\n';
cerr << "Press:";
for (int k = 0; k < K; k++) cerr << ' ' << final_trace.press_count[k];
cerr << '\n';
}
void output() const {
cout << best_doors.size() << '\n';
for (const auto& e : best_doors) {
cout << e.d << ' ' << e.i << ' ' << e.j << ' ' << e.g << '\n';
}
cout << best_switches.size() << '\n';
for (const auto& s : best_switches) {
cout << s.i << ' ' << s.j << ' ' << s.k << '\n';
}
}
void solve() {
input();
init();
improve();
output();
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
// 再現性を優先する場合は固定 seed のままにする。
// 提出時にランダム化したい場合だけ以下を有効化する。
// rng.seed(chrono::steady_clock::now().time_since_epoch().count());
Solver solver;
solver.solve();
cerr << "Score = " << solver.score << '\n';
return 0;
}
提出情報
ジャッジ結果
| セット名 |
test_ALL |
| 得点 / 配点 |
1044166544 / 3000000000 |
| 結果 |
|
| セット名 |
テストケース |
| test_ALL |
test_0000.txt, test_0001.txt, test_0002.txt, test_0003.txt, test_0004.txt, test_0005.txt, test_0006.txt, test_0007.txt, test_0008.txt, test_0009.txt, test_0010.txt, test_0011.txt, test_0012.txt, test_0013.txt, test_0014.txt, test_0015.txt, test_0016.txt, test_0017.txt, test_0018.txt, test_0019.txt, test_0020.txt, test_0021.txt, test_0022.txt, test_0023.txt, test_0024.txt, test_0025.txt, test_0026.txt, test_0027.txt, test_0028.txt, test_0029.txt, test_0030.txt, test_0031.txt, test_0032.txt, test_0033.txt, test_0034.txt, test_0035.txt, test_0036.txt, test_0037.txt, test_0038.txt, test_0039.txt, test_0040.txt, test_0041.txt, test_0042.txt, test_0043.txt, test_0044.txt, test_0045.txt, test_0046.txt, test_0047.txt, test_0048.txt, test_0049.txt, test_0050.txt, test_0051.txt, test_0052.txt, test_0053.txt, test_0054.txt, test_0055.txt, test_0056.txt, test_0057.txt, test_0058.txt, test_0059.txt, test_0060.txt, test_0061.txt, test_0062.txt, test_0063.txt, test_0064.txt, test_0065.txt, test_0066.txt, test_0067.txt, test_0068.txt, test_0069.txt, test_0070.txt, test_0071.txt, test_0072.txt, test_0073.txt, test_0074.txt, test_0075.txt, test_0076.txt, test_0077.txt, test_0078.txt, test_0079.txt, test_0080.txt, test_0081.txt, test_0082.txt, test_0083.txt, test_0084.txt, test_0085.txt, test_0086.txt, test_0087.txt, test_0088.txt, test_0089.txt, test_0090.txt, test_0091.txt, test_0092.txt, test_0093.txt, test_0094.txt, test_0095.txt, test_0096.txt, test_0097.txt, test_0098.txt, test_0099.txt, test_0100.txt, test_0101.txt, test_0102.txt, test_0103.txt, test_0104.txt, test_0105.txt, test_0106.txt, test_0107.txt, test_0108.txt, test_0109.txt, test_0110.txt, test_0111.txt, test_0112.txt, test_0113.txt, test_0114.txt, test_0115.txt, test_0116.txt, test_0117.txt, test_0118.txt, test_0119.txt, test_0120.txt, test_0121.txt, test_0122.txt, test_0123.txt, test_0124.txt, test_0125.txt, test_0126.txt, test_0127.txt, test_0128.txt, test_0129.txt, test_0130.txt, test_0131.txt, test_0132.txt, test_0133.txt, test_0134.txt, test_0135.txt, test_0136.txt, test_0137.txt, test_0138.txt, test_0139.txt, test_0140.txt, test_0141.txt, test_0142.txt, test_0143.txt, test_0144.txt, test_0145.txt, test_0146.txt, test_0147.txt, test_0148.txt, test_0149.txt |
| ケース名 |
結果 |
実行時間 |
メモリ |
| test_0000.txt |
AC |
1882 ms |
7768 KiB |
| test_0001.txt |
AC |
1883 ms |
8564 KiB |
| test_0002.txt |
AC |
1882 ms |
8496 KiB |
| test_0003.txt |
AC |
1882 ms |
7972 KiB |
| test_0004.txt |
AC |
1883 ms |
8560 KiB |
| test_0005.txt |
AC |
1882 ms |
8052 KiB |
| test_0006.txt |
AC |
1882 ms |
8560 KiB |
| test_0007.txt |
AC |
1882 ms |
7812 KiB |
| test_0008.txt |
AC |
1882 ms |
7804 KiB |
| test_0009.txt |
AC |
1883 ms |
8560 KiB |
| test_0010.txt |
AC |
1882 ms |
8556 KiB |
| test_0011.txt |
AC |
1883 ms |
8076 KiB |
| test_0012.txt |
AC |
1882 ms |
8616 KiB |
| test_0013.txt |
AC |
1882 ms |
8480 KiB |
| test_0014.txt |
AC |
1882 ms |
7824 KiB |
| test_0015.txt |
AC |
1883 ms |
7724 KiB |
| test_0016.txt |
AC |
1882 ms |
8588 KiB |
| test_0017.txt |
AC |
1882 ms |
8592 KiB |
| test_0018.txt |
AC |
1882 ms |
7840 KiB |
| test_0019.txt |
AC |
1882 ms |
8484 KiB |
| test_0020.txt |
AC |
1883 ms |
8448 KiB |
| test_0021.txt |
AC |
1883 ms |
8504 KiB |
| test_0022.txt |
AC |
1882 ms |
8508 KiB |
| test_0023.txt |
AC |
1884 ms |
8456 KiB |
| test_0024.txt |
AC |
1882 ms |
8496 KiB |
| test_0025.txt |
AC |
1882 ms |
8464 KiB |
| test_0026.txt |
AC |
1882 ms |
8516 KiB |
| test_0027.txt |
AC |
1883 ms |
8616 KiB |
| test_0028.txt |
AC |
1882 ms |
8528 KiB |
| test_0029.txt |
AC |
1882 ms |
8596 KiB |
| test_0030.txt |
AC |
1883 ms |
8648 KiB |
| test_0031.txt |
AC |
1882 ms |
7812 KiB |
| test_0032.txt |
AC |
1883 ms |
8612 KiB |
| test_0033.txt |
AC |
1883 ms |
7856 KiB |
| test_0034.txt |
AC |
1882 ms |
8640 KiB |
| test_0035.txt |
AC |
1882 ms |
8616 KiB |
| test_0036.txt |
AC |
1883 ms |
8568 KiB |
| test_0037.txt |
AC |
1882 ms |
8556 KiB |
| test_0038.txt |
AC |
1882 ms |
8616 KiB |
| test_0039.txt |
AC |
1882 ms |
8068 KiB |
| test_0040.txt |
AC |
1882 ms |
8564 KiB |
| test_0041.txt |
AC |
1883 ms |
7848 KiB |
| test_0042.txt |
AC |
1883 ms |
8060 KiB |
| test_0043.txt |
AC |
1883 ms |
8064 KiB |
| test_0044.txt |
AC |
1882 ms |
7832 KiB |
| test_0045.txt |
AC |
1882 ms |
8500 KiB |
| test_0046.txt |
AC |
1882 ms |
8536 KiB |
| test_0047.txt |
AC |
1882 ms |
8588 KiB |
| test_0048.txt |
AC |
1883 ms |
8576 KiB |
| test_0049.txt |
AC |
1882 ms |
8524 KiB |
| test_0050.txt |
AC |
1883 ms |
7688 KiB |
| test_0051.txt |
AC |
1882 ms |
8636 KiB |
| test_0052.txt |
AC |
1883 ms |
8600 KiB |
| test_0053.txt |
AC |
1882 ms |
8080 KiB |
| test_0054.txt |
AC |
1882 ms |
7884 KiB |
| test_0055.txt |
AC |
1883 ms |
8524 KiB |
| test_0056.txt |
AC |
1882 ms |
8468 KiB |
| test_0057.txt |
AC |
1882 ms |
8620 KiB |
| test_0058.txt |
AC |
1882 ms |
8560 KiB |
| test_0059.txt |
AC |
1883 ms |
8536 KiB |
| test_0060.txt |
AC |
1882 ms |
8596 KiB |
| test_0061.txt |
AC |
1882 ms |
8656 KiB |
| test_0062.txt |
AC |
1882 ms |
7944 KiB |
| test_0063.txt |
AC |
1882 ms |
8112 KiB |
| test_0064.txt |
AC |
1882 ms |
8108 KiB |
| test_0065.txt |
AC |
1882 ms |
8480 KiB |
| test_0066.txt |
AC |
1882 ms |
8512 KiB |
| test_0067.txt |
AC |
1883 ms |
8472 KiB |
| test_0068.txt |
AC |
1882 ms |
7896 KiB |
| test_0069.txt |
AC |
1882 ms |
8596 KiB |
| test_0070.txt |
AC |
1882 ms |
8532 KiB |
| test_0071.txt |
AC |
1882 ms |
8428 KiB |
| test_0072.txt |
AC |
1882 ms |
8484 KiB |
| test_0073.txt |
AC |
1882 ms |
8564 KiB |
| test_0074.txt |
AC |
1882 ms |
8452 KiB |
| test_0075.txt |
AC |
1883 ms |
8404 KiB |
| test_0076.txt |
AC |
1882 ms |
8480 KiB |
| test_0077.txt |
AC |
1882 ms |
7808 KiB |
| test_0078.txt |
AC |
1882 ms |
8512 KiB |
| test_0079.txt |
AC |
1882 ms |
8560 KiB |
| test_0080.txt |
AC |
1882 ms |
7772 KiB |
| test_0081.txt |
AC |
1882 ms |
8500 KiB |
| test_0082.txt |
AC |
1882 ms |
7936 KiB |
| test_0083.txt |
AC |
1882 ms |
8064 KiB |
| test_0084.txt |
AC |
1883 ms |
8468 KiB |
| test_0085.txt |
AC |
1882 ms |
8528 KiB |
| test_0086.txt |
AC |
1882 ms |
8600 KiB |
| test_0087.txt |
AC |
1882 ms |
8544 KiB |
| test_0088.txt |
AC |
1882 ms |
8528 KiB |
| test_0089.txt |
AC |
1882 ms |
8564 KiB |
| test_0090.txt |
AC |
1882 ms |
8420 KiB |
| test_0091.txt |
AC |
1882 ms |
8572 KiB |
| test_0092.txt |
AC |
1882 ms |
8636 KiB |
| test_0093.txt |
AC |
1882 ms |
8620 KiB |
| test_0094.txt |
AC |
1882 ms |
8620 KiB |
| test_0095.txt |
AC |
1883 ms |
8500 KiB |
| test_0096.txt |
AC |
1883 ms |
7892 KiB |
| test_0097.txt |
AC |
1882 ms |
8560 KiB |
| test_0098.txt |
AC |
1882 ms |
7904 KiB |
| test_0099.txt |
AC |
1883 ms |
7892 KiB |
| test_0100.txt |
AC |
1882 ms |
8564 KiB |
| test_0101.txt |
AC |
1882 ms |
8500 KiB |
| test_0102.txt |
AC |
1882 ms |
8524 KiB |
| test_0103.txt |
AC |
1882 ms |
8556 KiB |
| test_0104.txt |
AC |
1883 ms |
8568 KiB |
| test_0105.txt |
AC |
1882 ms |
8528 KiB |
| test_0106.txt |
AC |
1882 ms |
8512 KiB |
| test_0107.txt |
AC |
1882 ms |
8588 KiB |
| test_0108.txt |
AC |
1883 ms |
8476 KiB |
| test_0109.txt |
AC |
1882 ms |
8564 KiB |
| test_0110.txt |
AC |
1882 ms |
8448 KiB |
| test_0111.txt |
AC |
1882 ms |
7940 KiB |
| test_0112.txt |
AC |
1882 ms |
8064 KiB |
| test_0113.txt |
AC |
1882 ms |
8556 KiB |
| test_0114.txt |
AC |
1882 ms |
8508 KiB |
| test_0115.txt |
AC |
1882 ms |
8504 KiB |
| test_0116.txt |
AC |
1882 ms |
8528 KiB |
| test_0117.txt |
AC |
1883 ms |
8560 KiB |
| test_0118.txt |
AC |
1882 ms |
8532 KiB |
| test_0119.txt |
AC |
1882 ms |
8540 KiB |
| test_0120.txt |
AC |
1882 ms |
7696 KiB |
| test_0121.txt |
AC |
1882 ms |
8536 KiB |
| test_0122.txt |
AC |
1883 ms |
8584 KiB |
| test_0123.txt |
AC |
1882 ms |
8640 KiB |
| test_0124.txt |
AC |
1882 ms |
8472 KiB |
| test_0125.txt |
AC |
1882 ms |
8548 KiB |
| test_0126.txt |
AC |
1883 ms |
8576 KiB |
| test_0127.txt |
AC |
1882 ms |
8548 KiB |
| test_0128.txt |
AC |
1882 ms |
8568 KiB |
| test_0129.txt |
AC |
1883 ms |
8508 KiB |
| test_0130.txt |
AC |
1882 ms |
8556 KiB |
| test_0131.txt |
AC |
1882 ms |
8568 KiB |
| test_0132.txt |
AC |
1882 ms |
8016 KiB |
| test_0133.txt |
AC |
1883 ms |
8528 KiB |
| test_0134.txt |
AC |
1882 ms |
8512 KiB |
| test_0135.txt |
AC |
1882 ms |
7836 KiB |
| test_0136.txt |
AC |
1882 ms |
8528 KiB |
| test_0137.txt |
AC |
1882 ms |
7956 KiB |
| test_0138.txt |
AC |
1882 ms |
8492 KiB |
| test_0139.txt |
AC |
1882 ms |
8528 KiB |
| test_0140.txt |
AC |
1882 ms |
8528 KiB |
| test_0141.txt |
AC |
1882 ms |
8564 KiB |
| test_0142.txt |
AC |
1882 ms |
7784 KiB |
| test_0143.txt |
AC |
1883 ms |
7652 KiB |
| test_0144.txt |
AC |
1882 ms |
8504 KiB |
| test_0145.txt |
AC |
1882 ms |
8480 KiB |
| test_0146.txt |
AC |
1882 ms |
8536 KiB |
| test_0147.txt |
AC |
1882 ms |
8540 KiB |
| test_0148.txt |
AC |
1882 ms |
8048 KiB |
| test_0149.txt |
AC |
1882 ms |
8536 KiB |