Submission #152408

#TimeUsernameProblemLanguageResultExecution timeMemory
152408tfgOrganizing the Best Squad (FXCUP4_squad)C++17
100 / 100
2645 ms97328 KiB
#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 careful 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){ int hp1 = (a.x < 0 || (a.x==0 && a.y<0)); int hp2 = (b.x < 0 || (b.x==0 && b.y<0)); if(hp1 != hp2) return hp1 < hp2; 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 (stderr)

squad.cpp: In function 'std::vector<PT> minkowskiSum(const std::vector<PT>&, const std::vector<PT>&)':
squad.cpp:143:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(pa + pb + 1 < a.size()+b.size()){
        ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...