Submission #152600

#	Time	Username	Problem	Language	Result	Execution time	Memory
152600		josecruz	Organizing the Best Squad (FXCUP4_squad)	C++17	100 / 100	2705 ms	89968 KiB

squad

//#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 (stderr)

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 / 19
• Subtask 2: 28 / 28
• Subtask 3: 53 / 53