Submission #847674

#	Time	Username	Problem	Language	Result	Execution time	Memory
847674		belgianbot	Overtaking (IOI23_overtaking)	C++17	0 / 100	1 ms	348 KiB

overtaking

#include "overtaking.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;

vector<int> W, S;
vector<long long> T;
int L, N, X, M;
void init(int LL, int NN, std::vector<long long> TT, std::vector<int> WW, int XX, int MM, std::vector<int> SS)
{
    L = LL; N = NN; X = XX; M = MM;
    T = TT;
    W = WW; S = SS;
    return;
}

struct bus{
    int w, n;
    long long t;
    bool operator <(const bus& a) const{
        return (t < a.t || (a.t == t && w < a.w));
    }
     bool operator >(const bus& a) const{
        return (t > a.t || (a.t == t && w > a.w));
    }
};
long long arrival_time(long long Y)
{
    long long ans(Y);
    priority_queue< bus, vector<bus>, greater<bus> >q;
    for (int i(0); i < N; i++) {
        if (T[i] < Y) {
            if (W[i] > X) {
                bus a;
                a.w = W[i];
                a.t = T[i];
                a.n = i;
                q.push(a);
            }
        }
    }
    for (int i(1); i < M; i++) {
        vector< int > blocked(N);
        vector< bus > next;
        if (q.empty()){
            if (i == 1) ans += S[1] * X;
            ans += (S[M - 1] - S[i]) * X;
            break;
        }
        bus a = q.top(); q.pop();
        long long latest(a.t + (S[i] - S[i - 1]) * a.w);
        int blocking = a.n;
        blocked[a.n] = a.n;
        a.t = latest;
        next.push_back(a);
        while (!q.empty()) {
            a = q.top(); q.pop();
            if (a.t + (S[i] - S[i - 1]) * a.w <= latest) {
                blocked[a.n] = blocking;
            }
            else {
                latest = a.t + (S[i] - S[i - 1]) * a.w;
                blocking = a.n;
                blocked[a.n] = a.n;
            }
            a.t = latest;
            next.push_back(a);
        }
        int overtoken(N);
        if (ans + (S[i] - S[i - 1]) * X <= latest) {
            overtoken = blocking;
            ans = latest;
        }
        else ans += (S[i] - S[i - 1]) * X;
        for (bus j : next) {
            if (blocked[j.n] != overtoken) q.push(j);
        }
        
    }
    return ans;
}

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