oj.uz

Submission #302959

# Submission time Handle Problem Language Result Execution time Memory
302959 2020-09-19T14:47:17 Z Arg_007 Organizing the Best Squad (FXCUP4_squad) C++17
100 / 100
 2327 ms 70788 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define pb push_back
#define mp make_pair
#define PI ( acos(-1.0) )
#define FOR(i,a,b) for(i=a ; i<=b ; i++)
#define DBG printf("Hi\n")
#define i64 long long int
#define eps (1e-8)
#define xx first
#define yy second
#define ln 17
#define off 2
#define SZ(z) ((int)z.size())
#define MEM(a,x) memset(a,x,sizeof(a))

#define FastIO ios_base::sync_with_stdio(false); cin.tie(NULL)

using namespace __gnu_pbds;
using namespace std ;

typedef tree< i64, null_type, less<i64>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

#define IN freopen("262144.in","r",stdin)
#define OUT freopen("262144.out","w",stdout)

#include<squad.h>

#define maxn 300005
#define INF 1000000000
#define mod 998244353LL
#define log 60

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

typedef  long long int T ;
struct PT {
    T x , y ;
    PT() {}
    PT(T x_,T y_) {x=x_,y=y_;}
    PT operator + (const PT &p) { return {x+p.x,y+p.y} ;}
    PT operator - (const PT &p) { return {x-p.x,y-p.y} ;}
    PT operator * (const T &t) { return {x*t,y*t} ;}
    T operator * (const PT &p) { return x*p.x + y*p.y ; }
    T operator ^ (const PT &p)  { return x*p.y - y*p.x ;}
    bool operator==( const PT &p )const { return ((x==p.x) && (y==p.y)) ; }
    bool operator!=( const PT &p )const { return ((x!=p.x) || (y!=p.y)) ; }
    bool operator<(const PT &p) { return make_pair(x,y) < make_pair(p.x,p.y) ; }
};

double abs( PT p ){ return sqrt( p*p ) ; }
ostream& operator<<(ostream& os , PT p)
{
    os<<setprecision(10) ;
    return os<<"("<<p.x<<","<<p.y<<")" ;
}


T orient( PT a , PT b, PT c )
{
    //if ac is to the left of ab , it returns 1
    //if ac is in the same line as ab, it returns 0
    //if ac is to the right of ab, it returns -1
    return (b-a)^(c-a)  ;
}


//collected form tfg's code
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;
}
vector<PT> minkowskiSum(vector<PT> &a, vector<PT> &b){
	if(a.empty() || b.empty()) return std::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]);
			}
		}
	}
	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;
}


//Collected from our template library
PT dir;
bool half(PT p){
  return (dir^p) < 0 ||
        ( (dir^p) == 0 && (dir*p) > 0);
}
bool polarComp(PT p, PT q) {
  return make_tuple(half(p), 0)
       < make_tuple(half(q), (p^q));
}
void process(vector<PT> &P) {
  int mnid = 0;
  for (int i=0; i<P.size(); i++)
    if (P[i] < P[mnid])
      mnid = i;
  rotate(P.begin(), P.begin()+mnid, P.end());
}
vector<PT> MinkowskiSum(vector<PT>A, vector<PT>B){
  process(A); process(B);
  int n = A.size(), m = B.size();
  vector<PT> P(n), Q(m);
  for(int i=0; i<n; i++) P[i] = A[(i+1)%n] - A[i];
  for(int i=0; i<m; i++) Q[i] = B[(i+1)%m] - B[i];
  dir = PT(0, -1);
  vector<PT> C(n+m+1);
  merge(P.begin(), P.end(), Q.begin(), Q.end(),
                          C.begin()+1, polarComp);
  C[0] = A[0] + B[0];
  for(int i=1; i<C.size(); i++) C[i]=C[i]+C[i-1];
  C.pop_back();
  return C;
}


vector<PT> monotone_chain (vector <PT> &p, bool fl=false) {
     if(p.size()==0) return vector<PT>(0) ;
    vector<PT> hull ;
    vector <PT> L, U;
    sort (p.begin() , p.end()) ;

    for(int i = 0 ; i < p.size() ; i++) {
        while(L.size() >= 2 and orient(L[L.size()-2] , L.back() , p[i]) <= 0) {
            L.pop_back() ;
        }
        L.push_back(p[i]) ;
    }

    for(int i = (int)p.size()-1 ; i >= 0 ; i--) {
        while(U.size() >= 2 and orient(U[U.size()-2] , U.back() , p[i]) <= 0) {
            U.pop_back() ;
        }
        U.push_back(p[i]) ;
    }

    for(int i = 0 ; i < L.size() ; i++) hull.push_back(L[i]) ;
    if (L.back()!=U[0]) hull.push_back(U[0]) ;
    for(int i = 1 ; i + 1 < U.size() ; i++) hull.push_back(U[i]) ;
    if (U.back()!=L[0]) hull.push_back(U.back()) ;
    if( hull.size() == 2 && hull[0] == hull[1] ) hull.pop_back() ;
    return hull ;
}

