Submission #1220951

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220951		PotatoMan	Overtaking (IOI23_overtaking)	C++17	0 / 100	0 ms	328 KiB

overtaking

#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

struct Bus {
    ll t, w;
    int id;
};

bool cmp(const Bus &a, const Bus &b) {
    if (a.t == b.t) return a.w < b.w;
    return a.t < b.t;
}

int N, M;
vector<int> stations;
vector<Bus> buses, buses_init;
vector<ll> arrTimes_station[1005];

ll dist(int i) {
    return stations[i] - stations[i - 1];
}

ll compute(ll t, ll w, int j) {
    return t + dist(j) * w;
}

void init(int Lp, int Np, vector<ll> Tp, vector<int> Wp, int Xp, int Mp, vector<int> Sp) {
    buses.clear();
    stations = Sp;

    for (int i = 0; i < Np; i++) {
        if (Wp[i] >= Xp) buses.push_back({Tp[i], Wp[i], i});
    }

    buses.push_back({0, (ll)Xp, Np});
    N = (int)buses.size();
    M = Mp;

    buses_init = buses;

    for (int j = 1; j < M; j++) {
        sort(buses.begin(), buses.end(), cmp);
        ll curMax = 0;
        arrTimes_station[j].clear();
        arrTimes_station[j].reserve(N);

        for (int i = 0; i < N; i++) {
            ll expected = compute(buses[i].t, buses[i].w, j);
            buses[i].t = max(expected, curMax);
            curMax = max(curMax, buses[i].t);
            arrTimes_station[j].push_back(buses[i].t);
        }
    }
}

ll arrival_time(ll Y) {
    buses = buses_init;

    ll arrival = Y, pace = 0;
    for (auto &b : buses) {
        if (b.id == N - 1) {
            b.t = Y;
            pace = b.w;
            break;
        }
    }

    for (int j = 1; j < M; j++) {
        auto &arr = arrTimes_station[j];
        int pos = (int)(upper_bound(arr.begin(), arr.end(), arrival) - arr.begin());
        ll block = (pos == 0) ? 0 : arr[pos - 1];
        arrival = max(arrival + dist(j) * pace, block);

        for (auto &b : buses) {
            if (b.id == N - 1) {
                b.t = arrival;
                break;
            }
        }
    }

    for (auto &b : buses)
        if (b.id == N - 1) return b.t;

    return -1;
}

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