結果
| 問題 | No.5023 Airlines Optimization |
| コンテスト | |
| ユーザー |
 titan23
|
| 提出日時 | 2026-02-25 22:21:40 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 30,822 bytes |
| 記録 | |
| コンパイル時間 | 9,141 ms |
| コンパイル使用メモリ | 395,664 KB |
| 実行使用メモリ | 7,976 KB |
| スコア | 6,598,874 |
| 最終ジャッジ日時 | 2026-02-25 22:21:56 |
| 合計ジャッジ時間 | 14,003 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 21 WA * 79 |
ソースコード
// 初期解のみ
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
// #include <atcoder/all>
// using namespace atcoder;
using ll = long long;
#define rep(i, n) for (ll i = 0; i < (ll)(n); ++i)
const ll dy[] = {-1, 0, 0, 1};
const ll dx[] = {0, -1, 1, 0};
template <class T, class T1, class T2> bool isrange(T target, T1 low, T2 high) { return low <= target && target < high; }
template <class T, class U> T min(const T &t, const U &u) { return t < u ? t : u; }
template <class T, class U> T max(const T &t, const U &u) { return t < u ? u : t; }
template <class T, class U> bool chmin(T &t, const U &u) { if (t > u) { t = u; return true; } return false; }
template <class T, class U> bool chmax(T &t, const U &u) { if (t < u) { t = u; return true; } return false; }
// #include "titan_cpplib/ahc/timer.cpp"
#include <iostream>
#include <chrono>
using namespace std;
// Timer
namespace titan23 {
/**
* @brief 時間計測クラス
*/
class Timer {
private:
chrono::time_point<chrono::high_resolution_clock> start_timepoint;
public:
Timer() : start_timepoint(chrono::high_resolution_clock::now()) {}
//! リセットする
void reset() {
start_timepoint = chrono::high_resolution_clock::now();
}
//! 経過時間[ms](double)を返す
double elapsed() const {
// auto end_timepoint = chrono::high_resolution_clock::now();
// auto start = chrono::time_point_cast<chrono::microseconds>(start_timepoint).time_since_epoch().count();
// auto end = chrono::time_point_cast<chrono::microseconds>(end_timepoint).time_since_epoch().count();
// return (end - start) * 0.001;
auto end_timepoint = std::chrono::high_resolution_clock::now();
std::chrono::duration<double, std::milli> duration = end_timepoint - start_timepoint;
return duration.count();
}
};
} // namespace titan23
// #include "titan_cpplib/algorithm/random.cpp"
#include <cassert>
#include <unordered_set>
#include <vector>
using namespace std;
// Random
namespace titan23 {
/**
* @brief (疑似)乱数生成クラス(XOR shift)
*/
class Random {
private:
unsigned int _x, _y, _z, _w;
constexpr unsigned int _xor128() {
const unsigned int t = _x ^ (_x << 11);
_x = _y;
_y = _z;
_z = _w;
_w = (_w ^ (_w >> 19)) ^ (t ^ (t >> 8));
return _w;
}
public:
Random() : _x(123456789), _y(362436069), _z(521288629), _w(88675123) {}
//! `[0, 1]` の乱数を返す(実数)
constexpr double random() { return (double)(_xor128()) / 0xFFFFFFFF; }
//! `[0, end]` の乱数を返す(整数)
constexpr int randint(const int end) {
assert(0 <= end);
return (((unsigned long long)_xor128() * (end+1)) >> 32);
}
//! `[begin, end]` の乱数を返す(整数)
constexpr int randint(const int begin, const int end) {
assert(begin <= end);
return begin + (((unsigned long long)_xor128() * (end-begin+1)) >> 32);
}
//! `[0, end)` の乱数を返す(整数)
constexpr int randrange(const int end) {
assert(0 < end);
return (((unsigned long long)_xor128() * end) >> 32);
}
//! `[begin, end)` の乱数を返す(整数)
constexpr int randrange(const int begin, const int end) {
assert(begin < end);
return begin + (((unsigned long long)_xor128() * (end-begin)) >> 32);
}
//! `[0, u64_MAX)` の乱数を返す / zobrist hash等の使用を想定
constexpr unsigned long long rand_u64() {
return ((unsigned long long)_xor128() << 32) | _xor128();
}
//! `[0, end)` の異なる乱数を2つ返す
constexpr pair<int, int> rand_pair(const int end) {
assert(end >= 2);
int u = randrange(end);
int v = u + randrange(1, end);
if (v >= end) v -= end;
if (u > v) swap(u, v);
return {u, v};
}
//! `[begin, end)` の異なる乱数を2つ返す
constexpr pair<int, int> rand_pair(const int begin, const int end) {
assert(end - begin >= 2);
int u = randrange(begin, end);
int v = (u + randrange(1, end-begin));
if (v >= end) v -= (end-begin);
if (u > v) swap(u, v);
return {u, v};
}
//! Note `a`は非const
vector<int> rand_vec(const int cnt, vector<int> &a) {
int n = a.size();
for (int i = 0; i < cnt; ++i) {
int j = randrange(i, n);
swap(a[i], a[j]);
}
vector<int> res(a.begin(), a.begin()+cnt);
return res;
}
//! `[begin, end)` の乱数を返す(実数)
constexpr double randdouble(const double begin, const double end) {
assert(begin < end);
return begin + random() * (end-begin);
}
//! `vector` をインプレースにシャッフルする / `O(n)`
template <typename T>
constexpr void shuffle(vector<T> &a) {
int n = a.size();
for (int i = 0; i < n-1; ++i) {
int j = randrange(i, n);
swap(a[i], a[j]);
}
}
template <typename T>
vector<T> choices(const vector<T> &a, const int k) {
assert(a.size() >= k);
vector<T> r(k);
unordered_set<int> seen;
for (int i = 0; i < k; ++i) {
int x = randrange(a.size());
while (seen.find(x) != seen.end()) x = randrange(a.size());
seen.insert(x);
r[i] = a[x];
}
return r;
}
template <typename T>
constexpr T choice(const vector<T> &a) {
assert(!a.empty());
return a[randrange(a.size())];
}
template <typename T>
constexpr T choice(const vector<T> &a, const vector<int> &w, bool normal) {
assert(normal == false);
assert(a.size() == w.size());
double sum = 0.0;
for (const int &x: w) sum += x;
assert(sum > 0);
vector<double> x(w.size());
for (int i = 0; i < x.size(); ++i) {
x[i] = (double)w[i] / sum;
if (i-1 >= 0) x[i] += x[i-1];
}
return choice(a, x);
}
template <typename T>
constexpr T choice(const vector<T> &a, const vector<double> &w) {
double i = random();
int l = -1, r = a.size()-1;
while (r - l > 1) {
int mid = (l + r) / 2;
if (w[mid] <= i) l = mid;
else r = mid;
}
return a[r];
}
template <typename T>
constexpr T rand_pop(vector<T> &a) {
assert(!a.empty());
int idx = randrange(a.size());
T res = a[idx];
a.erase(a.begin() + idx);
return res;
}
};
} // namespace titan23
// #include "titan_cpplib/others/print.cpp"
#include <iostream>
#include <vector>
#include <set>
#include <tuple>
#include <unordered_set>
#include <algorithm>
#include <map>
#include <unordered_map>
using namespace std;
// print
// -------------------------
// pair<K, V>
template<typename K, typename V> ostream& operator<<(ostream& os, const pair<K, V>& p);
// tuple<T1, T2, T3>
template<typename T1, typename T2, typename T3> ostream &operator<<(ostream &os, const tuple<T1, T2, T3> &t);
// tuple<T1, T2, T3, T4>
template<typename T1, typename T2, typename T3, typename T4> ostream &operator<<(ostream &os, const tuple<T1, T2, T3, T4> &t);
// vector<T>
template<typename T> ostream& operator<<(ostream& os, const vector<T>& a);
// vector<vector<T>>
template<typename T> ostream& operator<<(ostream& os, const vector<vector<T>>& a);
// array<T, 2>
template<typename T> ostream& operator<<(ostream& os, const array<T, 2>& a);
// deque<T>
template<typename T> ostream& operator<<(ostream& os, const deque<T>& dq);
// set<T>
template<typename T> ostream& operator<<(ostream& os, const set<T>& s);
// multiset<T>
template<typename T> ostream& operator<<(ostream& os, const multiset<T>& s);
// unordered_set<T>
template<typename T> ostream& operator<<(ostream& os, const unordered_set<T>& a);
// map<K, V>
template<typename K, typename V> ostream& operator<<(ostream& os, const map<K, V>& mp);
// unordered_map<K, V>
template<typename K, typename V> ostream& operator<<(ostream& os, const unordered_map<K, V>& mp);
// __int128_t
ostream& operator<<(ostream& os, __int128_t x);
// __uint128_t
ostream& operator<<(ostream& os, __uint128_t x);
// -------------------------
// color
static const string PRINT_RED = "\033[91m"; // 赤字
static const string PRINT_GREEN = "\033[92m"; // 緑字
static const string PRINT_BLUE = "\033[94m"; // 青字
static const string PRINT_NONE = "\033[m"; // 色を元に戻す
static const string PRINT_BOLD = "\u001b[1m"; // 太字
string to_red(const string &s) { return PRINT_RED + s + PRINT_NONE; }
string to_green(const string &s) { return PRINT_GREEN + s + PRINT_NONE; }
string to_blue(const string &s) { return PRINT_BLUE + s + PRINT_NONE; }
string to_bold(const string &s) { return PRINT_BOLD + s + PRINT_NONE; }
string spacefill(const string s, const int f) {
int n = s.size();
string t;
for (int i = 0; i < f-n; ++i) t += " ";
t += s;
return t;
}
string zfill(const string s, const int f) {
int n = s.size();
string t;
for (int i = 0; i < f-n; ++i) t += "0";
t += s;
return t;
}
string bin(long long s) {
if (s == 0) return "0";
string t;
while (s) {
t += (s & 1) ? '1' : '0';
s >>= 1;
}
reverse(t.begin(), t.end());
return t;
}
void DEBUG_LINE() { cerr << "[Line] : " << __LINE__ << std::endl; }
string to_string_int128(__int128_t x) {
if (x == 0) return "0";
bool neg = false;
if (x < 0) { neg = true; x = -x; }
string s;
while (x > 0) {
s += char('0' + (int)(x % 10));
x /= 10;
}
if (neg) s += '-';
reverse(s.begin(), s.end());
return s;
}
string to_string_uint128(__uint128_t x) {
if (x == 0) return "0";
string s;
while (x > 0) {
s += char('0' + (int)(x % 10));
x /= 10;
}
reverse(s.begin(), s.end());
return s;
}
// __int128_t
ostream& operator<<(ostream& os, __int128_t x) {
os << to_string_int128(x);
return os;
}
// __uint128_t
ostream& operator<<(ostream& os, __uint128_t x) {
os << to_string_uint128(x);
return os;
}
// pair<K, V>
template<typename K, typename V>
ostream& operator<<(ostream& os, const pair<K, V>& p) {
os << "(" << p.first << ", " << p.second << ")";
return os;
}
// tuple<T1, T2, T3>
template<typename T1, typename T2, typename T3>
ostream &operator<<(ostream &os, const tuple<T1, T2, T3> &t) {
os << "(" << get<0>(t) << ", " << get<1>(t) << ", " << get<2>(t) << ")";
return os;
}
// tuple<T1, T2, T3, T4>
template<typename T1, typename T2, typename T3, typename T4>
ostream &operator<<(ostream &os, const tuple<T1, T2, T3, T4> &t) {
os << "(" << get<0>(t) << ", " << get<1>(t) << ", " << get<2>(t) << ", " << get<3>(t) << ")";
return os;
}
// array<T, 2>
template<typename T>
ostream& operator<<(ostream& os, const array<T, 2>& a) {
os << "[";
for (int i = 0; i < (int)a.size(); ++i) {
if (i > 0) os << ", ";
os << a[i];
}
os << "]";
return os;
}
// vector<T>
template<typename T>
ostream& operator<<(ostream& os, const vector<T>& a) {
os << "[";
for (int i = 0; i < (int)a.size(); ++i) {
if (i > 0) os << ", ";
os << a[i];
}
os << "]";
return os;
}
// vector<vector<T>>
template<typename T>
ostream& operator<<(ostream& os, const vector<vector<T>>& a) {
os << "[\n";
int h = (int)a.size();
for (int i = 0; i < h; ++i) {
os << " " << a[i] << '\n';
}
os << "]";
return os;
}
// deque<T>
template<typename T>
ostream& operator<<(ostream& os, const deque<T>& dq) {
vector<T> a(dq.begin(), dq.end());
os << a;
return os;
}
// set<T>
template<typename T>
ostream& operator<<(ostream& os, const set<T>& s) {
os << "{";
auto it = s.begin();
while (it != s.end()) {
os << *it;
++it;
if (it != s.end()) {
os << ", ";
}
}
os << "}";
return os;
}
// multiset<T>
template<typename T>
ostream& operator<<(ostream& os, const multiset<T>& s) {
os << "{";
auto it = s.begin();
while (it != s.end()) {
os << *it;
++it;
if (it != s.end()) {
os << ", ";
}
}
os << "}";
return os;
}
// unordered_set<T>
template<typename T>
ostream& operator<<(ostream& os, const unordered_set<T>& a) {
set<T> s(a.begin(), a.end());
os << s;
return os;
}
// map<K, V>
template<typename K, typename V>
ostream& operator<<(ostream& os, const map<K, V>& mp) {
os << "{";
auto it = mp.begin();
while (it != mp.end()) {
os << it->first << ": " << it->second;
++it;
if (it != mp.end()) {
os << ", ";
}
}
os << "}";
return os;
}
// unordered_map<K, V>
template<typename K, typename V>
ostream& operator<<(ostream& os, const unordered_map<K, V>& mp) {
map<K, V> m(mp.begin(), mp.end());
os << m;
return os;
}
const int MAX_TIME = 1260; // 21:00
const int MIN_TIME = 360; // 06:00
const int N = 47;
const int R = 1000;
const int M = 400;
const int K = 25;
vector<int> X, Y;
vector<ll> W;
struct Flight {
int u, v, s, t;
};
vector<Flight> square_flights;
int req_time_mat[50][50];
int s_square[50][50][21]; // [source][dest][target_time_idx]
double dist_mat[50][50];
double w_prod[50][50];
int parse_time(const string& t_str) {
int h = stoi(t_str.substr(0, 2));
int m = stoi(t_str.substr(3, 2));
return h * 60 + m;
}
string format_time(int minutes) {
int h = minutes / 60;
int m = minutes % 60;
string res = "";
if (h < 10) res += "0";
res += to_string(h) + ":";
if (m < 10) res += "0";
res += to_string(m);
return res;
}
void input() {
char c = cin.peek(); // ???????????????
if (c == (char)0xEF) {
cin.get(); cin.get(); cin.get();
}
int a;
cin >> a >> a;
X.resize(N);
Y.resize(N);
W.resize(N);
rep(i, N) cin >> X[i] >> Y[i] >> W[i];
cin >> a;
square_flights.resize(M);
rep(i, M) {
string s_str, t_str;
cin >> square_flights[i].u >> s_str >> square_flights[i].v >> t_str;
--square_flights[i].u;
--square_flights[i].v;
square_flights[i].s = parse_time(s_str);
square_flights[i].t = parse_time(t_str);
}
cin >> a;
}
void precalc() {
rep(i, N) rep(j, N) {
dist_mat[i][j] = hypot((double)X[i] - X[j], (double)Y[i] - Y[j]);
if (i == j) {
req_time_mat[i][j] = 0;
} else {
double val = 60.0 * dist_mat[i][j] / 800.0 + 40.0;
req_time_mat[i][j] = (int)(ceil(val / 5.0 - 1e-9)) * 5;
if (req_time_mat[i][j] < (int)ceil(val)) req_time_mat[i][j] += 5; // 安全策
req_time_mat[i][j] = (( (int)ceil(val) + 4) / 5) * 5;
}
}
rep(i, N) rep(j, N) rep(t, 21) s_square[i][j][t] = -2e9;
vector<Flight> sq = square_flights;
sort(sq.begin(), sq.end(), [](const Flight& a, const Flight& b) {
return a.s > b.s;
});
rep(dest, N) {
rep(tidx, 21) {
int T = 660 + tidx * 30;
vector<int> dp(N, -2e9);
for (const auto& f : sq) {
if (f.t <= T) {
if (f.v == dest) {
dp[f.u] = max(dp[f.u], f.s);
} else if (dp[f.v] >= f.t) {
dp[f.u] = max(dp[f.u], f.s);
}
}
}
rep(src, N) s_square[src][dest][tidx] = dp[src];
}
}
}
// sa 最小化
namespace sa {
titan23::Random sarnd;
const int LOG_TABLE_SIZE = 4096;
double LOG_TABLE[LOG_TABLE_SIZE]; // 線形補間
static bool is_log_initialized = [] {
for (int i = 0; i < LOG_TABLE_SIZE; ++i) {
LOG_TABLE[i] = log((double)(i + 0.5) / LOG_TABLE_SIZE);
}
return true;
}();
// TODO
using ScoreType = double;
struct Param {
double start_temp = 1e-3, end_temp = 1e-6;
} param;
// ==================================================================================
struct Changed {
int TYPE_CNT = 4; // 0:シフト, 1:部分再構築, 2:末尾追加/削除, 3:Swap
int type;
ScoreType pre_score;
int plane_idx1;
int plane_idx2; // Swap用
vector<Flight> old_flights1;
vector<Flight> old_flights2; // Swap用
Changed() {}
} changed;
void sa_init() {
precalc();
}
class State {
public:
bool is_valid;
ScoreType score;
vector<vector<Flight>> planes;
State() {}
void init() {
score = 0;
planes.resize(K);
vector<vector<int>> visit_count(N, vector<int>(N, 0));
rep(k, K) {
int cur_t = MIN_TIME;
// 25機をランダムな都市に配置してスタート
int cur_l = sa::sarnd.randrange(N);
while (true) {
int best_nxt = -1;
double best_eval = -1.0;
rep(nxt, N) {
if (nxt == cur_l) continue;
int dur = req_time_mat[cur_l][nxt];
// 乗り継ぎや少しの空き時間を考慮して出発時刻を仮決め
int st = ((cur_t + 4) / 5) * 5 + 5;
if (st + dur > MAX_TIME) continue;
// 評価関数：需要の積 / 所要時間
double eval = (double)W[cur_l] * W[nxt] / dur;
// 【重要】他の機体がすでに飛んでいる路線にはペナルティを与え、全国に散らばらせる
eval /= (1.0 + visit_count[cur_l][nxt] * 5.0 + visit_count[nxt][cur_l] * 5.0);
// 乱数で揺らぎを持たせる
eval *= (1.0 + sa::sarnd.randrange(100) / 200.0);
if (chmax(best_eval, eval)) {
best_nxt = nxt;
}
}
if (best_nxt == -1) break;
int st = ((cur_t + 4) / 5) * 5 + sa::sarnd.randrange(3) * 5;
int dur = req_time_mat[cur_l][best_nxt];
planes[k].push_back({cur_l, best_nxt, st, st + dur});
visit_count[cur_l][best_nxt]++;
cur_t = st + dur;
cur_l = best_nxt;
}
}
score = calc_eval();
print();
exit(0);
}
void reset_is_valid() { is_valid = true; }
ScoreType get_score() const { return score; }
ScoreType get_true_score() const { return score; }
double calc_eval() const {
// e8の構築とソート
vector<Flight> e8;
e8.reserve(K * 30); // 動的確保を減らすための予約
for (const auto& p : planes) for (const auto& f : p) e8.push_back(f);
sort(e8.begin(), e8.end(), [](const Flight& a, const Flight& b) { return a.s > b.s; });
double v_sq = 0, v_e8 = 0;
double min_dist = 0.25 * R;
// DPの枝刈り・高速化
vector<vector<int>> dp(N, vector<int>(21, -2e9));
rep(dest, N) {
// 初期化
rep(u, N) rep(tidx, 21) dp[u][tidx] = -2e9;
// フライトごとに1ループだけ回し、影響する target_time (tidx) のみ更新する
for (const auto& f : e8) {
// f.t が間に合う最初の tidx を直接計算 (T = 660 + tidx*30)
int start_tidx = max(0, (f.t - 660 + 29) / 30);
if (start_tidx > 20) continue; // どの締切にも間に合わない
if (f.v == dest) {
for (int tidx = start_tidx; tidx < 21; ++tidx) {
if (f.s > dp[f.u][tidx]) dp[f.u][tidx] = f.s;
}
} else {
for (int tidx = start_tidx; tidx < 21; ++tidx) {
if (dp[f.v][tidx] >= f.t) {
if (f.s > dp[f.u][tidx]) dp[f.u][tidx] = f.s;
}
}
}
}
rep(src, N) {
if (dist_mat[src][dest] < min_dist) continue;
double weight = (double)W[src] * W[dest];
rep(tidx, 21) {
if (s_square[src][dest][tidx] < dp[src][tidx]) v_e8 += weight;
else v_sq += weight;
}
}
}
return (v_sq + v_e8 == 0) ? 0.0 : -(v_e8 / (v_sq + v_e8));
}
void modify(const ScoreType threshold, const double progress) {
is_valid = true;
changed.type = sa::sarnd.randrange(changed.TYPE_CNT);
changed.plane_idx1 = sa::sarnd.randrange(K);
changed.old_flights1 = planes[changed.plane_idx1];
auto& target1 = planes[changed.plane_idx1];
if (changed.type == 0) {
// 【Type 0: 時間のシフト微調整】
if (target1.empty()) { is_valid = false; return; }
int idx = sa::sarnd.randrange(target1.size());
int delta = (sa::sarnd.randrange(7) - 3) * 5; // -15, -10, -5, 0, 5, 10, 15
if (delta == 0) delta = 5;
int new_s = target1[idx].s + delta;
int new_t = target1[idx].t + delta;
int min_s = (idx == 0) ? MIN_TIME : target1[idx-1].t;
int max_t = (idx + 1 == target1.size()) ? MAX_TIME : target1[idx+1].s;
if (new_s >= min_s && new_t <= max_t) {
target1[idx].s = new_s;
target1[idx].t = new_t;
} else {
is_valid = false;
}
} else if (changed.type == 1) {
// 【Type 1: 部分再構築（シンプル版）】
int sz = target1.size();
int L = sa::sarnd.randrange(sz + 1);
int R = L + sa::sarnd.randrange(min(3, sz - L + 1));
int cur_l = (L == 0) ? sa::sarnd.randrange(N) : target1[L-1].v;
int cur_t = (L == 0) ? MIN_TIME : target1[L-1].t;
int tgt_l = (R == sz) ? -1 : target1[R].u;
int tgt_t = (R == sz) ? MAX_TIME : target1[R].s;
vector<Flight> new_segment;
bool ok = true;
if (tgt_l != -1) {
if (cur_l == tgt_l) {
// 同じ都市なら何もしない（空き時間ができる）
} else {
int st = ((cur_t + 4)/5)*5 + sa::sarnd.randrange(3)*5;
int dur = req_time_mat[cur_l][tgt_l];
// 時間が間に合えば直接繋ぐ、無理なら棄却
if (st + dur <= tgt_t) {
new_segment.push_back({cur_l, tgt_l, st, st + dur});
} else {
ok = false;
}
}
} else {
// 後ろがない場合、適当に新しく伸ばす
int len = sa::sarnd.randrange(4);
rep(step, len) {
int nxt_l = sa::sarnd.randrange(N);
if (nxt_l == cur_l) nxt_l = (nxt_l + 1) % N;
int st = ((cur_t + 4)/5)*5 + sa::sarnd.randrange(3)*5;
int dur = req_time_mat[cur_l][nxt_l];
if (st + dur > MAX_TIME) break;
new_segment.push_back({cur_l, nxt_l, st, st + dur});
cur_t = st + dur;
cur_l = nxt_l;
}
}
if (!ok) {
is_valid = false;
} else {
vector<Flight> next_flights;
next_flights.reserve(L + new_segment.size() + (sz - R));
for(int i = 0; i < L; ++i) next_flights.push_back(target1[i]);
for(auto& f : new_segment) next_flights.push_back(f);
for(int i = R; i < sz; ++i) next_flights.push_back(target1[i]);
target1 = next_flights;
}
} else if (changed.type == 2) {
// 【Type 2: 末尾の追加・削除】
if (sa::sarnd.randrange(2) == 0) {
if (!target1.empty()) target1.pop_back(); else is_valid = false;
} else {
int last_time = MIN_TIME, last_loc = sa::sarnd.randrange(N);
if (!target1.empty()) { last_time = target1.back().t; last_loc = target1.back().v; }
int next_loc = sa::sarnd.randrange(N);
if (next_loc == last_loc) next_loc = (next_loc + 1) % N;
int st = ((max(MIN_TIME, last_time) + 4) / 5) * 5 + sa::sarnd.randrange(6) * 5;
int dur = req_time_mat[last_loc][next_loc];
if (st + dur <= MAX_TIME) target1.push_back({last_loc, next_loc, st, st + dur});
else is_valid = false;
}
} else if (changed.type == 3) {
// 【Type 3: 2機間のスケジュールSwap】
changed.plane_idx2 = sa::sarnd.randrange(K);
if (changed.plane_idx1 == changed.plane_idx2) { is_valid = false; return; }
changed.old_flights2 = planes[changed.plane_idx2];
auto& target2 = planes[changed.plane_idx2];
if (target1.empty() || target2.empty()) { is_valid = false; return; }
// 共通して訪れる都市の履歴を探す
vector<pair<int, int>> common_points;
rep(i, target1.size()) rep(j, target2.size()) {
if (target1[i].v == target2[j].v) common_points.push_back({i, j});
}
if (common_points.empty()) { is_valid = false; return; }
auto pt = common_points[sa::sarnd.randrange(common_points.size())];
int i1 = pt.first, i2 = pt.second;
// SwapするSuffix部分を取り出す
vector<Flight> suf1(target1.begin() + i1 + 1, target1.end());
vector<Flight> suf2(target2.begin() + i2 + 1, target2.end());
int t1_end = target1[i1].t;
int t2_end = target2[i2].t;
// 時間の整合性を保つためのシフト処理ラムダ
auto shift_suffix = [](vector<Flight>& suf, int prev_t) {
int cur_t = prev_t;
vector<Flight> valid_suf;
for(auto& f : suf) {
int st = max(f.s, ((cur_t + 4)/5)*5);
int dur = f.t - f.s;
if (st + dur <= MAX_TIME) {
valid_suf.push_back({f.u, f.v, st, st + dur});
cur_t = st + dur;
} else break; // 時間切れで以降は切り捨て
}
return valid_suf;
};
suf1 = shift_suffix(suf1, t2_end);
suf2 = shift_suffix(suf2, t1_end);
target1.resize(i1 + 1);
for(auto& f : suf2) target1.push_back(f);
target2.resize(i2 + 1);
for(auto& f : suf1) target2.push_back(f);
}
if (is_valid) score = calc_eval();
}
void rollback() {
planes[changed.plane_idx1] = changed.old_flights1;
if (changed.type == 3) {
planes[changed.plane_idx2] = changed.old_flights2; // Swapの場合は2機とも戻す
}
}
void advance() {}
void print() const {
rep(k, K) {
cout << planes[k].size() << "\n";
for (const auto& f : planes[k]) {
cout << f.u+1 << " " << format_time(f.s) << " "
<< f.v+1 << " " << format_time(f.t) << "\n";
}
}
}
};
// ==================================================================================
// TIME_LIMIT: ms
State sa_run(const double TIME_LIMIT, const bool verbose = false) {
titan23::Timer sa_timer;
const double START_TEMP = param.start_temp;
const double END_TEMP = param.end_temp;
const double TEMP_VAL = (START_TEMP - END_TEMP) / TIME_LIMIT;
State state;
state.init();
State best_state = state;
ScoreType score = state.get_score();
ScoreType best_score = score;
double now_time;
long long cnt = 0, bst_cnt = 0, upd_cnt = 0;
vector<long long> accept(changed.TYPE_CNT), modify(changed.TYPE_CNT);
while (true) {
// if ((cnt & 31) == 0) now_time = sa_timer.elapsed();
now_time = sa_timer.elapsed();
if (now_time > TIME_LIMIT) break;
++cnt;
ScoreType threshold = score - (START_TEMP-TEMP_VAL*now_time) * LOG_TABLE[sarnd.randrange(LOG_TABLE_SIZE)];
changed.pre_score = state.score;
double progress = now_time / TIME_LIMIT;
state.reset_is_valid();
state.modify(threshold, progress);
modify[changed.type]++;
ScoreType new_score = state.get_score();
if (state.is_valid && new_score <= threshold) {
++upd_cnt;
accept[changed.type]++;
state.advance();
score = new_score;
if (score < best_score) {
bst_cnt++;
best_score = score;
best_state = state;
if (verbose) {
cerr << "Info: score=" << best_score << endl;
}
}
} else {
state.score = changed.pre_score;
state.rollback();
}
}
if (verbose) {
cerr << "=============" << endl;
for (int i = 0; i < modify.size(); ++i) {
cerr << "Info: Type=" << i << " | " << accept[i] << " / " << modify[i] << endl;
}
cerr << "Info: bst=" << bst_cnt << endl;
cerr << "Info: ac=" << upd_cnt << endl;
cerr << "Info: loop=" << cnt << endl;
cerr << "Info: accept rate=" << (cnt > 0 ? (int)((double)upd_cnt/cnt*100) : 0) << "%" << endl;
cerr << "Info: update best rate=" << (cnt > 0 ? (int)((double)bst_cnt/cnt*100) : 0) << "%" << endl;
cerr << "Info: best_score = " << best_score << endl;
cerr << "Info: cnt=" << cnt << endl;
}
return best_state;
}
} // namespace sa
void solve() {
sa::sa_init();
const double TL = 950;
sa::State best_state = sa::sa_run(TL, true);
best_state.print();
ll final_score = (ll)(1000000 * (-best_state.get_score()));
cerr << "Score = " << final_score*100 << endl;
// 55367915
cerr << dist_mat[6][10] << endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout << fixed << setprecision(3);
cerr << fixed << setprecision(3);
input();
solve();
return 0;
}