結果
| 問題 | No.5023 Airlines Optimization |
| コンテスト | |
| ユーザー |
 titan23
|
| 提出日時 | 2026-02-25 22:57:01 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
AC
|
| 実行時間 | 976 ms / 1,000 ms |
| コード長 | 32,194 bytes |
| 記録 | |
| コンパイル時間 | 9,703 ms |
| コンパイル使用メモリ | 404,148 KB |
| 実行使用メモリ | 7,848 KB |
| スコア | 44,560,018 |
| 最終ジャッジ日時 | 2026-02-25 22:58:55 |
| 合計ジャッジ時間 | 111,183 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge6 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 100 |
ソースコード
#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-4, end_temp = 1e-7;
} param;
void sa_init() {
precalc();
}
// ==================================================================================
struct Changed {
int TYPE_CNT = 6;
int type;
int p; // 変更した飛行機のインデックス
double pre_score;
vector<Flight> old_flights; // ロールバック用のバックアップ
} changed;
class State {
public:
bool is_valid;
double score;
vector<vector<Flight>> planes;
State() : score(0) {}
void init() {
score = 0;
planes.assign(K, vector<Flight>());
vector<vector<int>> visit_count(N, vector<int>(N, 0));
rep(k, K) {
int cur_t = MIN_TIME;
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 base_st = ((cur_t + 4) / 5) * 5;
if (base_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 base_st = ((cur_t + 4) / 5) * 5;
int st = base_st + sa::sarnd.randrange(3) * 5;
int dur = req_time_mat[cur_l][best_nxt];
if (st + dur > MAX_TIME) {
break;
}
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();
}
void reset_is_valid() { is_valid = true; }
double get_score() const { return score; }
double get_true_score() const { return score; }
double calc_eval() const {
// 【高速化1】動的確保を廃止し、static配列を使い回す
static Flight e8_buf[2000];
int e8_sz = 0;
for (const auto& p : planes) {
for (const auto& f : p) {
e8_buf[e8_sz++] = f;
}
}
// 時間の降順にソート
sort(e8_buf, e8_buf + e8_sz, [](const Flight& a, const Flight& b) { return a.s > b.s; });
double v_sq = 0, v_e8 = 0;
double min_dist = 0.25 * R;
// 【高速化2】DPテーブルもstaticにして1次元的に爆速クリア
// dp[現在地][目的地][目標時刻インデックス]
static int dp[47][47][21];
std::fill((int*)dp, (int*)dp + 47 * 47 * 21, -2000000000);
for (int i = 0; i < e8_sz; ++i) {
const Flight& f = e8_buf[i];
int start_tidx = max(0, (f.t - 660 + 29) / 30);
if (start_tidx > 20) continue;
int u = f.u, v = f.v, s = f.s, t = f.t;
// dest が自分自身 (v) の場合
for (int tidx = start_tidx; tidx < 21; ++tidx) {
if (s > dp[u][v][tidx]) dp[u][v][tidx] = s;
}
// dest がそれ以外の場合（乗り継ぎ）
for (int dest = 0; dest < N; ++dest) {
if (dest == v) continue;
// 【高速化3】単調性を利用して if 分岐を劇的に減らす
int first_tidx = 21;
for (int tidx = start_tidx; tidx < 21; ++tidx) {
if (dp[v][dest][tidx] >= t) {
first_tidx = tidx; // ここで間に合えば、これ以降も絶対間に合う
break;
}
}
// 見つかった時刻以降を無条件（if無し）で更新
for (int tidx = first_tidx; tidx < 21; ++tidx) {
if (s > dp[u][dest][tidx]) dp[u][dest][tidx] = s;
}
}
}
// 最終的なスコアの集計
for (int dest = 0; dest < N; ++dest) {
for (int src = 0; src < N; ++src) {
if (dist_mat[src][dest] < min_dist) continue;
double weight = (double)W[src] * W[dest];
for (int tidx = 0; tidx < 21; ++tidx) {
if (s_square[src][dest][tidx] < dp[src][dest][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 double threshold, const double progress) {
is_valid = true;
changed.pre_score = score;
// {Type0(シフト), Type1(末尾削除), Type2(末尾追加), Type3(再構築), Type4(賢い架け替え), Type5(ショートカット)}
vector<double> w_start = {15, 15, 15, 20, 20, 15};
vector<double> w_end = {30, 5, 15, 0, 30, 20};
vector<double> w(6);
double w_sum = 0;
rep(i, 6) {
w[i] = w_start[i] * (1.0 - progress) + w_end[i] * progress;
w_sum += w[i];
}
double r = (sa::sarnd.randrange(10000) / 10000.0) * w_sum;
double cur_w = 0;
changed.type = 5;
rep(i, 6) {
cur_w += w[i];
if (r <= cur_w) {
changed.type = i;
break;
}
}
// --------------------------
changed.p = sa::sarnd.randrange(K);
changed.old_flights = planes[changed.p];
int p = changed.p;
if (changed.type == 0) {
/* Type 0: シフト */
if (planes[p].empty()) { is_valid = false; }
else {
int idx = sa::sarnd.randrange(planes[p].size());
int shift = (sa::sarnd.randrange(7) - 3) * 5;
if (shift == 0) is_valid = false;
else {
int new_s = planes[p][idx].s + shift;
int new_t = planes[p][idx].t + shift;
int prev_t = (idx == 0) ? MIN_TIME : planes[p][idx - 1].t;
int next_s = (idx + 1 == (int)planes[p].size()) ? MAX_TIME : planes[p][idx + 1].s;
if (new_s >= prev_t && new_t <= next_s && new_t <= MAX_TIME) {
planes[p][idx].s = new_s; planes[p][idx].t = new_t;
} else is_valid = false;
}
}
}
else if (changed.type == 1) {
/* Type 1: 末尾削除 */
if (planes[p].empty()) is_valid = false;
else {
int del_cnt = 1 + sa::sarnd.randrange(min(3, (int)planes[p].size()));
rep(i, del_cnt) planes[p].pop_back();
}
}
else if (changed.type == 2) {
/* Type 2: 末尾追加 */
int cur_t = MIN_TIME; int cur_l = sa::sarnd.randrange(N);
if (!planes[p].empty()) { cur_t = planes[p].back().t; cur_l = planes[p].back().v; }
int nxt_l = sa::sarnd.randrange(N); if (nxt_l == cur_l) nxt_l = (nxt_l + 1) % N;
int base_st = ((cur_t + 4) / 5) * 5; int st = base_st + sa::sarnd.randrange(4) * 5;
int dur = req_time_mat[cur_l][nxt_l];
if (st + dur <= MAX_TIME) planes[p].push_back({cur_l, nxt_l, st, st + dur});
else is_valid = false;
}
else if (changed.type == 3) {
/* Type 3: 部分再構築 */
if (planes[p].empty()) is_valid = false;
else {
int keep = sa::sarnd.randrange(planes[p].size());
planes[p].resize(keep);
int cur_t = MIN_TIME; int cur_l = sa::sarnd.randrange(N);
if (keep > 0) { cur_t = planes[p].back().t; cur_l = planes[p].back().v; }
int add_cnt = 1 + sa::sarnd.randrange(3);
rep(step, add_cnt) {
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 base_st = ((cur_t + 4) / 5) * 5;
if (base_st + dur > MAX_TIME) continue;
double eval = (double)W[cur_l] * W[nxt] / dur;
eval *= (1.0 + sa::sarnd.randrange(100) / 200.0);
if (chmax(best_eval, eval)) best_nxt = nxt;
}
if (best_nxt != -1) {
int base_st = ((cur_t + 4) / 5) * 5;
int st = base_st + sa::sarnd.randrange(3) * 5;
int dur = req_time_mat[cur_l][best_nxt];
if (st + dur <= MAX_TIME) {
planes[p].push_back({cur_l, best_nxt, st, st + dur});
cur_t = st + dur; cur_l = best_nxt;
} else break;
} else break;
}
}
}
else if (changed.type == 4) {
/* 【新規】 Type 4: 賢い中間架け替え (Greedy Replace) */
if (planes[p].size() < 2) {
is_valid = false;
} else {
int idx = sa::sarnd.randrange(planes[p].size() - 1);
int u = planes[p][idx].u;
int old_v = planes[p][idx].v;
int w = planes[p][idx+1].v;
int best_new_v = -1;
double best_eval = -1.0;
int st1 = planes[p][idx].s;
int next_s = (idx + 2 == (int)planes[p].size()) ? MAX_TIME : planes[p][idx + 2].s;
// 時間内に収まる中で最も需要が高い中継地を探す
rep(new_v, N) {
if (new_v == u || new_v == old_v || new_v == w) continue;
int dur1 = req_time_mat[u][new_v];
int dur2 = req_time_mat[new_v][w];
int st2 = ((st1 + dur1 + 4) / 5) * 5;
if (st2 + dur2 <= next_s && st2 + dur2 <= MAX_TIME) {
double eval = (double)W[u] * W[new_v] / dur1 + (double)W[new_v] * W[w] / dur2;
eval *= (1.0 + sa::sarnd.randrange(100) / 200.0); // 乱数で揺らす
if (chmax(best_eval, eval)) {
best_new_v = new_v;
}
}
}
if (best_new_v == -1) {
is_valid = false;
} else {
int dur1 = req_time_mat[u][best_new_v];
int dur2 = req_time_mat[best_new_v][w];
int st2 = ((st1 + dur1 + 4) / 5) * 5;
planes[p][idx].v = best_new_v;
planes[p][idx].t = st1 + dur1;
planes[p][idx+1].u = best_new_v;
planes[p][idx+1].s = st2;
planes[p][idx+1].t = st2 + dur2;
}
}
}
else if (changed.type == 5) {
/* 【新規】 Type 5: ショートカット（1点削除・直結） */
if (planes[p].size() < 2) {
is_valid = false;
} else {
int idx = sa::sarnd.randrange(planes[p].size() - 1);
int u = planes[p][idx].u;
int w = planes[p][idx+1].v;
if (u == w) {
// A -> B -> A のような往復便だった場合は両方とも消して大きな空き時間を作る
planes[p].erase(planes[p].begin() + idx, planes[p].begin() + idx + 2);
} else {
// A -> B -> C を A -> C に直結させる
int st = planes[p][idx].s;
int dur = req_time_mat[u][w];
int next_s = (idx + 2 == (int)planes[p].size()) ? MAX_TIME : planes[p][idx + 2].s;
if (st + dur <= next_s && st + dur <= MAX_TIME) {
planes[p][idx].v = w;
planes[p][idx].t = st + dur;
planes[p].erase(planes[p].begin() + idx + 1);
} else {
is_valid = false;
}
}
}
}
if (!is_valid) {
rollback();
} else {
score = calc_eval();
}
}
void rollback() {
planes[changed.p] = changed.old_flights;
score = changed.pre_score;
}
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 = 970;
sa::State best_state = sa::sa_run(TL, false);
best_state.print();
ll final_score = (ll)(1000000 * (-best_state.get_score()));
cerr << "Score = " << final_score*100 << endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout << fixed << setprecision(3);
cerr << fixed << setprecision(3);
input();
solve();
return 0;
}