oj.uz

Submission #151931

# Submission time Handle Problem Language Result Execution time Memory
151931 2019-09-05T14:26:34 Z tfg Organizing the Best Squad (FXCUP4_squad) C++17
100 / 100
 2680 ms 88492 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());
	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:142: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 18 ms 14456 KB Output is correct
3 Correct 1870 ms 37420 KB Output is correct
4 Correct 1878 ms 37712 KB Output is correct
5 Correct 157 ms 19344 KB Output is correct
6 Correct 2430 ms 83316 KB Output is correct
7 Correct 2390 ms 83336 KB Output is correct
8 Correct 2360 ms 88472 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 14672 KB Output is correct
3 Correct 1865 ms 37528 KB Output is correct
4 Correct 1856 ms 37384 KB Output is correct
5 Correct 96 ms 16628 KB Output is correct
6 Correct 2448 ms 69888 KB Output is correct
7 Correct 2446 ms 69908 KB Output is correct
8 Correct 2464 ms 69792 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 1870 ms 37420 KB Output is correct
4 Correct 1878 ms 37712 KB Output is correct
5 Correct 157 ms 19344 KB Output is correct
6 Correct 2430 ms 83316 KB Output is correct
7 Correct 2390 ms 83336 KB Output is correct
8 Correct 2360 ms 88472 KB Output is correct
9 Correct 13 ms 14456 KB Output is correct
10 Correct 26 ms 14672 KB Output is correct
11 Correct 1865 ms 37528 KB Output is correct
12 Correct 1856 ms 37384 KB Output is correct
13 Correct 96 ms 16628 KB Output is correct
14 Correct 2448 ms 69888 KB Output is correct
15 Correct 2446 ms 69908 KB Output is correct
16 Correct 2464 ms 69792 KB Output is correct
17 Correct 86 ms 16976 KB Output is correct
18 Correct 31 ms 14652 KB Output is correct
19 Correct 2060 ms 37576 KB Output is correct
20 Correct 2060 ms 37464 KB Output is correct
21 Correct 108 ms 17436 KB Output is correct
22 Correct 2667 ms 83292 KB Output is correct
23 Correct 2680 ms 83464 KB Output is correct
24 Correct 2656 ms 88492 KB Output is correct