Submission #1225316

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225316		LucaIlie	Overtaking (IOI23_overtaking)	C++17	39 / 100	3592 ms	37288 KiB

overtaking

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

using namespace std;

const int MAX_N = 2000;
const int MAX_M = 2000;
const long long INF = 1e18;

struct bus {
    long long t;
    int v;
    int p;
};

int n, m, x;
bus buses[MAX_M][MAX_N];
long long timeByBus[MAX_M][MAX_N];
long long arrivalTime[MAX_M][MAX_N];
int stations[MAX_M];

long long getArrivalTime(int s, long long t) {
    int l = s, r = m;
    while (r - l > 1) {
        int mid = (l + r) / 2;
        long long d = stations[mid] - stations[s];
        bool ok = false;
        for (int i = 0; i < n; i++) {
            int b = buses[s][i].p;
            if (timeByBus[s][b] < t && timeByBus[s][b] + (long long)d * buses[s][i].v >= t + (long long)d * x)
                ok = true;
        }
        if (ok)
            r = mid;
        else
            l = mid;
    }
    // printf("ARRIVAL %d %lld %d %d\n", s, t, r, x);
    if (r == m)
        return t + (long long)x * (stations[m - 1] - stations[s]);

    int bus = 0;
    long long maxx = 0;
    for (int i = 0; i < n; i++) {
        int b = buses[s][i].p;
        if (timeByBus[s][b] < t) {
            if (timeByBus[r][b] > maxx) {
                maxx = timeByBus[r][b];
                bus = b;
            }
        }
    }
    // printf("BUS %d %lld\n", bus, arrivalTime[r][bus]);
    return arrivalTime[r][bus];
}

void init(int L, int N, vector<long long> T, vector<int> W, int X, int M, vector<int> S) {
    n = N;
    m = M;
    x = X;
    for (int i = 0; i < n; i++)
        buses[0][i] = {T[i], W[i], i};
    for (int i = 0; i < m; i++)
        stations[i] = S[i];

    for (int j = 0; j < m - 1; j++) {
        sort(buses[j], buses[j] + n, [](bus a, bus b) {
            if (a.t == b.t)
                return a.v < b.v;
            return a.t < b.t;
        } );

        for (int i = 0; i < n; i++)
            buses[j + 1][i] = buses[j][i];
        for (int i = 0; i < n; i++)
            buses[j + 1][i].t = buses[j][i].t + (long long)buses[j][i].v * (stations[j + 1] - stations[j]);
        for (int i = 1; i < n; i++)
            buses[j + 1][i].t = max(buses[j + 1][i].t, buses[j + 1][i - 1].t);
       // for (int i = 0; i < n; i++)
       //      printf("%lld ", buses[j + 1][i].t);
       //  printf("\n");
    }

    for (int j = 0; j < m; j++) {
        for (int i = 0; i < n; i++)
            timeByBus[j][buses[j][i].p] = buses[j][i].t;
        buses[j][n].t = INF;
    }

    for (int i = 0; i < n; i++)
        arrivalTime[m - 1][buses[m - 1][i].p] = buses[m - 1][i].t;
    for (int j = m - 2; j >= 0; j--) {
        for (int i = 0; i < n; i++)
            arrivalTime[j][buses[j][i].p] = getArrivalTime(j, buses[j][i].t);
    }

    // for (int s = m - 1; s >= 0; s--) {
    //     for (int i = 0; i < n; i++)
    //         printf("%lld ", arrivalTime[s][i]);
    //     printf("\n");
    // }
}

long long arrival_time(long long y) {
    return getArrivalTime(0, y);
}

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