Submission #152479

#	Time	Username	Problem	Language	Result	Execution time	Memory
152479		arnold518	Organizing the Best Squad (FXCUP4_squad)	C++17	100 / 100	1381 ms	87764 KiB

squad

#include "squad.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 3e5;
const ll INF = numeric_limits<ll>::max();

int N;
vector<int> A, D, P;

struct Point
{
    ll x, y; int num;
    bool operator == (const Point &p) { return p.x==x && p.y==y;  }
};
Point operator - (const Point& p, const Point& q) { return { p.x-q.x, p.y-q.y, q.num }; }

struct Snipe
{
    ll ccw(const Point& p1, const Point& p2)
    {
        ll t=p1.x*p2.y-p1.y*p2.x;
        if(t==0) return t;
        else return t/abs(t);
    }

    ll ccw(const Point& p, const Point& q1, const Point& q2)
    {
        return ccw(q1-p, q2-p);
    }

    ll dist(const Point& p, const Point& q)
    {
        return (p.x-q.x)*(p.x-q.x)+(p.y-q.y)*(p.y-q.y);
    }

    bool cmp(const Point& p, const Point& q)
    {
        if(ccw(s, p, q)!=0) return ccw(s, p, q)>0;
        else return dist(s, p)<dist(s, q);
    }

    int N, NN;
    vector<Point> arr;
    vector<Point> CH, CH2;
    vector<Point> up, down;
    Point s={INF, INF};

    void add(Point p) { arr.push_back(p); }

    void ConvexHull()
    {
        int i, j;
        N=arr.size();

        for(i=0; i<N; i++) if(arr[i].y<s.y || (arr[i].y==s.y && arr[i].x<s.x)) s=arr[i];
        sort(arr.begin(), arr.end(), [&](const Point& p, const Point& q)
        {
            if(ccw(s, p, q)!=0) return ccw(s, p, q)>0;
            else if(dist(s, p)!=dist(s, q)) return dist(s, p)<dist(s, q);
            else return p.num<q.num;
        });

        for(i=0; i<N; i++)
        {
            while(2<=CH.size() && ccw(CH[CH.size()-2], CH[CH.size()-1], arr[i])<0) CH.pop_back();
            CH.push_back(arr[i]);
        }
        N=CH.size();

        CH2=CH;
        CH2.erase(unique(CH2.begin(), CH2.end()), CH2.end()); NN=CH2.size();

        for(i=0; i<NN; i++)
        {
            Point t=CH2[(i+1)%NN]-CH2[i];

            if(t.y>0 || (t.y==0 && t.x>0)) up.push_back(t);
            else down.push_back(t);
        }
    }

    int query(ll a, ll b)
    {
        int i, j;
        if(NN==0) return -1;

        Point ul={b, -a}, dl={b, -a};
        if(ul.y<0) ul.x*=-1, ul.y*=-1;
        if(dl.y>0) dl.x*=-1, dl.y*=-1;

        int ut=lower_bound(up.begin(), up.end(), ul, [&](const Point &p, const Point &q){ return ccw(p, q)>=0; })-up.begin();
        int dt=lower_bound(down.begin(), down.end(), dl, [&](const Point& p, const Point& q){ return ccw(p, q)>=0; })-down.begin();

        dt+=up.size();
        if(dt==N) dt=0;

        if(NN==1) ut=dt=0;

        ll uy=b*CH2[ut].y+a*CH2[ut].x;
        ll dy=b*CH2[dt].y+a*CH2[dt].x;

        //printf("WOW %lld %lld : %d %d / %d\n", a, b, ut, dt, N);

        if(uy>dy) return lower_bound(CH.begin(), CH.end(), CH2[ut], [&](const Point& p, const Point& q)
        {
            if(ccw(s, p, q)!=0) return ccw(s, p, q)>0;
            else if(dist(s, p)!=dist(s, q)) return dist(s, p)<dist(s, q);
            else return p.num<q.num;
        })-CH.begin();
        else return lower_bound(CH.begin(), CH.end(), CH2[dt], [&](const Point& p, const Point& q)
        {
            if(ccw(s, p, q)!=0) return ccw(s, p, q)>0;
            else if(dist(s, p)!=dist(s, q)) return dist(s, p)<dist(s, q);
            else return p.num<q.num;
        })-CH.begin();
    }
} SA1, SA2, SB1, SB2;

