제출 #150658

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
150658		----MIT합격선---- (#200)	최적의 팀 구성 (FXCUP4_squad)	C++17	100 / 100	1197 ms	123896 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 pdxyio pair<double,xyio>
#define ff first
#define ss second
#define INF 1e18
using namespace std;

struct xyio{
    LL x,y;
    int idx,ord;

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

pdxyio AV[333333];
vector<xyio> ACH1,ACH2[333333];

pdxyio DV[333333];
vector<xyio> DCH1,DCH2[333333];

LL ccw(xyio p,xyio q,xyio 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(xyio p,xyio 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],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.ord=i;

    ACH1.push_back({0,0,-1,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,-1,n+1});

    for(int i=1;i<ACH1.size()-1;i++){
        ACH2[i].push_back({0,0,-1,0});
        for(int j=max(1,ACH1[i-1].ord);j<=min(n,ACH1[i+1].ord);j++){
            if(j==ACH1[i].ord) 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,-1,n+1});
    }
/*
    printf("%d - ",ACH1.size());
    for(xyio p:ACH1) printf("%d%d ",p.ord,p.idx); printf("\n");

    for(int i=1;i<ACH1.size()-1;i++){
        printf("%d - ",ACH2[i].size());
        for(xyio p:ACH2[i]) printf("%d%d ",p.ord,p.idx); printf("\n");
    }
    printf("\n");
*/
    for(int i=1;i<=n;i++) DV[i].ss={D[i-1],P[i-1],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.ord=i;

    DCH1.push_back({0,0,-1,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,-1,n+1});

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

        for(int j=max(1,DCH1[i-1].ord);j<=min(n,DCH1[i+1].ord);j++){
            if(j==DCH1[i].ord) 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,-1,n+1});
    }
/*
    printf("%d - ",DCH1.size());
    for(xyio p:DCH1) printf("%d%d ",p.ord,p.idx); printf("\n");

    for(int i=1;i<DCH1.size()-1;i++){
        printf("%d - ",DCH2[i].size());
        for(xyio p:DCH2[i]) printf("%d%d ",p.ord,p.idx); printf("\n");
    }
    printf("\n");
*/
    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;

    //printf("%d %d\n%d %d\n",ACH1[a1].idx,ACH2[a1][a2].idx,DCH1[d1].idx,DCH2[d1][d2].idx);

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

컴파일 시 표준 에러 (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:86: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:151:29: warning: right operand of comma operator has no effect [-Wunused-value]
     s1=0,e1=DCH1.size()-1,m1;
                             ^
squad.cpp:160:33: warning: right operand of comma operator has no effect [-Wunused-value]
     s2=0,e2=DCH2[d1].size()-1,m2;
                                 ^

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