oj.uz

답안 #149032

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

std::vector<PT> ConvexHull (std::vector<PT> pts) {
	if(pts.size() <= 1) return pts;
	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);
	return ans;
}

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]);
		}
		hull[0] = ConvexHull(hull[0]);
		hull[1] = ConvexHull(hull[1]);
		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]);
		}
		hull[0] = ConvexHull(hull[0]);
		hull[1] = ConvexHull(hull[1]);
		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);
	tot = 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 'std::vector<PT> ConvexHull(std::vector<PT>)':
squad.cpp:26: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:110:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < a.size(); i++) {
                  ~~^~~~~~~~~~
squad.cpp:111:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j = 0; j < b.size(); j++) {
                   ~~^~~~~~~~~~
squad.cpp:119:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(pa < a.size() || pb < b.size()){
        ~~~^~~~~~~~~~
squad.cpp:119:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(pa < a.size() || pb < b.size()){
                         ~~~^~~~~~~~~~
squad.cpp:120: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:120: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
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 14208 KB Output is correct
2 Correct 17 ms 15228 KB Output is correct
3 Correct 1752 ms 219352 KB Output is correct
4 Correct 1695 ms 219532 KB Output is correct
5 Correct 165 ms 43068 KB Output is correct
6 Correct 2998 ms 524288 KB Output is correct
7 Correct 2920 ms 524288 KB Output is correct
8 Execution timed out 3060 ms 524288 KB Time limit exceeded

Subtask #2
28.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 14464 KB Output is correct
2 Correct 27 ms 15736 KB Output is correct
3 Correct 1710 ms 185688 KB Output is correct
4 Correct 1721 ms 185688 KB Output is correct
5 Correct 91 ms 28640 KB Output is correct
6 Correct 2552 ms 438360 KB Output is correct
7 Correct 2605 ms 438484 KB Output is correct
8 Correct 2491 ms 438360 KB Output is correct

Subtask #3
0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 14208 KB Output is correct
2 Correct 17 ms 15228 KB Output is correct
3 Correct 1752 ms 219352 KB Output is correct
4 Correct 1695 ms 219532 KB Output is correct
5 Correct 165 ms 43068 KB Output is correct
6 Correct 2998 ms 524288 KB Output is correct
7 Correct 2920 ms 524288 KB Output is correct
8 Execution timed out 3060 ms 524288 KB Time limit exceeded