oj.uz

답안 #149062

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
149062 2019-09-01T05:39:47 Z お前はもう死んでいる(#3784, kuroni, nvmdava, tfg) 최적의 팀 구성 (FXCUP4_squad) C++17
47 / 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, bool needs = true) {
	if(pts.size() <= 1) return pts;
	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);
	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], false);
		hull[1] = 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]);
		}
		hull[0] = ConvexHull(hull[0], false);
		hull[1] = 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);
	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>, bool)':
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
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 14464 KB Output is correct
2 Correct 16 ms 15228 KB Output is correct
3 Correct 1667 ms 219352 KB Output is correct
4 Correct 1510 ms 219480 KB Output is correct
5 Correct 159 ms 43068 KB Output is correct
6 Correct 2837 ms 524288 KB Output is correct
7 Correct 2825 ms 524288 KB Output is correct
8 Correct 2802 ms 524288 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 15736 KB Output is correct
3 Correct 1456 ms 185564 KB Output is correct
4 Correct 1457 ms 185560 KB Output is correct
5 Correct 89 ms 28640 KB Output is correct
6 Correct 2403 ms 438356 KB Output is correct
7 Correct 2350 ms 438484 KB Output is correct
8 Correct 2332 ms 438484 KB Output is correct

Subtask #3
0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 14464 KB Output is correct
2 Correct 16 ms 15228 KB Output is correct
3 Correct 1667 ms 219352 KB Output is correct
4 Correct 1510 ms 219480 KB Output is correct
5 Correct 159 ms 43068 KB Output is correct
6 Correct 2837 ms 524288 KB Output is correct
7 Correct 2825 ms 524288 KB Output is correct
8 Correct 2802 ms 524288 KB Output is correct
9 Correct 13 ms 14464 KB Output is correct
10 Correct 23 ms 15736 KB Output is correct
11 Correct 1456 ms 185564 KB Output is correct
12 Correct 1457 ms 185560 KB Output is correct
13 Correct 89 ms 28640 KB Output is correct
14 Correct 2403 ms 438356 KB Output is correct
15 Correct 2350 ms 438484 KB Output is correct
16 Correct 2332 ms 438484 KB Output is correct
17 Correct 86 ms 16888 KB Output is correct
18 Correct 28 ms 16632 KB Output is correct
19 Correct 1700 ms 219480 KB Output is correct
20 Correct 1681 ms 219352 KB Output is correct
21 Correct 120 ms 32852 KB Output is correct
22 Execution timed out 3103 ms 524288 KB Time limit exceeded
23 Halted 0 ms 0 KB -