oj.uz

Submission #150658

# Submission time Handle Problem Language Result Execution time Memory
150658 2019-09-01T08:47:31 Z ----MIT합격선----(#3601, maruii, Diuven, andy627) Organizing the Best Squad (FXCUP4_squad) C++17
100 / 100
 1197 ms 123896 KB 
#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));
}

Compilation message

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.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 16000 KB Output is correct
2 Correct 16 ms 16128 KB Output is correct
3 Correct 339 ms 41848 KB Output is correct
4 Correct 346 ms 41848 KB Output is correct
5 Correct 44 ms 22768 KB Output is correct
6 Correct 436 ms 121652 KB Output is correct
7 Correct 453 ms 121652 KB Output is correct
8 Correct 433 ms 121784 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 16000 KB Output is correct
2 Correct 20 ms 16256 KB Output is correct
3 Correct 489 ms 44088 KB Output is correct
4 Correct 475 ms 44084 KB Output is correct
5 Correct 41 ms 18932 KB Output is correct
6 Correct 739 ms 83980 KB Output is correct
7 Correct 771 ms 83976 KB Output is correct
8 Correct 784 ms 84012 KB Output is correct

Subtask #3
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 16000 KB Output is correct
2 Correct 16 ms 16128 KB Output is correct
3 Correct 339 ms 41848 KB Output is correct
4 Correct 346 ms 41848 KB Output is correct
5 Correct 44 ms 22768 KB Output is correct
6 Correct 436 ms 121652 KB Output is correct
7 Correct 453 ms 121652 KB Output is correct
8 Correct 433 ms 121784 KB Output is correct
9 Correct 16 ms 16000 KB Output is correct
10 Correct 20 ms 16256 KB Output is correct
11 Correct 489 ms 44088 KB Output is correct
12 Correct 475 ms 44084 KB Output is correct
13 Correct 41 ms 18932 KB Output is correct
14 Correct 739 ms 83980 KB Output is correct
15 Correct 771 ms 83976 KB Output is correct
16 Correct 784 ms 84012 KB Output is correct
17 Correct 94 ms 18552 KB Output is correct
18 Correct 24 ms 16384 KB Output is correct
19 Correct 520 ms 44212 KB Output is correct
20 Correct 531 ms 44216 KB Output is correct
21 Correct 56 ms 20980 KB Output is correct
22 Correct 1174 ms 123892 KB Output is correct
23 Correct 1093 ms 123892 KB Output is correct
24 Correct 1197 ms 123896 KB Output is correct