結果
| 問題 | No.5023 Airlines Optimization |
| コンテスト | |
| ユーザー |
 てんぷら
|
| 提出日時 | 2026-02-26 01:04:45 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 29,198 bytes |
| 記録 | |
| コンパイル時間 | 8,357 ms |
| コンパイル使用メモリ | 359,256 KB |
| 実行使用メモリ | 23,320 KB |
| スコア | 53,079,487 |
| 最終ジャッジ日時 | 2026-02-26 01:06:38 |
| 合計ジャッジ時間 | 110,958 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 87 TLE * 13 |
ソースコード
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <algorithm>
#include <array>
#include <chrono>
#include <cmath>
#include <cstdint>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <random>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;
using ll = long long;
struct City {
int x, y;
ll w;
};
struct Flight {
int a, b;
int s, t;
};
struct PlanePlan {
vector<int> route;
int offset = 0;
int duration = 0;
};
struct DemandTerm {
int src, dst;
long double w;
array<int, 21> sq;
};
constexpr int START_HOUR = 6;
constexpr int END_HOUR = 21;
constexpr int SLOT_MIN = 5;
constexpr int MAX_SLOT = (END_HOUR - START_HOUR) * 60 / SLOT_MIN; // 180
constexpr int TARGET_CNT = 21;
constexpr int TARGET_START = (11 - START_HOUR) * 60 / SLOT_MIN; // 60
constexpr int TARGET_STEP = 30 / SLOT_MIN; // 6
constexpr int NEG_INF = -1e9;
int parseTimeToSlot(const string &s) {
auto pos = s.find(':');
int hh = stoi(s.substr(0, pos));
int mm = stoi(s.substr(pos + 1));
return (hh * 60 + mm - START_HOUR * 60) / SLOT_MIN;
}
string slotToTime(int slot) {
int total = START_HOUR * 60 + slot * SLOT_MIN;
int hh = total / 60;
int mm = total % 60;
char buf[16];
snprintf(buf, sizeof(buf), "%02d:%02d", hh, mm);
return string(buf);
}
int calcDurationSlot(const City &c1, const City &c2) {
double dx = double(c1.x) - double(c2.x);
double dy = double(c1.y) - double(c2.y);
double d = sqrt(dx * dx + dy * dy);
double minutes = 60.0 * d / 800.0 + 40.0;
return (int)ceil(minutes / 5.0 - 1e-12);
}
int routeDuration(const vector<int> &route, const vector<vector<int>> &dur) {
int total = 0;
for(int i = 1; i < (int)route.size(); ++i) {
if(route[i - 1] == route[i])
return MAX_SLOT + 1;
total += dur[route[i - 1]][route[i]];
if(total > MAX_SLOT)
return total;
}
return total;
}
void normalizePlane(PlanePlan &p, const vector<vector<int>> &dur) {
if(p.route.empty())
p.route.push_back(0);
vector<int> fixed;
fixed.reserve(p.route.size());
fixed.push_back(p.route[0]);
for(int i = 1; i < (int)p.route.size(); ++i) {
if(p.route[i] != p.route[i - 1])
fixed.push_back(p.route[i]);
}
p.route.swap(fixed);
if(p.route.empty())
p.route.push_back(0);
p.duration = routeDuration(p.route, dur);
while(p.duration > MAX_SLOT && (int)p.route.size() > 1) {
p.route.pop_back();
p.duration = routeDuration(p.route, dur);
}
int lim = max(0, MAX_SLOT - p.duration);
p.offset = min(max(0, p.offset), lim);
}
void appendPlaneFlights(const PlanePlan &p, const vector<vector<int>> &dur, vector<Flight> &out) {
int tm = p.offset;
for(int i = 1; i < (int)p.route.size(); ++i) {
int a = p.route[i - 1];
int b = p.route[i];
int nt = tm + dur[a][b];
out.push_back({a, b, tm, nt});
tm = nt;
}
}
vector<Flight> flattenPlans(const vector<PlanePlan> &plans, const vector<vector<int>> &dur) {
vector<Flight> flights;
for(const auto &p : plans)
appendPlaneFlights(p, dur, flights);
return flights;
}
struct ScoreEvaluator {
int N;
uint64_t allMask;
explicit ScoreEvaluator(int n) : N(n) {
allMask = (N == 64 ? ~0ULL : ((1ULL << N) - 1));
}
vector<vector<Flight>> buildByStart(const vector<Flight> &flights, int target) const {
vector<vector<Flight>> byStart(target + 1);
for(const auto &f : flights) {
if(f.s < 0 || f.s > target || f.t < 0 || f.t > target)
continue;
byStart[f.s].push_back(f);
}
return byStart;
}
vector<vector<int>> latestMatrixForTarget(const vector<vector<Flight>> &byStart, int target) const {
vector<vector<uint64_t>> reach(target + 1, vector<uint64_t>(N, 0ULL));
for(int c = 0; c < N; ++c)
reach[target][c] = (1ULL << c);
for(int tm = target - 1; tm >= 0; --tm) {
for(int c = 0; c < N; ++c)
reach[tm][c] = reach[tm + 1][c];
for(const auto &f : byStart[tm]) {
reach[tm][f.a] |= reach[f.t][f.b];
}
}
vector<vector<int>> latest(N, vector<int>(N, NEG_INF));
for(int src = 0; src < N; ++src) {
uint64_t rem = allMask;
for(int tm = target; tm >= 0 && rem; --tm) {
uint64_t m = reach[tm][src] & rem;
while(m) {
int dst = __builtin_ctzll(m);
latest[src][dst] = tm;
rem &= ~(1ULL << dst);
m &= (m - 1);
}
}
}
return latest;
}
vector<vector<vector<int>>> precomputeSqBest(const vector<Flight> &sqFlights) const {
vector<vector<vector<int>>> sqBest(TARGET_CNT, vector<vector<int>>(N, vector<int>(N, NEG_INF)));
for(int k = 0; k < TARGET_CNT; ++k) {
int target = TARGET_START + TARGET_STEP * k;
auto byStart = buildByStart(sqFlights, target);
sqBest[k] = latestMatrixForTarget(byStart, target);
}
return sqBest;
}
vector<vector<vector<int>>> precomputeAllLatest(const vector<Flight> &flights) const {
vector<vector<Flight>> allByStart(MAX_SLOT + 1);
for(const auto &f : flights) {
if(0 <= f.s && f.s <= MAX_SLOT && 0 <= f.t && f.t <= MAX_SLOT)
allByStart[f.s].push_back(f);
}
vector<vector<vector<int>>> allLatest(MAX_SLOT + 1, vector<vector<int>>(N, vector<int>(N, NEG_INF)));
for(int deadline = 0; deadline <= MAX_SLOT; ++deadline) {
vector<vector<uint64_t>> reach(deadline + 1, vector<uint64_t>(N, 0ULL));
for(int c = 0; c < N; ++c)
reach[deadline][c] = (1ULL << c);
for(int tm = deadline - 1; tm >= 0; --tm) {
for(int c = 0; c < N; ++c)
reach[tm][c] = reach[tm + 1][c];
for(const auto &f : allByStart[tm]) {
if(f.t <= deadline)
reach[tm][f.a] |= reach[f.t][f.b];
}
}
for(int src = 0; src < N; ++src) {
uint64_t rem = allMask;
for(int tm = deadline; tm >= 0 && rem; --tm) {
uint64_t m = reach[tm][src] & rem;
while(m) {
int dst = __builtin_ctzll(m);
allLatest[deadline][src][dst] = tm;
rem &= ~(1ULL << dst);
m &= (m - 1);
}
}
}
}
return allLatest;
}
double score(
const vector<Flight> &ciFlights,
const vector<DemandTerm> &demands) const {
long double vSq = 0.0L, vCi = 0.0L;
for(int k = 0; k < TARGET_CNT; ++k) {
int target = TARGET_START + TARGET_STEP * k;
auto byStart = buildByStart(ciFlights, target);
auto latest = latestMatrixForTarget(byStart, target);
for(const auto &d : demands) {
if(d.sq[k] < latest[d.src][d.dst])
vCi += d.w;
else
vSq += d.w;
}
}
long double den = vSq + vCi;
if(den <= 0.0L)
return 0.0;
return (double)(vCi / den);
}
};
PlanePlan buildCyclicPlan(
const vector<int> &cycle,
int offset,
const vector<vector<int>> &dur) {
PlanePlan p;
if(cycle.empty())
return p;
p.route.push_back(cycle[0]);
p.offset = offset;
int tm = offset;
int cur = cycle[0];
int idx = 1 % (int)cycle.size();
while(true) {
int nxt = cycle[idx];
if(nxt == cur)
break;
int nt = tm + dur[cur][nxt];
if(nt > MAX_SLOT)
break;
p.route.push_back(nxt);
tm = nt;
cur = nxt;
idx = (idx + 1) % (int)cycle.size();
}
p.duration = tm - offset;
normalizePlane(p, dur);
return p;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, R;
cin >> N >> R;
vector<City> cities(N);
for(int i = 0; i < N; ++i)
cin >> cities[i].x >> cities[i].y >> cities[i].w;
int M;
cin >> M;
vector<Flight> sqFlights(M);
for(int i = 0; i < M; ++i) {
int a, b;
string ss, tt;
cin >> a >> ss >> b >> tt;
--a;
--b;
sqFlights[i] = {a, b, parseTimeToSlot(ss), parseTimeToSlot(tt)};
}
int K;
cin >> K;
vector<vector<int>> dur(N, vector<int>(N, 0));
for(int i = 0; i < N; ++i) {
for(int j = 0; j < N; ++j)
if(i != j)
dur[i][j] = calcDurationSlot(cities[i], cities[j]);
}
vector<vector<long double>> pairWeight(N, vector<long double>(N, 0.0L));
double threshold = 0.25 * R;
for(int i = 0; i < N; ++i) {
for(int j = 0; j < N; ++j) {
double dx = double(cities[i].x) - double(cities[j].x);
double dy = double(cities[i].y) - double(cities[j].y);
double d = sqrt(dx * dx + dy * dy);
if(d + 1e-12 >= threshold) {
pairWeight[i][j] = (long double)cities[i].w * (long double)cities[j].w;
}
}
}
ScoreEvaluator evaluator(N);
auto sqBest = evaluator.precomputeSqBest(sqFlights); // [k][src][dst]
vector<DemandTerm> demands;
demands.reserve(N * N);
for(int src = 0; src < N; ++src) {
for(int dst = 0; dst < N; ++dst) {
if(pairWeight[src][dst] == 0.0L)
continue;
DemandTerm d;
d.src = src;
d.dst = dst;
d.w = pairWeight[src][dst];
for(int k = 0; k < TARGET_CNT; ++k)
d.sq[k] = sqBest[k][src][dst];
demands.push_back(d);
}
}
vector<vector<int>> demandId(N, vector<int>(N, -1));
for(int i = 0; i < (int)demands.size(); ++i)
demandId[demands[i].src][demands[i].dst] = i;
vector<long double> cityScore(N, 0.0L);
for(int i = 0; i < N; ++i) {
long double s = (long double)cities[i].w * 1e6L;
for(int j = 0; j < N; ++j)
s += pairWeight[i][j] + pairWeight[j][i];
cityScore[i] = max((long double)1.0, s);
}
vector<int> cityOrd(N);
iota(cityOrd.begin(), cityOrd.end(), 0);
sort(cityOrd.begin(), cityOrd.end(), [&](int a, int b) {
return cityScore[a] > cityScore[b];
});
long double totalDen = 0.0L;
for(const auto &d : demands)
totalDen += d.w;
totalDen *= (long double)TARGET_CNT;
double bestScoreAll = -1.0;
int bestTrial = -1;
vector<vector<Flight>> bestPlaneFlights;
auto baseLatestAll = evaluator.precomputeAllLatest({});
mt19937_64 rng(123456789ULL);
const double TL = 0.85;
const int maxLegPerPlane = 14;
auto begin = chrono::steady_clock::now();
auto makeSeedOrder = [&](int token) {
vector<int> seedOrder = cityOrd;
int mode = token % 4;
if(mode == 0) {
int shift = (token * 7) % N;
rotate(seedOrder.begin(), seedOrder.begin() + shift, seedOrder.end());
} else if(mode == 1) {
reverse(seedOrder.begin(), seedOrder.end());
int shift = (token * 5) % N;
rotate(seedOrder.begin(), seedOrder.begin() + shift, seedOrder.end());
} else if(mode == 2) {
int top = min(N, max(12, K * 2));
shuffle(seedOrder.begin(), seedOrder.begin() + top, rng);
int shift = (int)(rng() % N);
rotate(seedOrder.begin(), seedOrder.begin() + shift, seedOrder.end());
} else {
int top = min(N, max(20, K * 3));
shuffle(seedOrder.begin(), seedOrder.begin() + top, rng);
int rest = min(N, top + 10);
if(top < rest)
shuffle(seedOrder.begin() + top, seedOrder.begin() + rest, rng);
int shift = (int)(rng() % N);
rotate(seedOrder.begin(), seedOrder.begin() + shift, seedOrder.end());
}
return seedOrder;
};
auto flattenPlaneFlights = [&](const vector<vector<Flight>> &pf) {
vector<Flight> flights;
for(const auto &v : pf)
flights.insert(flights.end(), v.begin(), v.end());
return flights;
};
auto applyFlightToLatestAll = [&](vector<vector<vector<int>>> &latestAll, int a, int b, int dep, int arr) {
const auto &depMat = latestAll[dep];
for(int target = arr; target <= MAX_SLOT; ++target) {
auto &targetMat = latestAll[target];
array<int, 47> dstList{};
int dstCnt = 0;
for(int dst = 0; dst < N; ++dst) {
if(targetMat[b][dst] >= arr)
dstList[dstCnt++] = dst;
}
if(dstCnt == 0)
continue;
for(int src = 0; src < N; ++src) {
int pre = depMat[src][a];
if(pre == NEG_INF)
continue;
for(int i = 0; i < dstCnt; ++i) {
int dst = dstList[i];
if(pre > targetMat[src][dst])
targetMat[src][dst] = pre;
}
}
}
};
auto calcCiFromLatest = [&](const vector<vector<vector<int>>> &latestAll) {
long double ci = 0.0L;
for(int k = 0; k < TARGET_CNT; ++k) {
int target = TARGET_START + TARGET_STEP * k;
for(const auto &d : demands) {
if(d.sq[k] < latestAll[target][d.src][d.dst])
ci += d.w;
}
}
return ci;
};
auto calcDeltaCiEdge = [&](int a, int b, int dep, int arr, const vector<vector<vector<int>>> &latestAll) {
long double deltaCi = 0.0L;
const auto &depMat = latestAll[dep];
array<int, 47> preBySrc{};
array<int, 47> activeSrc{};
int activeSrcCnt = 0;
for(int src = 0; src < N; ++src)
if((preBySrc[src] = depMat[src][a]) != NEG_INF)
activeSrc[activeSrcCnt++] = src;
if(activeSrcCnt == 0)
return 0.0L;
int startK = 0;
if(arr > TARGET_START) {
startK = (arr - TARGET_START + TARGET_STEP - 1) / TARGET_STEP;
if(startK < 0)
startK = 0;
if(startK > TARGET_CNT)
startK = TARGET_CNT;
}
array<array<int, 47>, TARGET_CNT> addDst{};
array<int, TARGET_CNT> addCnt{};
for(int dst = 0; dst < N; ++dst) {
int firstK = TARGET_CNT;
for(int k = startK; k < TARGET_CNT; ++k) {
int target = TARGET_START + TARGET_STEP * k;
if(latestAll[target][b][dst] >= arr) {
firstK = k;
break;
}
}
if(firstK < TARGET_CNT)
addDst[firstK][addCnt[firstK]++] = dst;
}
array<int, 47> activeDst{};
int activeDstCnt = 0;
for(int k = startK; k < TARGET_CNT; ++k) {
for(int i = 0; i < addCnt[k]; ++i)
activeDst[activeDstCnt++] = addDst[k][i];
if(activeDstCnt == 0)
continue;
int target = TARGET_START + TARGET_STEP * k;
const auto &targetMat = latestAll[target];
for(int si = 0; si < activeSrcCnt; ++si) {
int src = activeSrc[si];
int pre = preBySrc[src];
for(int di = 0; di < activeDstCnt; ++di) {
int dst = activeDst[di];
int idx2 = demandId[src][dst];
if(idx2 < 0)
continue;
const auto &d = demands[idx2];
int oldCi = targetMat[src][dst];
if(pre <= oldCi)
continue;
if(d.sq[k] < pre && !(d.sq[k] < oldCi))
deltaCi += d.w;
}
}
}
return deltaCi;
};
auto extendGreedy = [&](vector<vector<Flight>> &planeFlights,
vector<int> &headCity,
vector<int> &headTime,
vector<int> &legCount,
vector<vector<vector<int>>> &latestAll,
long double ¤tCi,
double ¤tScore,
int unlockPlane) {
int maxTotalOps = K * maxLegPerPlane;
for(int op = 0; op < maxTotalOps; ++op) {
vector<tuple<int, int, int, int>> ops; // plane, from, dep, arr
ops.reserve(K * N);
for(int p = 0; p < K; ++p) {
if(unlockPlane >= 0 && p != unlockPlane)
continue;
if(legCount[p] >= maxLegPerPlane)
continue;
int b = headCity[p];
int arr = headTime[p];
for(int a = 0; a < N; ++a) {
if(a == b)
continue;
int dep = arr - dur[a][b];
if(dep < 0)
continue;
ops.emplace_back(p, a, dep, arr);
}
}
if(ops.empty())
break;
double bestScore = currentScore;
long double bestDeltaCi = 0.0L;
int bestPlane = -1, bestFrom = -1, bestDep = -1, bestArr = -1;
for(const auto &[p, a, dep, arr] : ops) {
int b = headCity[p];
long double deltaCi = calcDeltaCiEdge(a, b, dep, arr, latestAll);
double s = (totalDen > 0.0L ? (double)((currentCi + deltaCi) / totalDen) : 0.0);
if(s > bestScore || (s == bestScore && deltaCi > bestDeltaCi)) {
bestScore = s;
bestDeltaCi = deltaCi;
bestPlane = p;
bestFrom = a;
bestDep = dep;
bestArr = arr;
}
}
if(bestPlane < 0)
break;
int b = headCity[bestPlane];
planeFlights[bestPlane].insert(planeFlights[bestPlane].begin(), {bestFrom, b, bestDep, bestArr});
headCity[bestPlane] = bestFrom;
headTime[bestPlane] = bestDep;
legCount[bestPlane]++;
applyFlightToLatestAll(latestAll, bestFrom, b, bestDep, bestArr);
currentCi += bestDeltaCi;
currentScore = (totalDen > 0.0L ? (double)(currentCi / totalDen) : 0.0);
}
};
auto buildPlaneByDP = [&](int seedCity, const vector<vector<vector<int>>> &latestAll) {
static constexpr long double NEG = -1e100L;
static array<array<array<long double, MAX_SLOT + 2>, 47>, 47> edgeDiff;
static array<array<array<long double, MAX_SLOT + 1>, 47>, 47> edgeGain;
static array<array<long double, MAX_SLOT + 1>, 47> dp;
static array<array<int, MAX_SLOT + 1>, 47> nxt;
for(int u = 0; u < N; ++u)
for(int v = 0; v < N; ++v) {
edgeDiff[u][v].fill(0.0L);
edgeGain[u][v].fill(0.0L);
}
for(int u = 0; u < N; ++u) {
for(int dst = 0; dst < N; ++dst) {
if(pairWeight[u][dst] == 0.0L)
continue;
for(int k = 0; k < TARGET_CNT; ++k) {
int target = TARGET_START + TARGET_STEP * k;
int r_s = sqBest[k][u][dst];
int c_s = latestAll[target][u][dst];
if(c_s > r_s)
continue;
int min_s = max(0, r_s + 1);
for(int v = 0; v < N; ++v) {
if(u == v)
continue;
int max_t = (v == dst ? target : latestAll[target][v][dst]);
if(max_t < 0)
continue;
int max_s = min(MAX_SLOT - dur[u][v], max_t - dur[u][v]);
if(min_s > max_s)
continue;
edgeDiff[u][v][min_s] += pairWeight[u][dst];
if(max_s + 1 <= MAX_SLOT)
edgeDiff[u][v][max_s + 1] -= pairWeight[u][dst];
}
}
}
}
for(int u = 0; u < N; ++u) {
for(int v = 0; v < N; ++v) {
long double cur = 0.0L;
for(int s = 0; s <= MAX_SLOT; ++s) {
cur += edgeDiff[u][v][s];
edgeGain[u][v][s] = cur;
}
}
}
for(int u = 0; u < N; ++u) {
dp[u].fill(0.0L);
nxt[u].fill(-1);
}
for(int t = MAX_SLOT; t >= 0; --t) {
for(int u = 0; u < N; ++u) {
if(t + 1 <= MAX_SLOT) {
dp[u][t] = dp[u][t + 1];
nxt[u][t] = -1; // wait
} else {
dp[u][t] = 0.0L;
nxt[u][t] = -1;
}
for(int v = 0; v < N; ++v) {
if(u == v)
continue;
int nt = t + dur[u][v];
if(nt > MAX_SLOT)
continue;
long double cand = edgeGain[u][v][t] + dp[v][nt];
if(cand > dp[u][t]) {
dp[u][t] = cand;
nxt[u][t] = v;
}
}
}
}
int bestCity = seedCity;
long double bestVal = dp[seedCity][0];
for(int u = 0; u < N; ++u) {
if(dp[u][0] > bestVal) {
bestVal = dp[u][0];
bestCity = u;
}
}
vector<Flight> path;
int u = bestCity, t = 0;
while(t <= MAX_SLOT) {
int v = nxt[u][t];
if(v < 0)
t++;
else {
int nt = t + dur[u][v];
path.push_back({u, v, t, nt});
t = nt;
u = v;
}
}
return path;
};
vector<vector<Flight>> currentPlaneFlights(K);
vector<int> currentHeadCity(K), currentHeadTime(K), currentLegCount(K, 0);
auto seedOrder = makeSeedOrder(0);
vector<vector<vector<int>>> latestAll = baseLatestAll;
const int DP_INIT_PLANES = K;
for(int p = 0; p < K; ++p) {
int c = seedOrder[p % N];
bool useDp = (p < DP_INIT_PLANES);
if(useDp) {
auto flights = buildPlaneByDP(c, latestAll);
currentPlaneFlights[p] = flights;
currentLegCount[p] = (int)flights.size();
if(flights.empty()) {
currentHeadCity[p] = c;
currentHeadTime[p] = MAX_SLOT;
} else {
currentHeadCity[p] = flights[0].a;
currentHeadTime[p] = flights[0].s;
for(const auto &f : flights)
applyFlightToLatestAll(latestAll, f.a, f.b, f.s, f.t);
}
} else {
currentHeadCity[p] = c;
currentHeadTime[p] = MAX_SLOT;
currentLegCount[p] = 0;
}
}
long double currentCi = calcCiFromLatest(latestAll);
double currentScore = (totalDen > 0.0L ? (double)(currentCi / totalDen) : 0.0);
bestPlaneFlights = currentPlaneFlights;
bestScoreAll = evaluator.score(flattenPlaneFlights(bestPlaneFlights), demands);
bestTrial = 0;
int initFlightCnt = 0;
for(const auto &v : bestPlaneFlights)
initFlightCnt += (int)v.size();
cerr << fixed << setprecision(12)
<< "iter=0 score=" << bestScoreAll
<< " flights=" << initFlightCnt << '\n';
int iter = 1;
while(true) {
double elapsed = chrono::duration<double>(chrono::steady_clock::now() - begin).count();
if(elapsed >= TL)
break;
int resetPlane = (int)(rng() % K);
if(iter % 3 == 0) {
resetPlane = 0;
for(int p = 1; p < K; ++p) {
if(currentLegCount[p] < currentLegCount[resetPlane])
resetPlane = p;
}
}
vector<vector<Flight>> candPlaneFlights = currentPlaneFlights;
vector<int> candHeadCity = currentHeadCity;
vector<int> candHeadTime = currentHeadTime;
vector<int> candLegCount = currentLegCount;
auto order = makeSeedOrder(iter + 1);
int seed = order[(resetPlane * 7 + iter) % N];
candPlaneFlights[resetPlane].clear();
candHeadCity[resetPlane] = seed;
candHeadTime[resetPlane] = MAX_SLOT;
candLegCount[resetPlane] = 0;
auto candLatestAll = baseLatestAll;
for(int p = 0; p < K; ++p) {
for(const auto &f : candPlaneFlights[p])
applyFlightToLatestAll(candLatestAll, f.a, f.b, f.s, f.t);
}
long double candCi = calcCiFromLatest(candLatestAll);
double candScore = (totalDen > 0.0L ? (double)(candCi / totalDen) : 0.0);
extendGreedy(
candPlaneFlights, candHeadCity, candHeadTime, candLegCount, candLatestAll, candCi, candScore, resetPlane);
bool accept = (candScore >= currentScore);
if(!accept) {
long double delta = currentScore - candScore;
long double temp = 0.0005L;
long double prob = expl(-delta / temp);
long double r = (long double)(rng() & ((1ULL << 53) - 1)) / (long double)(1ULL << 53);
if(r < prob)
accept = true;
}
if(accept) {
currentPlaneFlights.swap(candPlaneFlights);
currentHeadCity.swap(candHeadCity);
currentHeadTime.swap(candHeadTime);
currentLegCount.swap(candLegCount);
latestAll.swap(candLatestAll);
currentCi = candCi;
currentScore = candScore;
}
if(candScore > bestScoreAll) {
auto candFlights = flattenPlaneFlights(candPlaneFlights);
double exact = evaluator.score(candFlights, demands);
if(exact > bestScoreAll) {
bestScoreAll = exact;
bestTrial = iter;
bestPlaneFlights = candPlaneFlights;
}
}
if(iter % 50 == 0) {
int curFlightCnt = 0;
for(const auto &v : currentPlaneFlights)
curFlightCnt += (int)v.size();
cerr << fixed << setprecision(12)
<< "iter=" << iter
<< " current=" << currentScore
<< " best=" << bestScoreAll
<< " flights=" << curFlightCnt << '\n';
}
iter++;
}
auto scorePlaneFlights = [&](const vector<vector<Flight>> &pf) {
return evaluator.score(flattenPlaneFlights(pf), demands);
};
vector<vector<Flight>> planeFlights = bestPlaneFlights;
double finalScore = bestScoreAll;
for(int p = 0; p < K; ++p) {
auto &pf = planeFlights[p];
if(pf.empty())
continue;
int minStart = pf.front().s;
int maxEnd = pf.back().t;
int lo = max(-6, -minStart);
int hi = min(6, MAX_SLOT - maxEnd);
int bestDelta = 0;
double bestLocal = finalScore;
for(int delta = lo; delta <= hi; ++delta) {
if(delta == 0)
continue;
for(auto &f : pf) {
f.s += delta;
f.t += delta;
}
double s = scorePlaneFlights(planeFlights);
for(auto &f : pf) {
f.s -= delta;
f.t -= delta;
}
if(s > bestLocal) {
bestLocal = s;
bestDelta = delta;
}
}
if(bestDelta != 0) {
for(auto &f : pf) {
f.s += bestDelta;
f.t += bestDelta;
}
finalScore = bestLocal;
}
}
vector<Flight> finalFlights = flattenPlaneFlights(planeFlights);
vector<int> flownCity(N, 0);
for(const auto &f : finalFlights) {
flownCity[f.a] = 1;
flownCity[f.b] = 1;
}
for(int i = 0; i < K; ++i) {
cout << planeFlights[i].size() << '\n';
for(const auto &f : planeFlights[i]) {
cout << (f.a + 1) << ' ' << slotToTime(f.s) << ' ' << (f.b + 1) << ' ' << slotToTime(f.t) << '\n';
}
}
cerr << fixed << setprecision(12)
<< "best_trial=" << bestTrial << ' '
<< "score=" << finalScore
<< " unique_cities=" << count(flownCity.begin(), flownCity.end(), 1)
<< " flights=" << finalFlights.size() << '\n';
return 0;
}