Submission #841337

#	Time	Username	Problem	Language	Result	Execution time	Memory
841337		happypotato	Catfish Farm (IOI22_fish)	C++17	Compilation error	0 ms	0 KiB

fish

// 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

Compilation message (stderr)

fish.cpp:4:10: fatal error: overtaking.h: No such file or directory
    4 | #include "overtaking.h"
      |          ^~~~~~~~~~~~~~
compilation terminated.