Submission #1220887

#TimeUsernameProblemLanguageResultExecution timeMemory
1220887PotatoManOvertaking (IOI23_overtaking)C++17
0 / 100
0 ms324 KiB
#include "overtaking.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; struct Bus { ll departureTime; ll pace; ll id; }; bool byDepartureTime(Bus b1,Bus b2){ if( b1.departureTime == b2.departureTime ){ return b1.pace < b2.pace; } return b1.departureTime < b2.departureTime; } vector<Bus> bus; // Buses vector<ll> S; // Stations ll N,M; int computeExpArrival(const Bus& b, int stationIndex) { int distance = S[stationIndex] - S[stationIndex - 1]; return b.departureTime + distance * b.pace; } void init(int Lp, int Np, std::vector<long long> Tp, std::vector<int> Wp, int X, int Mp, std::vector<int> Sp) { // Load regular bus data for(int i = 0 ; i < N ; i++){ bus.push_back({Wp[i],Tp[i],i}); } // Load reserve bus data (ID = N) bus.push_back({X,-1,Np}); // Load station data for(int i = 0 ; i < Mp ; i++){ S.push_back(Sp[i]); } // Assign N and M N = bus.size(); M = S.size(); } ll arrival_time(ll Y) { // Set reserve bus departure time for (auto &b : bus) { if (b.id == N) b.departureTime = Y; } // Simulate station-by-station for (int j = 1; j < M; j++) { sort(bus.begin(), bus.end(), byDepartureTime); ll curMax = 0; for (int i = 0; i < bus.size(); i++) { ll exp = computeExpArrival(bus[i], j); bus[i].departureTime = max(exp, curMax); curMax = max(curMax, bus[i].departureTime); } } // Return final arrival time of the reserve bus (id == N) for (auto &b : bus) { if (b.id == N) return b.departureTime; } // This should never happen return -1; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...