Submission #150460

#	Time	Username	Problem	Language	Result	Execution time	Memory
150460		----MIT합격선---- (#200)	Organizing the Best Squad (FXCUP4_squad)	C++17	0 / 100	32 ms	16048 KiB

squad

#include "squad.h"

#include <stdio.h>
#include <math.h>
#include <vector>
#include <algorithm>
#define LL long long
#define pll pair<LL,LL>
#define pdxyi pair<double,xyi>
#define ff first
#define ss second
#define INF 1e18
using namespace std;

struct xyi{
    LL x,y;
    int idx;

    bool operator<(const xyi A)const{
        if(y!=A.y) return y<A.y;
        return x<A.x;
    }
};

pdxyi AV[333333];
vector<xyi> ACH1,ACH2[333333];

pdxyi DV[333333];
vector<xyi> DCH1,DCH2[333333];

LL ccw(xyi p,xyi q,xyi r){
    return (p.x*q.y+q.x*r.y+r.x*p.y)-(p.y*q.x+q.y*r.x+r.y*p.x);
}

LL dist(xyi p,xyi q){
    return (p.x-q.x)*(p.x-q.x)+(p.y-q.y)*(p.y-q.y);
}

void Init(std::vector<int> A, std::vector<int> D, std::vector<int> P){
	int n = A.size();

    for(int i=1;i<=n;i++) AV[i].ss={A[i-1],P[i-1],0};
    for(int i=1;i<=n;i++) AV[i].ff=atan2(AV[i].ss.y,AV[i].ss.x);
    sort(AV+1,AV+n+1);
    for(int i=1;i<=n;i++) AV[i].ss.idx=i;

    ACH1.push_back({0,0,0});
    for(int i=1;i<=n;i++){
        while(ACH1.size()>=2 && ccw(ACH1[ACH1.size()-2],ACH1[ACH1.size()-1],AV[i].ss)<=0) ACH1.pop_back();
        ACH1.push_back(AV[i].ss);
    }
    ACH1.push_back({0,0,n+1});

    for(int i=1;i<ACH1.size()-1;i++){
        ACH2[i].push_back({0,0,0});

        for(int j=max(1,ACH1[i-1].idx);j<=min(n,ACH1[i+1].idx);j++){
            if(j==ACH1[i].idx) continue;

            while(ACH2[i].size()>=2 && ccw(ACH2[i][ACH2[i].size()-2],ACH2[i][ACH2[i].size()-1],AV[j].ss)<=0) ACH2[i].pop_back();
            ACH2[i].push_back(AV[j].ss);
        }

        ACH2[i].push_back({0,0,n+1});
    }

    /*
    printf("%d - ",ACH1.size());
    for(xyi p:ACH1) printf("%d ",p.idx); printf("\n");

    for(int i=1;i<ACH1.size()-1;i++){
        printf("%d - ",ACH2[i].size());
        for(xyi p:ACH2[i]) printf("%d ",p.idx); printf("\n");
    }
    */

    for(int i=1;i<=n;i++) DV[i].ss={D[i-1],P[i-1],0};
    for(int i=1;i<=n;i++) DV[i].ff=atan2(DV[i].ss.y,DV[i].ss.x);
    sort(DV+1,DV+n+1);
    for(int i=1;i<=n;i++) DV[i].ss.idx=i;

    DCH1.push_back({0,0,0});
    for(int i=1;i<=n;i++){
        while(DCH1.size()>=2 && ccw(DCH1[DCH1.size()-2],DCH1[DCH1.size()-1],DV[i].ss)<=0) DCH1.pop_back();
        DCH1.push_back(DV[i].ss);
    }
    DCH1.push_back({0,0,n+1});

    for(int i=1;i<DCH1.size()-1;i++){
        DCH2[i].push_back({0,0,0});

        for(int j=max(1,DCH1[i-1].idx);j<=min(n,DCH1[i+1].idx);j++){
            if(j==DCH1[i].idx) continue;

            while(DCH2[i].size()>=2 && ccw(DCH2[i][DCH2[i].size()-2],DCH2[i][DCH2[i].size()-1],DV[j].ss)<=0) DCH2[i].pop_back();
            DCH2[i].push_back(DV[j].ss);
        }

        DCH2[i].push_back({0,0,n+1});
    }

    return;
}

int X,Y;

LL Af1(int i){
    return ACH1[i].x*X+ACH1[i].y*Y;
}

LL Af2(int i,int j){
    return ACH2[i][j].x*X+ACH2[i][j].y*Y;
}

LL Df1(int i){
    return DCH1[i].x*X+DCH1[i].y*Y;
}

LL Df2(int i,int j){
    return DCH2[i][j].x*X+DCH2[i][j].y*Y;
}

long long BestSquad(int _X, int _Y){
    X=_X; Y=_Y;
    int a1,a2,d1,d2;

    int s1=0,e1=ACH1.size()-1,m1;
    while(s1<=e1){
        m1=(s1+e1)>>1;

        if(Af1(m1)<Af1(m1+1)) s1=m1+1;
        else e1=m1-1;
    }
    a1=s1;

    int s2=0,e2=ACH2[a1].size()-1,m2;
    while(s2<=e2){
        m2=(s2+e2)>>1;

        if(Af2(a1,m2)<Af2(a1,m2+1)) s2=m2+1;
        else e2=m2-1;
    }
    a2=s2;

    s1=0,e1=DCH1.size()-1,m1;
    while(s1<=e1){
        m1=(s1+e1)>>1;

        if(Df1(m1)<Df1(m1+1)) s1=m1+1;
        else e1=m1-1;
    }
    d1=s1;

    s2=0,e2=DCH2[d1].size()-1,m2;
    while(s2<=e2){
        m2=(s2+e2)>>1;

        if(Df2(d1,m2)<Df2(d1,m2+1)) s2=m2+1;
        else e2=m2-1;
    }
    d2=s2;

    if(ACH1[a1].idx!=DCH1[d1].idx) return Af1(a1)+Df1(d1);
	return max(Af1(a1)+Df2(d1,d2),Af2(a1,a2)+Df1(d1));
}

Compilation message (stderr)

squad.cpp: In function 'void Init(std::vector<int>, std::vector<int>, std::vector<int>)':
squad.cpp:54:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=1;i<ACH1.size()-1;i++){
                 ~^~~~~~~~~~~~~~
squad.cpp:89:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=1;i<DCH1.size()-1;i++){
                 ~^~~~~~~~~~~~~~
squad.cpp: In function 'long long int BestSquad(int, int)':
squad.cpp:145:29: warning: right operand of comma operator has no effect [-Wunused-value]
     s1=0,e1=DCH1.size()-1,m1;
                             ^
squad.cpp:154:33: warning: right operand of comma operator has no effect [-Wunused-value]
     s2=0,e2=DCH2[d1].size()-1,m2;
                                 ^

• Subtask 1: 0 / 19
• Subtask 2: 0 / 28
• Subtask 3: 0 / 53