oj.uz

Submission #152409

# Submission time Handle Problem Language Result Execution time Memory
152409 2019-09-07T22:53:20 Z tfg Organizing the Best Squad (FXCUP4_squad) C++17
100 / 100
 2620 ms 88456 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 < a.size()+b.size()){
		if(pb == (int) b.size() || (pa < (int) a.size() && comp((a[(pa+1)%a.size()]-a[pa]),(b[(pb+1)%b.size()]-b[pb]))))
			p = p + (a[(pa+1)%a.size()]-a[pa]), pa++;
		else p = p + (b[(pb+1)%b.size()]-b[pb]), 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)];
}

Compilation message

squad.cpp: In function 'std::vector<PT> minkowskiSum(const std::vector<PT>&, const std::vector<PT>&)':
squad.cpp:152:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(pa + pb + 1 < a.size()+b.size()){
        ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~

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 14456 KB Output is correct
3 Correct 1890 ms 37424 KB Output is correct
4 Correct 1854 ms 37380 KB Output is correct
5 Correct 147 ms 19180 KB Output is correct
6 Correct 2331 ms 83160 KB Output is correct
7 Correct 2324 ms 83288 KB Output is correct
8 Correct 2317 ms 88456 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 14328 KB Output is correct
2 Correct 25 ms 14636 KB Output is correct
3 Correct 1807 ms 37280 KB Output is correct
4 Correct 1810 ms 37432 KB Output is correct
5 Correct 93 ms 16608 KB Output is correct
6 Correct 2375 ms 69892 KB Output is correct
7 Correct 2371 ms 69896 KB Output is correct
8 Correct 2380 ms 70036 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 14456 KB Output is correct
3 Correct 1890 ms 37424 KB Output is correct
4 Correct 1854 ms 37380 KB Output is correct
5 Correct 147 ms 19180 KB Output is correct
6 Correct 2331 ms 83160 KB Output is correct
7 Correct 2324 ms 83288 KB Output is correct
8 Correct 2317 ms 88456 KB Output is correct
9 Correct 13 ms 14328 KB Output is correct
10 Correct 25 ms 14636 KB Output is correct
11 Correct 1807 ms 37280 KB Output is correct
12 Correct 1810 ms 37432 KB Output is correct
13 Correct 93 ms 16608 KB Output is correct
14 Correct 2375 ms 69892 KB Output is correct
15 Correct 2371 ms 69896 KB Output is correct
16 Correct 2380 ms 70036 KB Output is correct
17 Correct 86 ms 16964 KB Output is correct
18 Correct 31 ms 14712 KB Output is correct
19 Correct 2001 ms 37416 KB Output is correct
20 Correct 2024 ms 37424 KB Output is correct
21 Correct 107 ms 17488 KB Output is correct
22 Correct 2620 ms 83164 KB Output is correct
23 Correct 2608 ms 83304 KB Output is correct
24 Correct 2607 ms 83356 KB Output is correct