Submission #1244303

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244303		hugo_pm	Overtaking (IOI23_overtaking)	C++20	9 / 100	1 ms	584 KiB

overtaking

#include "overtaking.h"
#include <bits/stdc++.h>
#define int long long
using namespace std;
using i32 = int32_t;
using pii = pair<int, int>;

struct Bus {
    int time, inv_speed, id_bus;
    auto operator<=>(const Bus&) const = default;
};

int ceildiv(int x, int y) {
    assert(y > 0);
    return (x+y-1)/y;
}
class DemiDroiteMgr {
    const int pente_reserve;
    vector<Bus> dds;
    int nbDroites;

    public:
    DemiDroiteMgr(const vector<Bus> &__dds, int __pente_reserve) :
        pente_reserve(__pente_reserve), dds(__dds) {
        nbDroites = dds.size();
        sort(dds.begin(), dds.end());
    }
    /// returns {ceil(dpos of next int), bus}
    optional<pii> first_intersected_bus(int temps_reserve) {
        optional<pii> best;
        for (auto &dd : dds) {
            if (dd.time < temps_reserve) {
                assert(dd.inv_speed - pente_reserve > 0);
                int cdpos = ceildiv(
                    temps_reserve - dd.time,
                    dd.inv_speed - pente_reserve
                );
                if (!best.has_value() || cdpos < best->first) {
                    best = {cdpos, dd.id_bus};
                }
            }
        }
        return best;
    }
};

int nb_bus, nb_stations, inv_speed_reserve;
vector<Bus> initial_buses;
vector<int> stations;

void make_table();
void init(i32, i32 N, std::vector<long long> T, std::vector<i32> W, i32 X, i32, std::vector<i32> S)
{
    for (int i = 0; i < N; ++i) {
        if (W[i] > X)
            initial_buses.push_back({T[i], W[i], i});
    }
    stations = vector<int>(S.begin(), S.end());
    nb_bus = initial_buses.size(), nb_stations = stations.size();
    inv_speed_reserve = X;
    make_table();
}

vector<DemiDroiteMgr> help_find_next_intersection;
/// table[i_station][i_bus] = time at which the bus gets to the station
vector<vector<int>> table;

void make_table() {
    auto push_row = [] (const vector<Bus> &cur_buses) {
        table.push_back(vector<int>(nb_bus));
        for (const auto &bus : cur_buses) {
            table.back()[bus.id_bus] = bus.time;
        }
        help_find_next_intersection.emplace_back(cur_buses, inv_speed_reserve);
    };
    vector<Bus> cur_buses = initial_buses;
    push_row(cur_buses);
    for (int i_sta = 0; i_sta < nb_stations - 1; ++i_sta) {
        int dis = stations[i_sta+1] - stations[i_sta];
        sort(cur_buses.begin(), cur_buses.end());
        int i_earlier = 0, max_earl = 0;
        vector<Bus> nxt_buses;
        for (int i_time = 0; i_time < nb_bus; ++i_time) {
            const auto& [cur_time, inv_speed, id_bus] = cur_buses[i_time];
            while (i_earlier < i_time && cur_buses[i_earlier].time < cur_time) {
                max_earl = max(nxt_buses[i_earlier++].time, max_earl);
            }
            int nxt_time = max(cur_time + inv_speed * dis, max_earl);
            nxt_buses.push_back({nxt_time, inv_speed, id_bus});
        }
        push_row(nxt_buses);
        cur_buses = nxt_buses;
    }
}

struct Position {
    int station, time;
};

Position next_pos(Position cur) {
    Position if_no_inter = {
        nb_stations - 1,
        cur.time + (stations.back() - stations[cur.station]) * inv_speed_reserve
    };
    
    auto nx = help_find_next_intersection[cur.station].first_intersected_bus(cur.time);
    if (!nx.has_value())
        return if_no_inter;
    auto [ceil_delta_pos, crossed_bus] = *nx;
    int ceil_abspos = stations[cur.station] + ceil_delta_pos; 
    auto it = lower_bound(stations.begin(), stations.end(), ceil_abspos);
    Position nxt;
    nxt.station = it - stations.begin();
    if (nxt.station > nb_stations-1)
        return if_no_inter;
    nxt.time = table[nxt.station][crossed_bus];
    return nxt;
}

long long arrival_time(long long dep_time_reserve) {
    Position cur {0, dep_time_reserve};
    while (cur.station != nb_stations-1) {
        cur = next_pos(cur);
    }
    return cur.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