oj.uz

답안 #152598

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
152598 2019-09-08T14:20:56 Z josecruz 최적의 팀 구성 (FXCUP4_squad) C++17
100 / 100
 2726 ms 93220 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;
      /*
      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;
      */
      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;
      });
    }
    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;
      }
      */
      GetM = [](int l, int r) { return (l + r + 1) / 2; };
      GetL = [](int m) { return m; };
      GetR = [](int m) { return m - 1; };
      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 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;
      }
      */
      GetM = [](int l, int r) { return (l + r + 1) / 2; };
      GetL = [](int m) { return m; };
      GetR = [](int m) { return m - 1; };
      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:128:11: warning: unused variable 'l' [-Wunused-variable]
       int l = diff, r = n - 1;
           ^
squad.cpp:128:21: warning: unused variable 'r' [-Wunused-variable]
       int l = diff, r = n - 1;
                     ^
squad.cpp: In function 'std::vector<PT> minkowskiSum(const std::vector<PT>&, const std::vector<PT>&)':
squad.cpp:211: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

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 14456 KB Output is correct
2 Correct 19 ms 14588 KB Output is correct
3 Correct 1837 ms 42112 KB Output is correct
4 Correct 1897 ms 42076 KB Output is correct
5 Correct 141 ms 19688 KB Output is correct
6 Correct 2365 ms 87972 KB Output is correct
7 Correct 2355 ms 87936 KB Output is correct
8 Correct 2342 ms 93220 KB Output is correct

Subtask #2
28.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 14456 KB Output is correct
2 Correct 26 ms 14712 KB Output is correct
3 Correct 1825 ms 41200 KB Output is correct
4 Correct 1826 ms 41352 KB Output is correct
5 Correct 101 ms 17044 KB Output is correct
6 Correct 2462 ms 73600 KB Output is correct
7 Correct 2465 ms 73564 KB Output is correct
8 Correct 2497 ms 73208 KB Output is correct

Subtask #3
53.0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 14456 KB Output is correct
2 Correct 19 ms 14588 KB Output is correct
3 Correct 1837 ms 42112 KB Output is correct
4 Correct 1897 ms 42076 KB Output is correct
5 Correct 141 ms 19688 KB Output is correct
6 Correct 2365 ms 87972 KB Output is correct
7 Correct 2355 ms 87936 KB Output is correct
8 Correct 2342 ms 93220 KB Output is correct
9 Correct 13 ms 14456 KB Output is correct
10 Correct 26 ms 14712 KB Output is correct
11 Correct 1825 ms 41200 KB Output is correct
12 Correct 1826 ms 41352 KB Output is correct
13 Correct 101 ms 17044 KB Output is correct
14 Correct 2462 ms 73600 KB Output is correct
15 Correct 2465 ms 73564 KB Output is correct
16 Correct 2497 ms 73208 KB Output is correct
17 Correct 86 ms 19560 KB Output is correct
18 Correct 34 ms 14832 KB Output is correct
19 Correct 2043 ms 40324 KB Output is correct
20 Correct 2031 ms 46016 KB Output is correct
21 Correct 113 ms 18112 KB Output is correct
22 Correct 2726 ms 88780 KB Output is correct
23 Correct 2720 ms 92080 KB Output is correct
24 Correct 2703 ms 87968 KB Output is correct