struct data{
    int a , d , p ;
    bool operator<(data other){ return a-d < other.a-other.d ; }
}ara[maxn];

vector<PT> getHull(int b, int e)
{
    if(b>=e) return vector<PT>(0) ;

    int m = (b+e)/2 ;
    vector<PT> p1 = getHull(b,m) , p2 = getHull(m+1,e) ;
    vector<PT> p3 , p4 ;
    for(int i=b ; i<=m ; i++)
    {
        p3.pb( PT(ara[i].d,ara[i].p) ) ;
    }
    for(int i=m+1 ; i<=e ; i++)
    {
        p4.pb( PT(ara[i].a,ara[i].p) ) ;
    }
    p3 = monotone_chain(p3) ; p4 = monotone_chain(p4) ;
    vector<PT> p = MinkowskiSum(p3,p4) ;
    for(int i=0 ; i<p1.size() ; i++) p.pb(p1[i]) ;
    for(int i=0 ; i<p2.size() ; i++) p.pb(p2[i]) ;

    p = monotone_chain(p) ;
    return p ;
}

vector<PT> hull ;

void Init(vector<int> a , vector<int> d , vector<int> p)
{
    int n = a.size() ;
    for(int i=1 ; i<=n ; i++)
    {
        ara[i].a = a[i-1] ;
        ara[i].d = d[i-1] ;
        ara[i].p = p[i-1] ;
    }
    sort(ara+1,ara+n+1) ;

    vector<PT> h = getHull(1,n) ;

    sort(h.begin(),h.end()) ;
    hull = h ;

   // for(auto p: hull) cout<<p<<endl ;
   // return ;

    int idx = 0 ;
    for(int i=0 ; i<hull.size() ; i++)
    {
        while( idx>0 && hull[idx-1].y <= hull[i].y ) idx-- ;
        hull[idx] = hull[i] ;
        idx++ ;
    }
 //   printf("%d\n",idx) ;
    hull.erase( hull.begin()+idx , hull.end() ) ;
}

i64 BestSquad(int x, int y)
{
    int l = 0 , r = (int)hull.size() - 1 ;
    PT p(x,y) ;

    while( l+3 <= r )
    {
//        printf("-- %d %d\n",l,r) ;
        int mid1 = l + (r-l)/3 , mid2 = l + (2*(r-l))/3 ;
        if( hull[mid1]*p < hull[mid2]*p ) l = mid1 ;
        else r = mid2 ;
    }
    i64 ans = hull[l]*p ;
    for(int i=l ; i<=r ; i++) ans = max( ans , hull[i]*p ) ;
    return ans ;
}

vector<PT> getPoints(int n)
{
    vector<PT> points ;
    for(int i=0 ; i<n ; i++)
    {
        PT p ;
        p.x = rng()%100 ;
        p.y = rng()%100 ;
        points.pb(p) ;
    }
    return points ;
}
/*
int main()
{
    int n = 1000 ;

    vector<int> a , d , p ;

    for(int i=1 ; i<=n ; i++)
    {
        int m = 1000000000 ;
        a.pb( rng()%m + 1 ) ;
        d.pb( rng()%m + 1 ) ;
        p.pb( rng()%m + 1 ) ;
    }

    Init(a,d,p) ;

    for(auto p: hull) cout<<p<<endl ;

    int cnt = 50 ;
    while(cnt--)
    {
        int x , y ;
        x = rng()%10000 + 1 ; y = rng()%10000 + 1 ;
        printf("%d %d\n",x,y) ;
        //scanf("%d %d",&x,&y) ;
        i64 ansbrute = 0 ;
        for(int i=0 ; i<n ; i++)
        {
            for(int j=0 ; j<n ; j++)
            {
                if(i==j) continue ;
                ansbrute = max( ansbrute , 1LL*x*(a[i]+d[j]) + 1LL*y*(p[i]+p[j]) ) ;
            }
        }
        i64 mainans = 0 ;
        for(int i=0 ; i<hull.size() ; i++)
        {
            mainans = max( 1LL*mainans , 1LL*hull[i].x*x + 1LL*hull[i].y*y ) ;
        }
        printf("brute: %lld   main: %lld best: %lld\n",ansbrute,mainans,BestSquad(x,y)) ;
        if( ansbrute != BestSquad(x,y) )
        {
            printf("------------\n") ;
            return 0 ;
        }
    }


    vector<PT> p1 = getPoints(n) , p2 = getPoints(n) ;
    p1 = monotone_chain(p1) ; p2 = monotone_chain(p2) ;
    p2 = p1 ;
    vector<PT> p3 ;
    vector<PT> p5 , p4 ;
    for(int i=0 ; i<p1.size() ; i++)
    {
        for(int j=0 ; j<p2.size() ; j++) p5.pb( p1[i]+p2[j] ) ;
    }
    p5 = monotone_chain(p5) ;
    p3 = MinkowskiSum(p1,p2) ; //our template code
    p4 = minkowskiSum(p1,p2) ; //tfg's code

    p3 = monotone_chain(p3) ;
    p4 = monotone_chain(p4) ;

    for(auto p:p3) cout<<p<<endl ;
    cout<<endl<<endl ;
    for(auto p:p4) cout<<p<<endl ;
    cout<<endl<<endl ;

    sort(p3.begin(),p3.end()) ;
    sort(p4.begin(),p4.end()) ;

    if(p3==p4) cout<<"yes"<<endl ;
    else cout<<"no"<<endl ;
    cout<<(p3==p4)<<endl ;

    for(auto p:p5) cout<<p<<endl ;

    return 0 ;
}
*/

