oj.uz

Submission #153184

# Submission time Handle Problem Language Result Execution time Memory
153184 2019-09-12T18:49:17 Z tfg Organizing the Best Squad (FXCUP4_squad) C++17
100 / 100
 2521 ms 88420 KB 
#include "squad.h"

#include <vector>
#include <algorithm>
#include <cassert>

struct PT {
	typedef long long T;
	T x, y;
	PT(T xx = 0, T yy = 0) : x(xx), y(yy){}
	PT operator +(const PT &p) const { return PT(x+p.x,y+p.y); }
	PT operator -(const PT &p) const { return PT(x-p.x,y-p.y); }
	PT operator *(T c)         const { return PT(x*c,y*c);     }
	T operator *(const PT &p)  const { return x*p.x+y*p.y;     }
	T operator %(const PT &p)  const { return x*p.y-y*p.x;     }
	// be careful using this without eps!
	bool operator<(const PT &p)const { return x != p.x ? x < p.x : y < p.y; }
	bool operator==(const PT &p)const{ return x == p.x && y == p.y; }
};

std::vector<PT> splitHull(const std::vector<PT> &hull) {
	std::vector<PT> ans(hull.size());
	for(int i = 0, j = (int) hull.size()-1, k = 0; k < (int) hull.size(); k++) {
		if(hull[i] < hull[j]) {
			ans[k] = hull[i++];
		} else {
			ans[k] = hull[j--];
		}
	}
	return ans;
}

std::vector<PT> ConvexHull (std::vector<PT> pts, bool needs = true) {
	if(needs) {
		std::sort(pts.begin(), pts.end());
	}
	pts.resize(std::unique(pts.begin(), pts.end()) - pts.begin());
	if(pts.size() <= 1) return pts;
	std::vector<PT> ans(pts.size() + 2);
	int s = 0;
	for(int i = 0; i < (int) pts.size(); i++) {
		while(s > 1 && (pts[i] - ans[s - 2]) % (ans[s - 1] - ans[s - 2]) >= 0) {
			s--;
		}
		ans[s++] = pts[i];
	}
	for(int i = (int) pts.size() - 2, t = s + 1; i >= 0; i--) {
		while(s >= t && (pts[i] - ans[s - 2]) % (ans[s - 1] - ans[s - 2]) >= 0) {
			s--;
		}
		ans[s++] = pts[i];
	}
	ans.resize(s-1);
	return ans;
}

std::vector<PT> ConvexHull(const std::vector<PT> &a, const std::vector<PT> &b) {
	auto A = splitHull(a);
	auto B = splitHull(b);
	std::vector<PT> C(A.size() + B.size());
	std::merge(A.begin(), A.end(), B.begin(), B.end(), C.begin());
	return ConvexHull(C, false);
}

int maximizeScalarProduct(const std::vector<PT> &hull, PT vec) {
	int ans = 0;
	int n = hull.size();
	if(n < 20) {
		for(int i = 0; i < n; i++) {
			if(hull[i] * vec > hull[ans] * vec) {
				ans = i;
			}
		}
	} else {
		int diff = 1;
		if(hull[0] * vec == hull[1] * vec) {
			int l = 2, r = n - 1;
			while(l != r) {
				int mid = (l + r) / 2;
				if((hull[1] - hull[0]) * (hull[mid] - hull[0]) > 0 && (hull[1] - hull[0]) % (hull[mid] - hull[0]) == 0) {
					l = mid + 1;
				} else {
					r = mid;
				}
			}
			diff = l;
			//diff = 2;
		}
		if(hull[0] * vec < hull[diff] * vec) {
			int l = diff, r = n - 1;
			while(l != r) {
				int mid = (l + r + 1) / 2;
				if(hull[mid] * vec >= hull[mid - 1] * vec && hull[mid] * vec >= hull[0] * vec) {
					l = mid;
				} else {
					r = mid - 1;
				}
			}
			if(hull[0] * vec < hull[l] * vec) {
				ans = l;
			}
		} else {
			int l = diff, r = n - 1;
			while(l != r) {
				int mid = (l + r + 1) / 2;
				if(hull[mid] * vec >= hull[mid - 1] * vec || hull[mid - 1] * vec < hull[0] * vec) {
					l = mid;
				} else {
					r = mid - 1;
				}
			}
			if(hull[0] * vec < hull[l] * vec) {
				ans = l;
			}
		}
	}
	return ans;
}

bool comp(PT a, PT b){
	int hp1 = (a.x < 0 || (a.x==0 && a.y<0));
	int hp2 = (b.x < 0 || (b.x==0 && b.y<0));
	if(hp1 != hp2) return hp1 < hp2;
	long long R = a%b;
	if(R) return R > 0;
	return a*a < b*b;
}


