Submission #302960

#	Time	Username	Problem	Language	Result	Execution time	Memory
302960		Arg_007	Organizing the Best Squad (FXCUP4_squad)	C++17	100 / 100	2306 ms	55132 KiB

squad

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

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