Submission #1068397

#	Time	Username	Problem	Language	Result	Execution time	Memory
1068397		Arapak	Overtaking (IOI23_overtaking)	C++17	65 / 100	3533 ms	48976 KiB

overtaking

// Author: Kajetan Ramsza
#include "overtaking.h"
#include "bits/stdc++.h"
using namespace std;

#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)x.size()
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int,int> pii;

#ifdef DEBUG
auto& operator<<(auto &os, const pair<auto, auto> &p) {
    return os<<"("<<p.first<<", "<<p.second<<")";
}
auto& operator<<(auto &os, const auto &v) {
    os<<"{";
    for(auto it=begin(v);it!=end(v);++it) {
        if(it!=begin(v)) os<<", ";
        os<<(*it);
    }
    return os<<"}";
}

void dbg_out(auto... x) {
    ((cerr<<' '<<x), ...) << endl;
}
#define dbg(x...) cerr<<"("<<#x<<"):", dbg_out(x);
#else
#define dbg(...)
#endif

struct BusState {
    ll arrival_time;
    int bus_index;
    ll next_arrival = -1;

    friend ostream& operator<<(ostream &os, const BusState &bs) {
        return os<<"{arr: "<<bs.arrival_time<<" ind: "<<bs.bus_index<<" next: "<<bs.next_arrival<<"}";
    }
};

int l, n, m;
vll t;
vi s, w;

vector<vector<BusState>> state;

ll get_expected_next_arrival(ll arrival, ll speed, int s_ind) {
    return arrival + speed * ll(s[s_ind+1] - s[s_ind]);
}

void calc_next_arrival(int index) {
    dbg(index);
    assert(0 <= index && index < m);
    auto &st = state[index];
    sort(all(st), [](const auto &a, const auto &b) {
        return a.arrival_time < b.arrival_time;
    });

    int prev = -1;
    rep(i,0,n) {
        ll expected_next_arrival = get_expected_next_arrival(st[i].arrival_time, w[st[i].bus_index], index); 
        if(i > 0 && st[i-1].arrival_time != st[i].arrival_time) {
            rep(j,prev+1,i)
                if(prev == -1 || st[j].next_arrival > st[prev].next_arrival)
                    prev = j;
        }

        if(prev == -1) 
            st[i].next_arrival = expected_next_arrival;
        else 
            st[i].next_arrival = max(expected_next_arrival, st[prev].next_arrival);
    }

    sort(all(state[index]), [](const auto &a, const auto &b) {
        return tie(a.arrival_time, a.next_arrival) < tie(b.arrival_time, b.next_arrival);
    });
}

void preprocess() {
    state.assign(m, vector<BusState>(n));
    rep(i,0,n) state[0][i] = {t[i], i, -1};
    rep(s_ind,0,m-1) {
        calc_next_arrival(s_ind);
        rep(i,0,n) 
            state[s_ind+1][i] = {state[s_ind][i].next_arrival, state[s_ind][i].bus_index, -1};
    }
}

int X;

void init(int L, int N, vll T,  vi W, int _X, int M, vi S) {
    l = L;
    n = N;
    t = T;
    w = W;
    X = _X;
    m = M;
    s = S;
    dbg(l, n, m);
    preprocess();
    rep(i,0,m) dbg(state[i]);
}

ll find_worst_next_arrival(int s_ind, ll arrival) {
    int b = 0, e = n;
    while(b < e) {
        int mid = (b+e) / 2;
        if(state[s_ind][mid].arrival_time < arrival)
            b = mid + 1;
        else e = mid;
    }
    return b == 0 ? -1 : state[s_ind][b-1].next_arrival;
}

ll arrival_time(ll Y) {
    dbg(X, Y);
    rep(s_ind,0,m-1) {
        ll expected_next_arrival = get_expected_next_arrival(Y, X, s_ind);
        ll worst_next_arrival = find_worst_next_arrival(s_ind, Y);
        dbg(s_ind, expected_next_arrival, worst_next_arrival);
        Y = max(expected_next_arrival, worst_next_arrival);
    }
    return Y;
}

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