| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1220933 | PotatoMan | Overtaking (IOI23_overtaking) | C++17 | 0 ms | 0 KiB |
#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Bus {
ll arrivalTime;
ll pace;
int id;
};
bool byArrivalThenPace(const Bus &a, const Bus &b) {
if (a.arrivalTime == b.arrivalTime) return a.pace < b.pace;
return a.arrivalTime < b.arrivalTime;
}
vector<Bus> buses;
vector<ll> stations;
int N, M;
vector<ll> arrivalTimes_station[1005];
ll computeExpectedArrival(const Bus& b, int j) {
return b.arrivalTime + (stations[j] - stations[j - 1]) * b.pace;
}
void init(int Lp, int Np, vector<ll> Tp, vector<int> Wp, int Xp, int Mp, vector<int> Sp) {
buses.clear();
stations = Sp;
// Keep only buses with pace >= reserve pace Xp (Filtering)
for (int i = 0; i < Np; i++) {
if (Wp[i] >= Xp)
buses.push_back({Tp[i], Wp[i], i});
}
// Add reserve bus
buses.push_back({0, Xp, Np});
N = (int)buses.size();
M = Mp;
// Simulate station by station
for (int j = 1; j < M; j++) {
sort(buses.begin(), buses.end(), byArrivalThenPace);
ll curMax = 0;
vector<ll> arrivalTimes;
for (int i = 0; i < N; i++) {
ll expected = computeExpectedArrival(buses[i], j);
buses[i].arrivalTime = max(expected, curMax);
curMax = max(curMax, buses[i].arrivalTime);
arrivalTimes.push_back(buses[i].arrivalTime);
}
arrivalTimes_station[j] = arrivalTimes;
}
}
ll arrival_time(ll Y, int Xp) {
ll arrival = Y;
ll pace = Xp;
for (int j = 1; j < M; j++) {
const vector<ll>& arrTimes = arrivalTimes_station[j];
// Find first bus arriving strictly after current arrival
int pos = upper_bound(arrTimes.begin(), arrTimes.end(), arrival) - arrTimes.begin();
// Blocking bus arrival time is last bus arriving <= current arrival
ll blockingArrival = (pos == 0) ? 0 : arrTimes[pos - 1];
ll dist = stations[j] - stations[j - 1];
arrival = max(arrival + dist * pace, blockingArrival);
}
return arrival;
}