oj.uz

Submission #302960

# Submission time Handle Problem Language Result Execution time Memory
302960 2020-09-19T14:48:44 Z Arg_007 Organizing the Best Squad (FXCUP4_squad) C++17
100 / 100
 2306 ms 55132 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 1 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 1481 ms 19564 KB Output is correct
4 Correct 1470 ms 19696 KB Output is correct
5 Correct 107 ms 4272 KB Output is correct
6 Correct 1945 ms 54796 KB Output is correct
7 Correct 1968 ms 54392 KB Output is correct
8 Correct 1966 ms 54388 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 11 ms 640 KB Output is correct
3 Correct 1338 ms 19640 KB Output is correct
4 Correct 1367 ms 19588 KB Output is correct
5 Correct 65 ms 2308 KB Output is correct
6 Correct 2053 ms 47956 KB Output is correct
7 Correct 2062 ms 47960 KB Output is correct
8 Correct 2074 ms 48224 KB Output is correct

Subtask #3
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 1481 ms 19564 KB Output is correct
4 Correct 1470 ms 19696 KB Output is correct
5 Correct 107 ms 4272 KB Output is correct
6 Correct 1945 ms 54796 KB Output is correct
7 Correct 1968 ms 54392 KB Output is correct
8 Correct 1966 ms 54388 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 11 ms 640 KB Output is correct
11 Correct 1338 ms 19640 KB Output is correct
12 Correct 1367 ms 19588 KB Output is correct
13 Correct 65 ms 2308 KB Output is correct
14 Correct 2053 ms 47956 KB Output is correct
15 Correct 2062 ms 47960 KB Output is correct
16 Correct 2074 ms 48224 KB Output is correct
17 Correct 71 ms 2940 KB Output is correct
18 Correct 18 ms 768 KB Output is correct
19 Correct 1655 ms 19604 KB Output is correct
20 Correct 1651 ms 20084 KB Output is correct
21 Correct 79 ms 2988 KB Output is correct
22 Correct 2280 ms 54948 KB Output is correct
23 Correct 2306 ms 55132 KB Output is correct
24 Correct 2283 ms 54884 KB Output is correct