#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]))))
~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