void Init(vector<int> _A, vector<int> _D, vector<int> _P)
{
    int i, j;
    A=_A; D=_D; P=_P; N=A.size();

    for(i=0; i<N; i++)
    {
        SA1.add({A[i], P[i], i});
        SB1.add({D[i], P[i], i});
    }

    SA1.ConvexHull();
    SB1.ConvexHull();

    vector<int> chk;
    chk=vector<int>(N);
    for(i=0; i<SA1.CH.size(); i++) chk[SA1.CH[i].num]=1;
    for(i=0; i<N; i++) if(!chk[i]) SA2.add({A[i], P[i], i});

    chk=vector<int>(N);
    for(i=0; i<SB1.CH.size(); i++) chk[SB1.CH[i].num]=1;
    for(i=0; i<N; i++) if(!chk[i]) SB2.add({D[i], P[i], i});

    SA2.ConvexHull();
    SB2.ConvexHull();

    //for(i=0; i<SA1.CH2.size(); i++) printf("%lld %lld %d\n", SA1.CH2[i].x, SA1.CH2[i].y, SA1.CH2[i].num); printf("==========\n");
    //for(i=0; i<SA2.CH.size(); i++) printf("%lld %lld %d\n", SA2.CH[i].x, SA2.CH[i].y, SA2.CH[i].num); printf("==========\n");

    //for(i=0; i<SB1.CH2.size(); i++) printf("%lld %lld %d\n", SB1.CH2[i].x, SB1.CH2[i].y, SB1.CH2[i].num); printf("==========\n");
    //for(i=0; i<SB2.CH.size(); i++) printf("%lld %lld %d\n", SB2.CH[i].x, SB2.CH[i].y, SB2.CH[i].num); printf("==========\n");
}

ll BestSquad(int X, int Y)
{
    int i, j;

    vector<Point> CA, CB;

    int t=SA1.query(X, Y);
    CA.push_back(SA1.CH[t]);
    CA.push_back(SA1.CH[(t+1)%SA1.N]);
    CA.push_back(SA1.CH[(t+SA1.N-1)%SA1.N]);
    t=SA2.query(X, Y);
    if(t!=-1) CA.push_back(SA2.CH[SA2.query(X, Y)]);

    t=SB1.query(X, Y);
    CB.push_back(SB1.CH[t]);
    CB.push_back(SB1.CH[(t+1)%SB1.N]);
    CB.push_back(SB1.CH[(t+SB1.N-1)%SB1.N]);
    t=SB2.query(X, Y);
    if(t!=-1) CB.push_back(SB2.CH[SB2.query(X, Y)]);

    ll ans=0;
    for(i=0; i<CA.size(); i++) for(j=0; j<CB.size(); j++)
    {
        //printf("!!!%d %d\n", CA[i].num, CB[i].num);
        if(CA[i].num==CB[j].num) continue;
        ans=max(ans, CA[i].x*X+CA[i].y*Y+CB[j].x*X+CB[j].y*Y);
    }
    return ans;
}

Compilation message (stderr)

squad.cpp: In member function 'void Snipe::ConvexHull()':
squad.cpp:57:16: warning: unused variable 'j' [-Wunused-variable]
         int i, j;
                ^
squad.cpp: In member function 'int Snipe::query(ll, ll)':
squad.cpp:89:13: warning: unused variable 'i' [-Wunused-variable]
         int i, j;
             ^
squad.cpp:89:16: warning: unused variable 'j' [-Wunused-variable]
         int i, j;
                ^
squad.cpp: In function 'void Init(std::vector<int>, std::vector<int>, std::vector<int>)':
squad.cpp:140:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0; i<SA1.CH.size(); i++) chk[SA1.CH[i].num]=1;
              ~^~~~~~~~~~~~~~
squad.cpp:144:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0; i<SB1.CH.size(); i++) chk[SB1.CH[i].num]=1;
              ~^~~~~~~~~~~~~~
squad.cpp:126:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
squad.cpp: In function 'll BestSquad(int, int)':
squad.cpp:178:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0; i<CA.size(); i++) for(j=0; j<CB.size(); j++)
              ~^~~~~~~~~~
squad.cpp:178:42: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0; i<CA.size(); i++) for(j=0; j<CB.size(); j++)
                                         ~^~~~~~~~~~

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