oj.uz

Submission #152479

# Submission time Handle Problem Language Result Execution time Memory
152479 2019-09-08T06:50:52 Z arnold518 Organizing the Best Squad (FXCUP4_squad) C++17
100 / 100
 1381 ms 87764 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 252 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 449 ms 54336 KB Output is correct
4 Correct 448 ms 54228 KB Output is correct
5 Correct 24 ms 5932 KB Output is correct
6 Correct 382 ms 80028 KB Output is correct
7 Correct 385 ms 80012 KB Output is correct
8 Correct 384 ms 79984 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 396 KB Output is correct
2 Correct 8 ms 1144 KB Output is correct
3 Correct 785 ms 67044 KB Output is correct
4 Correct 783 ms 67048 KB Output is correct
5 Correct 33 ms 3904 KB Output is correct
6 Correct 1008 ms 79956 KB Output is correct
7 Correct 1006 ms 80024 KB Output is correct
8 Correct 1052 ms 80008 KB Output is correct

Subtask #3
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 252 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 449 ms 54336 KB Output is correct
4 Correct 448 ms 54228 KB Output is correct
5 Correct 24 ms 5932 KB Output is correct
6 Correct 382 ms 80028 KB Output is correct
7 Correct 385 ms 80012 KB Output is correct
8 Correct 384 ms 79984 KB Output is correct
9 Correct 2 ms 396 KB Output is correct
10 Correct 8 ms 1144 KB Output is correct
11 Correct 785 ms 67044 KB Output is correct
12 Correct 783 ms 67048 KB Output is correct
13 Correct 33 ms 3904 KB Output is correct
14 Correct 1008 ms 79956 KB Output is correct
15 Correct 1006 ms 80024 KB Output is correct
16 Correct 1052 ms 80008 KB Output is correct
17 Correct 133 ms 4372 KB Output is correct
18 Correct 10 ms 1016 KB Output is correct
19 Correct 842 ms 54584 KB Output is correct
20 Correct 849 ms 54656 KB Output is correct
21 Correct 48 ms 4360 KB Output is correct
22 Correct 1381 ms 80344 KB Output is correct
23 Correct 1380 ms 80224 KB Output is correct
24 Correct 1348 ms 87764 KB Output is correct