Submission #841472

#	Time	Username	Problem	Language	Result	Execution time	Memory
841472		model_code	Overtaking (IOI23_overtaking)	C++17	9 / 100	1 ms	212 KiB

overtaking

// correct/GA_st1.cpp

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

using namespace std;
using ll = long long;

vector<ll> endpoints;
ll total_time;

void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S)
{
    total_time = L * (ll)X;
    for (int i = 0; i < M; i++)
    {
        endpoints.push_back(T[0] + (W[0] - X) * (ll)S[i]);
    }
}

long long arrival_time(long long Y)
{
    // If W[0] < X, then endpoints is decreasing, so the call to lower_bound is UB.
    // However, it happens to return either begin() or end(), giving the correct answer.
    auto it = lower_bound(endpoints.begin(), endpoints.end(), Y);
    if (it == endpoints.begin() || it == endpoints.end())
    {
        return Y + total_time;
    }
    else
    {
        return *it + total_time;
    }
}

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