oj.uz

Submission #153183

# Submission time Handle Problem Language Result Execution time Memory
153183 2019-09-12T18:46:42 Z tfg Organizing the Best Squad (FXCUP4_squad) C++17
100 / 100
 2837 ms 92308 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;
	if(std::min(a.size(), b.size()) < 2){
		for(int i = 0; i < (int) a.size(); i++) {
			for(int j = 0; j < (int) b.size(); 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;
	auto insert = [&](PT p) {
		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);
	};
	while(pa + pb + 1 < (int) (a.size() + b.size())) {
		PT va = (a[(pa+1)%a.size()]-a[pa%a.size()]);
		PT vb = (b[(pb+1)%b.size()]-b[pb%b.size()]);
		if(pb == (int) b.size() || (pa < (int) a.size() && comp(va, vb))) { p = p + va, pa++; }
		else { p = p + vb, pb++; }
		insert(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 18 ms 14456 KB Output is correct
3 Correct 1858 ms 37568 KB Output is correct
4 Correct 1849 ms 37416 KB Output is correct
5 Correct 156 ms 19248 KB Output is correct
6 Correct 2559 ms 83352 KB Output is correct
7 Correct 2561 ms 83224 KB Output is correct
8 Correct 2559 ms 88464 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 26 ms 14676 KB Output is correct
3 Correct 1821 ms 37328 KB Output is correct
4 Correct 1825 ms 37388 KB Output is correct
5 Correct 95 ms 16508 KB Output is correct
6 Correct 2493 ms 69740 KB Output is correct
7 Correct 2489 ms 69792 KB Output is correct
8 Correct 2498 ms 69884 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 18 ms 14456 KB Output is correct
3 Correct 1858 ms 37568 KB Output is correct
4 Correct 1849 ms 37416 KB Output is correct
5 Correct 156 ms 19248 KB Output is correct
6 Correct 2559 ms 83352 KB Output is correct
7 Correct 2561 ms 83224 KB Output is correct
8 Correct 2559 ms 88464 KB Output is correct
9 Correct 13 ms 14456 KB Output is correct
10 Correct 26 ms 14676 KB Output is correct
11 Correct 1821 ms 37328 KB Output is correct
12 Correct 1825 ms 37388 KB Output is correct
13 Correct 95 ms 16508 KB Output is correct
14 Correct 2493 ms 69740 KB Output is correct
15 Correct 2489 ms 69792 KB Output is correct
16 Correct 2498 ms 69884 KB Output is correct
17 Correct 83 ms 16880 KB Output is correct
18 Correct 34 ms 14676 KB Output is correct
19 Correct 2029 ms 37356 KB Output is correct
20 Correct 2044 ms 37408 KB Output is correct
21 Correct 111 ms 17448 KB Output is correct
22 Correct 2835 ms 92144 KB Output is correct
23 Correct 2830 ms 92128 KB Output is correct
24 Correct 2837 ms 92308 KB Output is correct