Submission #855931

#	Time	Username	Problem	Language	Result	Execution time	Memory
855931		Sorting	Overtaking (IOI23_overtaking)	C++17	39 / 100	3551 ms	123752 KiB

overtaking

#include "overtaking.h"
#include <algorithm>
#include <map>
#include <numeric>

using namespace std;
typedef long long ll;

const int N = 1000 + 3;

ll dp[N][N];
int n, m;
ll t[N], w[N], s[N], l, x;

map<ll, vector<int>> groups[N];
ll time_at_sorting[N][N];

void reorder_buses(){
    int new_n = n;
    for(int i = 0; i < new_n; ++i){
        if(w[i] <= x){
            --new_n;
            swap(w[i], w[new_n]);
            swap(t[i], t[new_n]);
            --i;
        }
    }
    n = new_n;

    vector<int> perm(n);
    iota(perm.begin(), perm.end(), 0);

    sort(perm.begin(), perm.end(), [&](int l, int r){
        if(w[l] != w[r])
            return w[l] < w[r];
        return t[l] < t[r];
    });

    static ll tmp[N];
    copy(t, t + n, tmp);
    for(int i = 0; i < n; ++i){
        t[i] = tmp[perm[i]];
    }
    copy(w, w + n, tmp);
    for(int i = 0; i < n; ++i){
        w[i] = tmp[perm[i]];
    }
}

void init_groups(){
    for(int i = 0; i < n; ++i){
        time_at_sorting[0][i] = t[i];
        groups[0][t[i]].push_back(i);
    }

    for(int station = 1; station < m; ++station){
        vector<int> order;
        for(auto &[time, v]: groups[station - 1]){
            for(int x: v){
                order.push_back(x);
            }
        }

        for(int i = 0; i < n; ++i){
            time_at_sorting[station][i] = time_at_sorting[station - 1][i] + (s[station] - s[station - 1]) * w[i];
        }

        ll max_so_far = 0;
        for(int x: order){
            max_so_far = max(max_so_far, time_at_sorting[station][x]);
            time_at_sorting[station][x] = max_so_far;
            groups[station][max_so_far].push_back(x);
        }

        for(auto &[time, buses]: groups[station]){
            sort(buses.begin(), buses.end());
        }
    }
}

void init_buses(){
    reorder_buses();
    init_groups();
}

ll calc_time(int station, ll time){
    if(station == m - 1){
        return time;
    }

    auto iter = groups[station].lower_bound(time);
    if(iter == groups[station].begin()){
        return (s[m - 1] - s[station]) * x + time;
    }

    --iter;
    int bus = iter->second.back();

    ll next_time = (s[station + 1] - s[station]) * x + time;
    if(next_time > time_at_sorting[station + 1][bus]){
        return calc_time(station + 1, next_time);
    }
    return dp[station + 1][bus];

    /*int l = station + 1, r = m;
    while(l != r){
        int mid = (l + r) >> 1;
        
        ll time_at_mid = (s[mid] - s[station]) * x + time;
        if(time_at_sorting[mid][bus] >= time_at_mid){
            r = mid;
        }
        else{
            l = mid + 1;
        }
    }

    int next_station = l;
    if(next_station == m){
        return (s[m - 1] - s[station]) * x + time;
    }

    return dp[next_station][bus];*/
}

void calc_dp(){
    for(int station = m - 1; station >= 0; --station){
        if(station == m - 1){
            for(int i = 0; i < n; ++i){
                dp[station][i] = time_at_sorting[station][i];
            }
            continue;
        }

        for(int i = 0; i < n; ++i){
            dp[station][i] = calc_time(station, time_at_sorting[station][i]);
        }
    }
}

void init(int L, int N, vector<long long> T, vector<int> W, int X, int M, vector<int> S)
{
    l = L, n = N, x = X, m = M;
    copy(T.begin(), T.end(), t);
    copy(W.begin(), W.end(), w);
    copy(S.begin(), S.end(), s);

    init_buses();
    calc_dp();
}

ll arrival_time(ll Y)
{
    return calc_time(0, Y);
}

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