#1149405 (C++23) No.5023 Airlines Optimization

• 問題: No.5023 Airlines Optimization
• ユーザー: titan23
• 提出日時: 2026-02-25 23:43:49
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 988 ms / 1,000 ms
• コード長: 35,706 bytes
• コンパイル時間: 9,706 ms
• コンパイル使用メモリ: 411,512 KB
• 実行使用メモリ: 7,844 KB
• スコア: 50,704,130
• 最終ジャッジ日時: 2026-02-25 23:45:44
• 合計ジャッジ時間: 113,664 ms
• ジャッジサーバーID （参考情報）: judge1 / judge3

ファイルパターン	結果
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 (int i = 0; i < (int)(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;
}


struct OPT {
    double a0, a1, a2, a3, a4, a5, a6;
    double b0, b1, b2, b3, b4, b5, b6;
} opt;
// vector<double> wratio = {30, 15, 15, 20, 20, 10,  1};
vector<double> wratio;// = {30, 15, 15, 20, 20, 10,  1};


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;
}

// ==================================================================================
// 構造変更: イベントスイープ用データ
// ==================================================================================

struct FastBitset {
    uint64_t b[16];
    void clear() { for(int i=0; i<16; ++i) b[i] = 0; }
};

double TOTAL_WEIGHT_SUM = 0;
double W_prod[50][50];
vector<pair<int, int>> target_events[182];

void precalc_sweep() {
    TOTAL_WEIGHT_SUM = 0;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            if (i != j && dist_mat[i][j] >= 0.25 * R) {
                W_prod[i][j] = (double)W[i] * W[j];
                TOTAL_WEIGHT_SUM += W_prod[i][j] * 21.0;
            } else {
                W_prod[i][j] = 0.0;
            }
        }
    }

    for (int i = 0; i <= 181; ++i) target_events[i].clear();
    for (int dest = 0; dest < N; ++dest) {
        for (int tidx = 0; tidx < 21; ++tidx) {
            int T = 660 + tidx * 30; // 11:00以降
            int S_idx = (T - 360) / 5;
            if (S_idx >= 0 && S_idx <= 181) {
                target_events[S_idx].push_back({dest, tidx});
            }
        }
    }
}
// ==================================================================================

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];
        }
    }
    precalc_sweep();
}

// 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 = 5e-4, end_temp = 1e-7;
} param;


void sa_init() {
    precalc();
}

// ==================================================================================
struct Changed {
    int TYPE_CNT = 7; // Type 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(1e9);
    }

    void reset_is_valid() { is_valid = true; }
    double get_score() const { return score; }

    double calc_eval(double threshold = 0.0) const {
        static FastBitset current_reach[47];
        for(int i = 0; i < 47; ++i) current_reach[i].clear();

        static int head_arr[182], nxt_arr[2000]; 
        static int head_dep[182], nxt_dep[2000]; 
        static short flight_u[2000], flight_v[2000];
        static FastBitset flight_reach[2000];

        // 各時刻(182段階)のイベントリストを初期化
        for(int i = 0; i <= 181; ++i) {
            head_arr[i] = -1;
            head_dep[i] = -1;
        }

        // 全フライトを時刻ごとのバケツに放り込む（ソート不要）
        int id = 0;
        for (int k = 0; k < K; ++k) {
            for (const auto& f : planes[k]) {
                int arr_idx = (f.t - 360) / 5;
                int dep_idx = (f.s - 360) / 5;
                
                flight_u[id] = f.u;
                flight_v[id] = f.v;
                
                nxt_arr[id] = head_arr[arr_idx];
                head_arr[arr_idx] = id;
                
                nxt_dep[id] = head_dep[dep_idx];
                head_dep[dep_idx] = id;
                
                id++;
            }
        }

        double v_e8 = 0;
        
        // 時間を未来から過去へスイープする
        for (int S = 181; S >= 0; --S) {
            // 1. Target Event: 目的地への要求時刻を有効化
            for (const auto& tg : target_events[S]) {
                int bit_idx = tg.first * 21 + tg.second;
                current_reach[tg.first].b[bit_idx >> 6] |= (1ULL << (bit_idx & 63));
            }
            
            // 2. Departure Event: 出発
            int curr_dep = head_dep[S];
            while (curr_dep != -1) {
                int f_id = curr_dep;
                int u = flight_u[f_id];
                
                for (int i = 0; i < 16; ++i) {
                    // 出発によって新しく獲得した（0から1に反転した）到達性ビットを取得
                    uint64_t flipped = flight_reach[f_id].b[i] & ~current_reach[u].b[i];
                    if (flipped) {
                        current_reach[u].b[i] |= flipped;
                        uint64_t temp = flipped;
                        while (temp) {
                            int bit_pos = __builtin_ctzll(temp);
                            int global_bit = (i << 6) + bit_pos;
                            int dest = global_bit / 21;
                            int tidx = global_bit % 21;
                            
                            // 距離条件を満たすペアのみスコア計算
                            if (W_prod[u][dest] > 0.0) {
                                int real_s = S * 5 + 360;
                                // 反転した瞬間 = 最も遅い出発時刻
                                if (real_s > s_square[u][dest][tidx]) {
                                    v_e8 += W_prod[u][dest];
                                }
                            }
                            temp &= temp - 1; // 処理済みの最下位ビットを消去
                        }
                    }
                }
                curr_dep = nxt_dep[f_id];
            }
            
            // 3. Arrival Event: 到着（到着先の最新状態をフライト側に記録）
            int curr_arr = head_arr[S];
            while (curr_arr != -1) {
                int f_id = curr_arr;
                int v = flight_v[f_id];
                
                for (int i = 0; i < 16; ++i) {
                    flight_reach[f_id].b[i] = current_reach[v].b[i];
                }
                
                curr_arr = nxt_arr[f_id];
            }
        }
        
        return TOTAL_WEIGHT_SUM == 0 ? 0.0 : -(v_e8 / TOTAL_WEIGHT_SUM);
    }

    void modify(const double threshold, const double progress) {
        is_valid = true;
        changed.pre_score = score;

        vector<double> w(7);
        double w_sum = 0;
        rep(i, 7) {
            w[i] = wratio[i];
            w_sum += w[i];
        }

        double r = (sa::sarnd.randrange(10000) / 10000.0) * w_sum;
        double cur_w = 0;
        changed.type = 6;
        rep(i, 7) {
            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) {
            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) {
            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) {
            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) {
            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) {
            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) {
            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) {
                    planes[p].erase(planes[p].begin() + idx, planes[p].begin() + idx + 2);
                } else {
                    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;
                    }
                }
            }
        }
        else if (changed.type == 6) {
            if (planes[p].size() < 2) is_valid = false;
            else {
                int keep = sa::sarnd.randrange(max(1, (int)planes[p].size() / 3));
                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; }

                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 + 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(2) * 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;
                }
            }
        }

        if (!is_valid) {
            rollback();
        } else {
            score = calc_eval(threshold);
        }
    }

    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 = 980;
    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(int argc, char* argv[]) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(3);
    cerr << fixed << setprecision(3);

    wratio.resize(6);
    // wratio[0] = stod(argv[1]);
    // wratio[1] = stod(argv[2]);
    // wratio[2] = stod(argv[3]);
    // wratio[3] = stod(argv[4]);
    // wratio[4] = stod(argv[5]);
    // wratio[5] = stod(argv[6]);
    wratio[0] = 83;
    wratio[1] = 5;
    wratio[2] = 25;
    wratio[3] = 82;
    wratio[4] = 93;
    wratio[5] = 5;
    wratio[6] = 10;

    input();
    solve();

    return 0;
}