| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1068393 | Arapak | Overtaking (IOI23_overtaking) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// Author: Kajetan Ramsza
#include "overtaking.h"
#include "bits/stdc++.h"
using namespace std;
#ifdef DEBUG
#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;
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;
}