| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 841337 | happypotato | Catfish Farm (IOI22_fish) | 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.
// I am sorry
// I have mega skill issues
#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long // remove when necessary
#define pii pair<int, int>
#define ff first
#define ss second
#define pb push_back
const int mxN = 1001;
int arrive[mxN][mxN]; // [position][car]
int n, m;
int w[mxN], s[mxN];
int x;
map<int, int> mp[mxN];
map<int, int>::iterator it;
map<int, pii> ansmp;
map<int, pii>::iterator it2, it3;
void reset() {
for (int i = 0; i < n; i++) w[i] = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) arrive[i][j] = 0;
s[i] = 0;
mp[i].clear();
}
ansmp.clear();
}
void CalcArrival() {
for (int i = 1; i < m; i++) {
// calculate estimated ending time
for (int j = 0; j < n; j++) {
arrive[i][j] = arrive[i - 1][j] + w[j] * (s[i] - s[i - 1]);
// cerr << arrive[i - 1][j] << " | " << w[j] << " | ";
// cerr << s[i] - s[i - 1] << endl;
// cerr << i << " " << j << ": " << arrive[i][j] << endl;
}
// "delay" faster cars
// // brute force method
// for (int j = 0; j < n; j++) {
// for (int k = 0; k < n; k++) {
// if (j == k) continue;
// if (arrive[i - 1][j] > arrive[i - 1][k] && arrive[i][j] < arrive[i][k]) {
// // j overtook k on the road, delay
// arrive[i][j] = arrive[i][k];
// }
// }
// }
// sort by (estimated) ending time
vector<pair<pii, int>> v;
for (int j = 0; j < n; j++) {
v.pb({{arrive[i][j], arrive[i - 1][j]}, j});
}
sort(v.begin(), v.end(), [&](pair<pii, int> &lhs, pair<pii, int> &rhs) {
// sort by larger arrival time
if (lhs.ff.ff != rhs.ff.ff) return lhs.ff.ff > rhs.ff.ff;
// tiebreak by smaller starting time
return lhs.ff.ss < rhs.ff.ss;
});
for (pair<pii, int> &cur : v) {
it = mp[i].lower_bound(cur.ff.ss);
if (it == mp[i].begin()) {
if (it->ff != cur.ff.ss) mp[i][cur.ff.ss] = cur.ff.ff;
} else {
--it;
arrive[i][cur.ss] = it->ss;
}
}
mp[i].clear();
v.clear();
for (int j = 0; j < n; j++) {
v.pb({{arrive[i - 1][j], arrive[i][j]}, j});
}
sort(v.begin(), v.end(), [&](pair<pii, int> &lhs, pair<pii, int> &rhs) {
// sort by smaller starting time
if (lhs.ff.ff != rhs.ff.ff) return lhs.ff.ff < rhs.ff.ff;
// tiebreak by larger arrival time
return lhs.ff.ss > rhs.ff.ss;
});
int curmax = -1;
for (pair<pii, int> &cur : v) {
if (cur.ff.ss > curmax) {
mp[i][cur.ff.ff] = cur.ff.ss;
curmax = cur.ff.ss;
}
}
}
// for (int i = 0; i < m; i++) {
// for (int j = 0; j < n; j++) {
// cerr << arrive[i][j] << ' ';
// }
// cerr << endl;
// }
}
void CalcAnswer() {
for (int i = 1; i < m; i++) {
int dist = x * (s[i] - s[i - 1]);
for (it2 = ansmp.begin(); it2 != ansmp.end(); ++it2) {
int prev = it2->ss.ss;
it2->ss.ss += dist; // expected arrival time
it = mp[i].lower_bound(prev);
if (it != mp[i].begin()) {
--it;
it2->ss.ss = max(it2->ss.ss, it->ss);
}
}
// cerr << i << ": ";
// for (it2 = ansmp.begin(); it2 != ansmp.end(); ++it2) {
// cerr << it2->ff << " " << it2->ss.ff << " " << it2->ss.ss << " | ";
// }
// cerr << endl;
for (it = mp[i].begin(); it != mp[i].end(); ++it) {
pii range;
range.ff = it->ff - x * (s[i - 1] - s[0]);
range.ss = it->ss - x * (s[i] - s[0]);
if (range.ff == range.ss) continue;
ansmp[range.ff] = {range.ss, it->ss};
}
// cerr << i << ": ";
// for (it2 = ansmp.begin(); it2 != ansmp.end(); ++it2) {
// cerr << it2->ff << " " << it2->ss.ff << " " << it2->ss.ss << " | ";
// }
// cerr << endl;
for (it2 = ansmp.begin(); it2 != ansmp.end(); ++it2) {
it3 = it2;
++it3;
if (it3 == ansmp.end()) break;
if (it2->ss.ss == it3->ss.ss) {
it2->ss.ff = it3->ss.ff;
ansmp.erase(it3);
}
}
cerr << i << ": ";
for (it2 = ansmp.begin(); it2 != ansmp.end(); ++it2) {
cerr << it2->ff << " " << it2->ss.ff << " " << it2->ss.ss << " | ";
}
cerr << endl;
}
}
void init(int32_t L, int32_t N, vector<long long> T, vector<int32_t> W, int32_t X, int32_t M, vector<int32_t> S)
{
n = N; m = M;
reset();
for (int i = 0; i < n; i++) {
arrive[0][i] = T[i]; w[i] = W[i];
}
for (int i = 0; i < m; i++) {
s[i] = S[i];
}
x = X;
CalcArrival();
CalcAnswer();
}
long long bruh_arrival_time(long long t)
{
for (int i = 1; i < m; i++) {
int nt1 = t + x * (s[i] - s[i - 1]);
// look for delay
it = mp[i].lower_bound(t);
if (it != mp[i].begin()) {
--it;
nt1 = max(nt1, it->ss);
}
t = nt1;
}
return t;
}
long long arrival_time(long long t)
{
// return bruh_arrival_time(t);
// cout << t << ", bruh arrival " << bruh_arrival_time(t) << endl;
it2 = ansmp.lower_bound(t);
if (it2 != ansmp.begin()) {
--it2;
if (it2->ff < t && t <= it2->ss.ff) {
t = it2->ss.ss;
} else {
t += x * (s[m - 1] - s[0]);
}
} else {
t += x * (s[m - 1] - s[0]);
}
return t;
}
#undef int