oj.uz

Submission #151930

# Submission time Handle Problem Language Result Execution time Memory
151930 2019-09-05T14:24:39 Z tfg Organizing the Best Squad (FXCUP4_squad) C++17
100 / 100
 2696 ms 88616 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 carefull 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());
	for(int i = 0; i+1 < (int) pts.size(); i++) {
		assert(pts[i] < pts[i+1]);
	}
	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){
	if((a.x > 0 || (a.x==0 && a.y>0) ) && (b.x < 0 || (b.x==0 && b.y<0))) return 1;
	if((b.x > 0 || (b.x==0 && b.y>0) ) && (a.x < 0 || (a.x==0 && a.y<0))) return 0;
	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]);
			}
		}
	}
	ret.push_back(a[0]+b[0]);
	PT p = ret.back();
	int pa = 0, pb = 0;
	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++;
		while(ret.size() >= 2 && (p-ret.back()) % (p-ret[(int)ret.size()-2]) == 0) {
			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)];
}

Compilation message

squad.cpp: In function 'std::vector<PT> minkowskiSum(const std::vector<PT>&, const std::vector<PT>&)':
squad.cpp:145: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 14 ms 14328 KB Output is correct
2 Correct 19 ms 14444 KB Output is correct
3 Correct 1903 ms 37320 KB Output is correct
4 Correct 1897 ms 37716 KB Output is correct
5 Correct 147 ms 19284 KB Output is correct
6 Correct 2421 ms 83356 KB Output is correct
7 Correct 2405 ms 83272 KB Output is correct
8 Correct 2389 ms 88616 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14460 KB Output is correct
2 Correct 26 ms 14644 KB Output is correct
3 Correct 1905 ms 37500 KB Output is correct
4 Correct 1894 ms 37360 KB Output is correct
5 Correct 99 ms 16612 KB Output is correct
6 Correct 2507 ms 69748 KB Output is correct
7 Correct 2487 ms 69820 KB Output is correct
8 Correct 2493 ms 69764 KB Output is correct

Subtask #3
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14328 KB Output is correct
2 Correct 19 ms 14444 KB Output is correct
3 Correct 1903 ms 37320 KB Output is correct
4 Correct 1897 ms 37716 KB Output is correct
5 Correct 147 ms 19284 KB Output is correct
6 Correct 2421 ms 83356 KB Output is correct
7 Correct 2405 ms 83272 KB Output is correct
8 Correct 2389 ms 88616 KB Output is correct
9 Correct 14 ms 14460 KB Output is correct
10 Correct 26 ms 14644 KB Output is correct
11 Correct 1905 ms 37500 KB Output is correct
12 Correct 1894 ms 37360 KB Output is correct
13 Correct 99 ms 16612 KB Output is correct
14 Correct 2507 ms 69748 KB Output is correct
15 Correct 2487 ms 69820 KB Output is correct
16 Correct 2493 ms 69764 KB Output is correct
17 Correct 87 ms 16972 KB Output is correct
18 Correct 32 ms 14652 KB Output is correct
19 Correct 2086 ms 37512 KB Output is correct
20 Correct 2102 ms 37508 KB Output is correct
21 Correct 108 ms 17564 KB Output is correct
22 Correct 2696 ms 83200 KB Output is correct
23 Correct 2696 ms 83228 KB Output is correct
24 Correct 2683 ms 88520 KB Output is correct