oj.uz

답안 #151927

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
151927 2019-09-05T14:20:42 Z tfg 최적의 팀 구성 (FXCUP4_squad) C++17
100 / 100
 2712 ms 98720 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];
	}*/
	ans[s++] = pts[0];
	ans[s++] = pts.back();
	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> 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]);
		}
		ans = ConvexHull(ans, 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]);
		}
		ans = ConvexHull(ans, 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 ans;
}

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:147: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

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 14328 KB Output is correct
2 Correct 18 ms 14456 KB Output is correct
3 Correct 1471 ms 38940 KB Output is correct
4 Correct 1467 ms 38356 KB Output is correct
5 Correct 146 ms 19560 KB Output is correct
6 Correct 2376 ms 90592 KB Output is correct
7 Correct 2376 ms 90176 KB Output is correct
8 Correct 2399 ms 89968 KB Output is correct

Subtask #2
28.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 14456 KB Output is correct
2 Correct 24 ms 14828 KB Output is correct
3 Correct 1580 ms 38516 KB Output is correct
4 Correct 1561 ms 38520 KB Output is correct
5 Correct 92 ms 16992 KB Output is correct
6 Correct 2303 ms 75820 KB Output is correct
7 Correct 2308 ms 75944 KB Output is correct
8 Correct 2287 ms 75792 KB Output is correct

Subtask #3
53.0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 14328 KB Output is correct
2 Correct 18 ms 14456 KB Output is correct
3 Correct 1471 ms 38940 KB Output is correct
4 Correct 1467 ms 38356 KB Output is correct
5 Correct 146 ms 19560 KB Output is correct
6 Correct 2376 ms 90592 KB Output is correct
7 Correct 2376 ms 90176 KB Output is correct
8 Correct 2399 ms 89968 KB Output is correct
9 Correct 14 ms 14456 KB Output is correct
10 Correct 24 ms 14828 KB Output is correct
11 Correct 1580 ms 38516 KB Output is correct
12 Correct 1561 ms 38520 KB Output is correct
13 Correct 92 ms 16992 KB Output is correct
14 Correct 2303 ms 75820 KB Output is correct
15 Correct 2308 ms 75944 KB Output is correct
16 Correct 2287 ms 75792 KB Output is correct
17 Correct 87 ms 17628 KB Output is correct
18 Correct 28 ms 14836 KB Output is correct
19 Correct 1640 ms 38068 KB Output is correct
20 Correct 1642 ms 37956 KB Output is correct
21 Correct 110 ms 17988 KB Output is correct
22 Correct 2712 ms 89576 KB Output is correct
23 Correct 2663 ms 98448 KB Output is correct
24 Correct 2675 ms 98720 KB Output is correct