std::vector<PT> minkowskiSum(const std::vector<PT> &a, const std::vector<PT> &b){
	if(a.empty() || b.empty()) return std::vector<PT>(0);
	std::vector<PT> ret;
	int na = (int) a.size(), nb = (int) b.size();
	if(std::min(a.size(), b.size()) < 2){
		for(int i = 0; i < na; i++) {
			for(int j = 0; j < nb; j++) {
				ret.push_back(a[i]+b[j]);
			}
		}
		return ret;
	}
	ret.push_back(a[0]+b[0]);
	PT p = ret.back();
	int pa = 0, pb = 0;
	while(pa + pb + 1 < na + nb) {
		PT va = (a[(pa+1)%na]-a[pa%na]);
		PT vb = (b[(pb+1)%nb]-b[pb%nb]);
		if(pb == nb || (pa < na && comp(va, vb))) { p = p + va, pa++; }
		else { p = p + vb, pb++; }
		while(ret.size() >= 2 && (p-ret.back()) % (p-ret[(int)ret.size()-2]) == 0) {
			// removing colinear points
			// needs the scalar product stuff it the result is a line
			ret.pop_back();
		}
		ret.push_back(p);
	}
	return ret;
}

const int ms = 300300;
PT h1[ms], h2[ms], tmp[ms];

std::vector<PT> solve(int l, int r) {
	if(r - l <= 1) {
		return std::vector<PT>(0);
	}
	int mid = (l + r) / 2;
	std::vector<PT> ans = ConvexHull(solve(l, mid), solve(mid, r));
	std::vector<PT> other;
	{
		std::vector<PT> hull[2];
		for(int i = l; i < mid; i++) {
			hull[0].push_back(h1[i]);
		}
		for(int i = mid; i < r; i++) {
			hull[1].emplace_back(h2[i]);
		}
		other = minkowskiSum(ConvexHull(hull[0], false), ConvexHull(hull[1], false));
	}
	{
		std::vector<PT> hull[2];
		for(int i = l; i < mid; i++) {
			hull[0].push_back(h2[i]);
		}
		for(int i = mid; i < r; i++) {
			hull[1].emplace_back(h1[i]);
		}
		other = ConvexHull(other, minkowskiSum(ConvexHull(hull[0], false), ConvexHull(hull[1], false)));
	}
	std::merge(h1 + l, h1 + mid, h1 + mid, h1 + r, tmp + l);
	for(int i = l; i < r; i++) {
		h1[i] = tmp[i];
	}
	std::merge(h2 + l, h2 + mid, h2 + mid, h2 + r, tmp + l);
	for(int i = l; i < r; i++) {
		h2[i] = tmp[i];
	}
	return ConvexHull(ans, other);
}

std::vector<PT> tot;
void Init(std::vector<int> A, std::vector<int> D, std::vector<int> P){
	int N = A.size();
	for(int i = 0; i < N; i++) {
		h1[i] = PT(A[i], P[i]);
		h2[i] = PT(D[i], P[i]);
	}
	tot = solve(0, N);
}

long long BestSquad(int X, int Y){
	PT cur(X, Y);
	return cur * tot[maximizeScalarProduct(tot, cur)];
}

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 14328 KB Output is correct
2 Correct 20 ms 14428 KB Output is correct
3 Correct 1805 ms 37492 KB Output is correct
4 Correct 1795 ms 37496 KB Output is correct
5 Correct 138 ms 19248 KB Output is correct
6 Correct 2246 ms 83432 KB Output is correct
7 Correct 2245 ms 83216 KB Output is correct
8 Correct 2199 ms 88420 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 14456 KB Output is correct
2 Correct 25 ms 14680 KB Output is correct
3 Correct 1802 ms 37356 KB Output is correct
4 Correct 1776 ms 37600 KB Output is correct
5 Correct 91 ms 16612 KB Output is correct
6 Correct 2325 ms 69808 KB Output is correct
7 Correct 2314 ms 69892 KB Output is correct
8 Correct 2297 ms 69712 KB Output is correct

Subtask #3
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 14328 KB Output is correct
2 Correct 20 ms 14428 KB Output is correct
3 Correct 1805 ms 37492 KB Output is correct
4 Correct 1795 ms 37496 KB Output is correct
5 Correct 138 ms 19248 KB Output is correct
6 Correct 2246 ms 83432 KB Output is correct
7 Correct 2245 ms 83216 KB Output is correct
8 Correct 2199 ms 88420 KB Output is correct
9 Correct 13 ms 14456 KB Output is correct
10 Correct 25 ms 14680 KB Output is correct
11 Correct 1802 ms 37356 KB Output is correct
12 Correct 1776 ms 37600 KB Output is correct
13 Correct 91 ms 16612 KB Output is correct
14 Correct 2325 ms 69808 KB Output is correct
15 Correct 2314 ms 69892 KB Output is correct
16 Correct 2297 ms 69712 KB Output is correct
17 Correct 83 ms 16888 KB Output is correct
18 Correct 30 ms 14704 KB Output is correct
19 Correct 1967 ms 37428 KB Output is correct
20 Correct 1978 ms 37380 KB Output is correct
21 Correct 101 ms 17584 KB Output is correct
22 Correct 2517 ms 83340 KB Output is correct
23 Correct 2501 ms 83300 KB Output is correct
24 Correct 2521 ms 83164 KB Output is correct