oj.uz

Submission #152600

# Submission time Handle Problem Language Result Execution time Memory
152600 2019-09-08T14:24:31 Z josecruz Organizing the Best Squad (FXCUP4_squad) C++17
100 / 100
 2705 ms 89968 KB 
//#include "squad.h"

#include <vector>
#include <algorithm>
#include <cassert>
#include <functional>

using namespace std;

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; }
};

vector<PT> splitHull(const vector<PT> &hull) {
  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;
}

vector<PT> ConvexHull (vector<PT> pts, bool needs = true) {
  if(needs) {
    sort(pts.begin(), pts.end());
  }
  pts.resize(unique(pts.begin(), pts.end()) - pts.begin());
  if(pts.size() <= 1) return pts;
  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;
}

vector<PT> ConvexHull(const vector<PT> &a, const vector<PT> &b) {
  auto A = splitHull(a);
  auto B = splitHull(b);
  vector<PT> C(A.size() + B.size());
  merge(A.begin(), A.end(), B.begin(), B.end(), C.begin());
  return ConvexHull(C, false);
}

////////////////////////////////////////////////////////////////////////////////

using lint = long long;

function<bool(lint, lint)> Cond;// = [](lint l, lint r) { return l < r; };
function<lint(lint, lint)> GetM;// = [](lint l, lint r) { return (l + r) / 2; };
function<lint(lint)> GetL, GetR;// GetL = GetR = [](lint m) { return m; };

struct BinarySearch {
  template <class Int, class F, class... Args>
  Int operator () (Int l, Int r, const F &f, const Args&... args) {
    assert(l < r);
    while (Cond(l, r)) {
      Int m = GetM(l, r);
      if (f(m, args...))
        l = GetL(m);
      else
        r = GetR(m);
    }
    return l;
  }
};

////////////////////////////////////////////////////////////////////////////////

int maximizeScalarProduct(const 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 {
    BinarySearch bs;
    Cond = [](int l, int r) { return l != r; };
    int diff = 1;
    if(hull[0] * vec == hull[1] * vec) {
      int l = 2, r = n - 1;
      GetM = [](int l, int r) { return (l + r) / 2; };
      GetL = [](int m) { return m + 1; };
      GetR = [](int m) { return m; };
      diff = bs(2, n - 1, [&](int mid) {
        return (hull[1] - hull[0]) * (hull[mid] - hull[0]) > 0 && (hull[1] - hull[0]) % (hull[mid] - hull[0]) == 0;
      });
    }
    GetM = [](int l, int r) { return (l + r + 1) / 2; };
    GetL = [](int m) { return m; };
    GetR = [](int m) { return m - 1; };
    if(hull[0] * vec < hull[diff] * vec) {;
      int aux = bs(diff, n - 1, [&](int mid) {
        return hull[mid] * vec >= hull[mid - 1] * vec && hull[mid] * vec >= hull[0] * vec;
      });
      if (hull[0] * vec < hull[aux] * vec) {
        ans = aux;
      }
    } else {
      int aux = bs(diff, n - 1, [&](int mid) {
        return hull[mid] * vec >= hull[mid - 1] * vec || hull[mid - 1] * vec < hull[0] * vec;
      });
      if (hull[0] * vec < hull[aux] * vec) {
        ans = aux;
      }
    }
  }
  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;
}

vector<PT> minkowskiSum(const vector<PT> &a, const vector<PT> &b){
  if(a.empty() || b.empty()) return vector<PT>(0);
  vector<PT> ret;
  if(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]);
      }
    }
    return ret;
  }
  ret.push_back(a[0]+b[0]);
  PT p = ret.back();
  int pa = 0, pb = 0;
  auto insert = [&](PT p) {
    while(ret.size() >= 2 && (p-ret.back()) % (p-ret[(int)ret.size()-2]) == 0) {
      // removing colinear points
      // needs the scalar product stuff it the result is a line
      ret.pop_back();
    }
    ret.push_back(p);
  };
  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++;
    insert(p);
  }
  return ret;
}

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

vector<PT> solve(int l, int r) {
  if(r - l <= 1) {
    return vector<PT>(0);
  }
  int mid = (l + r) / 2;
  vector<PT> ans = ConvexHull(solve(l, mid), solve(mid, r));
  vector<PT> other;
  {
    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));
  }
  {
    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)));
  }
  merge(h1 + l, h1 + mid, h1 + mid, h1 + r, tmp + l);
  for(int i = l; i < r; i++) {
    h1[i] = tmp[i];
  }
  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);
}

vector<PT> tot;
void Init(vector<int> A, vector<int> D, 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

squad.cpp: In function 'int maximizeScalarProduct(const std::vector<PT>&, PT)':
squad.cpp:107:11: warning: unused variable 'l' [-Wunused-variable]
       int l = 2, r = n - 1;
           ^
squad.cpp:107:18: warning: unused variable 'r' [-Wunused-variable]
       int l = 2, r = n - 1;
                  ^
squad.cpp: In function 'std::vector<PT> minkowskiSum(const std::vector<PT>&, const std::vector<PT>&)':
squad.cpp:168:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(pa + pb + 1 < a.size()+b.size()){
         ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 14456 KB Output is correct
2 Correct 21 ms 14584 KB Output is correct
3 Correct 1886 ms 39528 KB Output is correct
4 Correct 1835 ms 39008 KB Output is correct
5 Correct 142 ms 19716 KB Output is correct
6 Correct 2365 ms 84400 KB Output is correct
7 Correct 2364 ms 84628 KB Output is correct
8 Correct 2333 ms 89968 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14456 KB Output is correct
2 Correct 27 ms 14772 KB Output is correct
3 Correct 1826 ms 38992 KB Output is correct
4 Correct 1831 ms 38756 KB Output is correct
5 Correct 95 ms 17140 KB Output is correct
6 Correct 2479 ms 71032 KB Output is correct
7 Correct 2448 ms 71420 KB Output is correct
8 Correct 2462 ms 71068 KB Output is correct

Subtask #3
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 14456 KB Output is correct
2 Correct 21 ms 14584 KB Output is correct
3 Correct 1886 ms 39528 KB Output is correct
4 Correct 1835 ms 39008 KB Output is correct
5 Correct 142 ms 19716 KB Output is correct
6 Correct 2365 ms 84400 KB Output is correct
7 Correct 2364 ms 84628 KB Output is correct
8 Correct 2333 ms 89968 KB Output is correct
9 Correct 14 ms 14456 KB Output is correct
10 Correct 27 ms 14772 KB Output is correct
11 Correct 1826 ms 38992 KB Output is correct
12 Correct 1831 ms 38756 KB Output is correct
13 Correct 95 ms 17140 KB Output is correct
14 Correct 2479 ms 71032 KB Output is correct
15 Correct 2448 ms 71420 KB Output is correct
16 Correct 2462 ms 71068 KB Output is correct
17 Correct 84 ms 18256 KB Output is correct
18 Correct 31 ms 14832 KB Output is correct
19 Correct 2040 ms 38844 KB Output is correct
20 Correct 2049 ms 38520 KB Output is correct
21 Correct 109 ms 18092 KB Output is correct
22 Correct 2705 ms 84280 KB Output is correct
23 Correct 2679 ms 84292 KB Output is correct
24 Correct 2696 ms 84132 KB Output is correct