Submission #841338

#	Time	Username	Problem	Language	Result	Execution time	Memory
841338		happypotato	메기 농장 (IOI22_fish)	C++17	Compilation error	0 ms	0 KiB

fish

// 65 marks

#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;

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();
	}
}

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 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();
}


long long bruh_arrival_time(long long t)
{
	for (int i = 1; i < m; i++) {
		int nt2 = t + x * (s[i] - s[i - 1]);
		for (int j = 0; j < n; j++) {
			// look for delay
			if (t > arrive[i - 1][j]) {
				nt2 = max(nt2, arrive[i][j]);
			}
		}
		t = nt2;
	}
	return t;
}

long long arrival_time(long long t)
{
	// return bruh_arrival_time(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;
}

#undef int

Compilation message (stderr)

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