Submission #1025857

#	Time	Username	Problem	Language	Result	Execution time	Memory
1025857		Gray	Overtaking (IOI23_overtaking)	C++17	65 / 100	3507 ms	41272 KiB

overtaking

#include "overtaking.h"
#include <algorithm>
#include <iostream>
#include <vector>
#define ll long long
#define ff first
#define ss second
#define ln "\n"
#define pll pair<ll, ll>
using namespace std;

ll L, n, x, m;
vector<ll> leave;
vector<ll> speed;
vector<ll> stat;
vector<vector<ll>> t;
vector<vector<ll>> ord;


void simulate(){
    for (ll i=0; i<m; i++){
        for (ll j=0; j<n; j++){
            ord[i][j]=j;
        }
    }
    for (ll i=0; i<n; i++){
        t[0][i]=leave[i];
    }
    sort(ord[0].begin(), ord[0].end(), [&](ll bus1, ll bus2)->bool{
        if (t[0][bus1]!=t[0][bus2]) return t[0][bus1]<t[0][bus2];
        return speed[bus1]<speed[bus2];
    });
    for (ll i=1; i<m; i++){
        for (ll j=0; j<n; j++){
            t[i][j]=t[i-1][j]+speed[j]*(stat[i]-stat[i-1]);
        }
        for (ll j=1; j<n; j++){
            t[i][ord[i-1][j]]=max(t[i][ord[i-1][j]], t[i][ord[i-1][j-1]]);
        }
        sort(ord[i].begin(), ord[i].end(), [&](ll bus1, ll bus2)->bool{
            if (t[i][bus1]!=t[i][bus2]) return t[i][bus1]<t[i][bus2];
            return speed[bus1]<speed[bus2];            
        });
    }
}

void init(int _L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S)
{
    L=_L; n=N; x=X; m=M;
    t.resize(m, vector<ll>(n));
    ord.resize(m, vector<ll>(n));
    leave = T;
    leave.push_back(0);
    speed.resize(n);
    stat.resize(m);
    for (ll i=0; i<n; i++) {speed[i]=W[i];}
    for (ll i=0; i<m; i++) {stat[i]=S[i];}
    simulate();
    // for (ll i=0; i<m; i++){
    //     for (ll j=0; j<n; j++) cout << t[i][j] << " ";
    //     cout << ln;
    // }
}


long long arrival_time(long long Y)
{
    // return 0;
    ll time=Y, ordi;
    ll l=-1, r=n;
    while (l+1<r){
        ll mid = (l+r)/2;
        if (t[0][ord[0][mid]]>time or (t[0][ord[0][mid]]==time and speed[ord[0][mid]]>=x)) r=mid;
        else l=mid;
    }
    ordi=r;
    // return ordi;
    for (ll i=1; i<m; i++){
        time += (stat[i]-stat[i-1])*x;
        if (ordi) time = max(time, t[i][ord[i][ordi-1]]);
        l=-1, r=ordi;
        while (l+1<r){
            ll mid = (l+r)/2;
            if (t[i][ord[i][mid]]>time or (t[i][ord[i][mid]]==time and speed[ord[i][mid]]>=x)) r=mid;
            else l=mid;
        }
        ordi=r;
    }
    return time;
}

• Subtask 0: 0 / 0
• Subtask 1: 9 / 9
• Subtask 2: 10 / 10
• Subtask 3: 20 / 20
• Subtask 4: 26 / 26
• Subtask 5: 0 / 35