Submission #1234603

#	Time	Username	Problem	Language	Result	Execution time	Memory
1234603		ericl23302	Overtaking (IOI23_overtaking)	C++20	10 / 100	1 ms	328 KiB

overtaking

#include "overtaking.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

vector<ll> starts, speeds, stations;
vector<vector<pair<ll, int>>> expected;
vector<vector<ll>> expectedFind;
ll length, n, m, speed;


void calcLayer(int layer) {
    vector<pair<ll, int>> &prev = expected[layer - 1], &cur = expected[layer];
    sort(prev.begin(), prev.end(), [](const pair<ll, int> a, const pair<ll, int> b) {
        if (a.first == b.first) return speeds[a.second] < speeds[b.second];
        return a.first < b.first;
    });
    ll prevReach = 0, prevArrive2 = 0, prevReach2 = 0, dist = stations[layer] - stations[layer - 1];
    for (auto &[arrive, idx] : prev) {
        ll curReach = arrive + speeds[idx] * dist;
        if (arrive == prevArrive2) curReach = max(curReach, prevReach);
        else curReach = max(curReach, prevReach2);

        cur.emplace_back(curReach, idx);
        expectedFind[layer][idx] = curReach;

        if (arrive == prevArrive2) prevReach2 = max(prevReach2, curReach);
        else prevReach = prevReach2, prevArrive2 = arrive, prevReach2 = curReach;
    }
}

void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S)
{
    length = L; 
    m = M;
    starts = T;
    speed = X;
    for (auto &i : W) {
        // if (i <= speed) continue;
        speeds.push_back(i);
    }
    n = speeds.size();
    for (auto &i : S) stations.push_back(i);

    expected.resize(m);
    expected[0].resize(n);
    expectedFind.resize(m, vector<ll>(n, 0));
    for (int i = 0; i < n; ++i) expected[0][i] = {starts[i], i}, expectedFind[0][i] = starts[i];
    for (int i = 1; i < m; ++i) calcLayer(i);

    // for (int i = 0; i < m; ++i) {
    //     cout << "LAYER: " << i << endl;
    //     for (auto j : expected[i]) cout << j.first << ' ' << j.second << "   ";
    //     cout << endl;
    //     for (auto j : expectedFind[i]) cout << j << ' ';
    //     cout << endl;
    // }
}

long long arrival_time(long long Y)
{
    if (n == 1) return (Y + speed * length);
    ll cur = Y;
    for (int i = 1; i < m; ++i) {
        auto which = lower_bound(expected[i - 1].begin(), expected[i - 1].end(), make_pair(cur, -1));
        if (which == expected[i - 1].begin()) return (cur + speed * (stations[m - 1] - stations[i - 1]));
        int idx = prev(which)->second;
        cur += speed * (stations[i] - stations[i - 1]);
        cur = max(cur, expectedFind[i][idx]);
    }

    return cur;
}

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