Compilation message

squad.cpp: In function 'std::vector<PT> minkowskiSum(std::vector<PT>&, std::vector<PT>&)':
squad.cpp:91:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<PT>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |  while(pa + pb + 1 < a.size()+b.size()){
      |        ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
squad.cpp: In function 'void process(std::vector<PT>&)':
squad.cpp:116:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<PT>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |   for (int i=0; i<P.size(); i++)
      |                 ~^~~~~~~~~
squad.cpp: In function 'std::vector<PT> MinkowskiSum(std::vector<PT>, std::vector<PT>)':
squad.cpp:132:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<PT>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |   for(int i=1; i<C.size(); i++) C[i]=C[i]+C[i-1];
      |                ~^~~~~~~~~
squad.cpp: In function 'std::vector<PT> monotone_chain(std::vector<PT>&, bool)':
squad.cpp:144:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<PT>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  144 |     for(int i = 0 ; i < p.size() ; i++) {
      |                     ~~^~~~~~~~~~
squad.cpp:158:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<PT>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  158 |     for(int i = 0 ; i < L.size() ; i++) hull.push_back(L[i]) ;
      |                     ~~^~~~~~~~~~
squad.cpp:160:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<PT>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  160 |     for(int i = 1 ; i + 1 < U.size() ; i++) hull.push_back(U[i]) ;
      |                     ~~~~~~^~~~~~~~~~
squad.cpp: In function 'std::vector<PT> getHull(int, int)':
squad.cpp:188:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<PT>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  188 |     for(int i=0 ; i<p1.size() ; i++) p.pb(p1[i]) ;
      |                   ~^~~~~~~~~~
squad.cpp:189:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<PT>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  189 |     for(int i=0 ; i<p2.size() ; i++) p.pb(p2[i]) ;
      |                   ~^~~~~~~~~~
squad.cpp: In function 'void Init(std::vector<int>, std::vector<int>, std::vector<int>)':
squad.cpp:217:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<PT>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  217 |     for(int i=0 ; i<hull.size() ; i++)
      |                   ~^~~~~~~~~~~~

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 1487 ms 28464 KB Output is correct
4 Correct 1484 ms 28208 KB Output is correct
5 Correct 107 ms 5000 KB Output is correct
6 Correct 2008 ms 70508 KB Output is correct
7 Correct 2023 ms 70184 KB Output is correct
8 Correct 2017 ms 70440 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 10 ms 640 KB Output is correct
3 Correct 1330 ms 26380 KB Output is correct
4 Correct 1347 ms 26120 KB Output is correct
5 Correct 66 ms 2696 KB Output is correct
6 Correct 2053 ms 57868 KB Output is correct
7 Correct 2070 ms 57160 KB Output is correct
8 Correct 2059 ms 56700 KB Output is correct

Subtask #3
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 1487 ms 28464 KB Output is correct
4 Correct 1484 ms 28208 KB Output is correct
5 Correct 107 ms 5000 KB Output is correct
6 Correct 2008 ms 70508 KB Output is correct
7 Correct 2023 ms 70184 KB Output is correct
8 Correct 2017 ms 70440 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 10 ms 640 KB Output is correct
11 Correct 1330 ms 26380 KB Output is correct
12 Correct 1347 ms 26120 KB Output is correct
13 Correct 66 ms 2696 KB Output is correct
14 Correct 2053 ms 57868 KB Output is correct
15 Correct 2070 ms 57160 KB Output is correct
16 Correct 2059 ms 56700 KB Output is correct
17 Correct 73 ms 5368 KB Output is correct
18 Correct 15 ms 768 KB Output is correct
19 Correct 1658 ms 28508 KB Output is correct
20 Correct 1673 ms 28560 KB Output is correct
21 Correct 79 ms 2976 KB Output is correct
22 Correct 2318 ms 70788 KB Output is correct
23 Correct 2327 ms 70540 KB Output is correct
24 Correct 2326 ms 70596 KB Output is correct