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

• 問題: No.5023 Airlines Optimization
• ユーザー: FplusFplusF
• 提出日時: 2026-02-25 21:44:55
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 3 ms / 1,000 ms
• コード長: 4,198 bytes
• コンパイル時間: 4,714 ms
• コンパイル使用メモリ: 357,056 KB
• 実行使用メモリ: 7,848 KB
• スコア: 10,628,261
• 最終ジャッジ日時: 2026-02-25 21:45:05
• 合計ジャッジ時間: 9,699 ms
• ジャッジサーバーID （参考情報）: judge3 / judge6

ファイルパターン	結果
other	AC * 100

ソースコード

#include <bits/stdc++.h>
using namespace std;
using pii=pair<int,int>;
using tii=tuple<int,int,int>;
using qii=tuple<int,int,int,int>;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
constexpr int INF=1e9;
constexpr ll INF_ll=1e18;
#define rep(i,n) for (int i=0;i<(int)(n);i++)
#define replr(i,l,r) for (int i=(int)(l);i<(int)(r);i++)
#define all(v) v.begin(),v.end()
#define len(v) ((int)v.size())
template<class T> inline bool chmin(T &a,const T &b){
    if(a>b){
        a=b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T &a,const T &b){
    if(a<b){
        a=b;
        return true;
    }
    return false;
}

namespace Timer{
    chrono::steady_clock::time_point program_start,start;
    void program_start_snap(){
        program_start=start=chrono::steady_clock::now();
    }
    void snap(){
        start=chrono::steady_clock::now();
    }
    int get_ms(){
        auto now=chrono::steady_clock::now();
        int ms=chrono::duration_cast<chrono::milliseconds>(now-start).count();
        return ms;
    }
    int get_ms_all_program(){
        auto now=chrono::steady_clock::now();
        int ms=chrono::duration_cast<chrono::milliseconds>(now-program_start).count();
        return ms;
    }
}

mt19937 mt;
uint32_t rand_int(uint32_t r){  //[0,r)
    assert(r!=0);
    return ((uint64_t)mt()*r)>>32;
}
int rand_int(int l,int r){  //[l,r)
    assert(l<r);
    return l+rand_int(r-l);
}
constexpr double one_div_mt_max=1.0/(double)mt19937::max();
double rand_double(){  //[0.0,1.0]
    return mt()*one_div_mt_max;
}

template<class T> T get_random_element(const vector<T> &v){
    assert(!v.empty());
    return v[rand_int(len(v))];
}

template<class T> void add(vector<T> &a,vector<T> b){
    for(auto i:b) a.push_back(i);
}

constexpr int N=47,R=1000,M=400,K=25;

array<int,N> X,Y,W;

struct Plan{
    int a,b;
    int s,t;
};

array<Plan,M> P;
array<array<int,N>,N> D;

map<int,string> Time_string;

namespace Solver{
    void solve(){
        array<vector<Plan>,K> ans;
        
        rep(k,K){
            int x=rand_int(N),t=6*60;
            while(true){
                vector<int> v;
                rep(i,N){
                    if(i==x) continue;
                    if(21*60<t+D[x][i]) continue;
                    v.push_back(i);
                }
                if(v.empty()) break;
                int nx=get_random_element(v);
                
                ans[k].emplace_back(x,nx,t,t+D[x][nx]);
                
                t+=D[x][nx];
                
                x=nx;
                
            }
        }
        
        rep(k,K){
            cout << len(ans[k]) << '\n';
            
            for(auto plan:ans[k]){
                cout << plan.a+1 << ' ' << Time_string[plan.s] << ' ' << plan.b+1 << ' ' << Time_string[plan.t] << '\n';
            }
        }
        
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    Timer::program_start_snap();
    
    int n,r;
    cin >> n >> r;
    
    assert(n==N);
    assert(r==R);
    
    rep(i,N) cin >> X[i] >> Y[i] >> W[i];
    
    int m;
    cin >> m;
    
    assert(m==M);
    
    rep(i,M){
        int a,b;
        string s,t;
        cin >> a >> s >> b >> t;
        a--;
        b--;
        P[i].a=a;
        P[i].b=b;
        
        int sx=stoi(s.substr(0,2)),sy=stoi(s.substr(3,2));
        int tx=stoi(t.substr(0,2)),ty=stoi(t.substr(3,2));
        
        P[i].s=sx*60+sy;
        P[i].t=tx*60+ty;
        
    }
    
    int k;
    cin >> k;
    
    assert(k==K);
    
    rep(i,N){
        rep(j,N){
            double d=hypot<double>(X[i]-X[j],Y[i]-Y[j]);
            int t=ceil(60*d/800+40);
            while(t%5!=0) t++;
            D[i][j]=t;
        }
    }
    
    
    for(int i=6;i<=21;i++){
        for(int j=0;j<60;j+=5){
            
            string sx=to_string(i),sy=to_string(j);
            
            while(len(sx)<2) sx.insert(sx.begin(),'0');
            while(len(sy)<2) sy.insert(sy.begin(),'0');
            
            Time_string[i*60+j]=sx+":"+sy;
            
            if(i==21) break;
        }
    }
    
    Solver::solve();
    exit(0);
}