oj.uz

답안 #149115

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
149115 2019-09-01T05:46:09 Z お前はもう死んでいる(#3784, kuroni, nvmdava, tfg) 최적의 팀 구성 (FXCUP4_squad) C++17
100 / 100
 2872 ms 380928 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;     }
	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; }
};

void ConvexHull (std::vector<PT> &pts, bool needs = true) {
	if(pts.size() <= 1) return;
	if(needs) {
		std::sort(pts.begin(), pts.end());
		pts.resize(std::unique(pts.begin(), pts.end()) - pts.begin());
	}
	std::vector<PT> ans(2 * pts.size());
	int s = 0;
	for(int i = 0; i < 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 = pts.size() - 1, t = s + 1; i > 0; i--) {
		while(s >= t && (pts[i - 1] - ans[s - 2]) % (ans[s - 1] - ans[s - 2]) >= 0) {
			s--;
		}
		ans[s++] = pts[i - 1];
	}
	ans.resize(s - 1);
	ans.swap(pts);
}

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> tot;
void poly_sum(std::vector<PT> &a, std::vector<PT> &b){
	if(a.empty() || b.empty()) return;
	if(std::min(a.size(), b.size()) < 2){
		for(int i = 0; i < a.size(); i++) {
			for(int j = 0; j < b.size(); j++) {
				tot.push_back(a[i]+b[j]);
			}
		}
	}
	tot.push_back(a[0]+b[0]);
	PT p = tot.back();
	int pa = 0, pb = 0;
	while(pa < a.size() || pb < b.size()){
		if(pb == b.size() || (pa < 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++;
		tot.push_back(p);
	}
	tot.pop_back();
}

const int ms = 300300;
PT h1[ms], h2[ms], tmp[ms];

void solve(int l, int r) {
	if(r - l <= 1) {
		return;
	}
	int mid = (l + r) / 2;
	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]);
		}
		ConvexHull(hull[0], false);
		ConvexHull(hull[1], false);
		poly_sum(hull[0], hull[1]);
	}
	{
		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]);
		}
		ConvexHull(hull[0], false);
		ConvexHull(hull[1], false);
		poly_sum(hull[0], hull[1]);
	}
	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];
	}
}

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]);
	}
	solve(0, N);
	ConvexHull(tot);
}

long long BestSquad(int X, int Y){
	PT cur(X, Y);
	return cur * tot[maximizeScalarProduct(tot, cur)];
}

Compilation message

squad.cpp: In function 'void ConvexHull(std::vector<PT>&, bool)':
squad.cpp:28:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < pts.size(); i++) {
                 ~~^~~~~~~~~~~~
squad.cpp: In function 'void poly_sum(std::vector<PT>&, std::vector<PT>&)':
squad.cpp:112:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < a.size(); i++) {
                  ~~^~~~~~~~~~
squad.cpp:113:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j = 0; j < b.size(); j++) {
                   ~~^~~~~~~~~~
squad.cpp:121:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(pa < a.size() || pb < b.size()){
        ~~~^~~~~~~~~~
squad.cpp:121:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(pa < a.size() || pb < b.size()){
                         ~~~^~~~~~~~~~
squad.cpp:122:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(pb == b.size() || (pa < a.size() && comp((a[(pa+1)%a.size()]-a[pa]),(b[(pb+1)%b.size()]-b[pb]))))
      ~~~^~~~~~~~~~~
squad.cpp:122:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(pb == b.size() || (pa < a.size() && comp((a[(pa+1)%a.size()]-a[pa]),(b[(pb+1)%b.size()]-b[pb]))))
                         ~~~^~~~~~~~~~

Subtask #1
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 14508 KB Output is correct
2 Correct 16 ms 15100 KB Output is correct
3 Correct 1406 ms 167900 KB Output is correct
4 Correct 1395 ms 167940 KB Output is correct
5 Correct 137 ms 33736 KB Output is correct
6 Correct 2613 ms 380880 KB Output is correct
7 Correct 2560 ms 380928 KB Output is correct
8 Correct 2488 ms 380880 KB Output is correct

Subtask #2
28.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 14464 KB Output is correct
2 Correct 23 ms 15480 KB Output is correct
3 Correct 1388 ms 142552 KB Output is correct
4 Correct 1389 ms 142552 KB Output is correct
5 Correct 80 ms 24800 KB Output is correct
6 Correct 2141 ms 332116 KB Output is correct
7 Correct 2250 ms 332116 KB Output is correct
8 Correct 2061 ms 332116 KB Output is correct

Subtask #3
53.0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 14508 KB Output is correct
2 Correct 16 ms 15100 KB Output is correct
3 Correct 1406 ms 167900 KB Output is correct
4 Correct 1395 ms 167940 KB Output is correct
5 Correct 137 ms 33736 KB Output is correct
6 Correct 2613 ms 380880 KB Output is correct
7 Correct 2560 ms 380928 KB Output is correct
8 Correct 2488 ms 380880 KB Output is correct
9 Correct 13 ms 14464 KB Output is correct
10 Correct 23 ms 15480 KB Output is correct
11 Correct 1388 ms 142552 KB Output is correct
12 Correct 1389 ms 142552 KB Output is correct
13 Correct 80 ms 24800 KB Output is correct
14 Correct 2141 ms 332116 KB Output is correct
15 Correct 2250 ms 332116 KB Output is correct
16 Correct 2061 ms 332116 KB Output is correct
17 Correct 89 ms 17020 KB Output is correct
18 Correct 31 ms 15984 KB Output is correct
19 Correct 1689 ms 167872 KB Output is correct
20 Correct 1730 ms 167896 KB Output is correct
21 Correct 106 ms 26836 KB Output is correct
22 Correct 2762 ms 380880 KB Output is correct
23 Correct 2868 ms 380892 KB Output is correct
24 Correct 2872 ms 380880 KB Output is correct