oj.uz

Submission #150060

# Submission time Handle Problem Language Result Execution time Memory
150060 2019-09-01T07:38:42 Z 맞WATLE(#3593, arnold518, ksmzzang2003, songc) Organizing the Best Squad (FXCUP4_squad) C++17
100 / 100
 1744 ms 78900 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 5 ms 384 KB Output is correct
2 Correct 6 ms 512 KB Output is correct
3 Correct 426 ms 53092 KB Output is correct
4 Correct 410 ms 53092 KB Output is correct
5 Correct 27 ms 5556 KB Output is correct
6 Correct 345 ms 78900 KB Output is correct
7 Correct 336 ms 78748 KB Output is correct
8 Correct 347 ms 78776 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 12 ms 896 KB Output is correct
3 Correct 776 ms 65740 KB Output is correct
4 Correct 768 ms 65868 KB Output is correct
5 Correct 38 ms 3492 KB Output is correct
6 Correct 1083 ms 78776 KB Output is correct
7 Correct 1086 ms 78776 KB Output is correct
8 Correct 1159 ms 78772 KB Output is correct

Subtask #3
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 6 ms 512 KB Output is correct
3 Correct 426 ms 53092 KB Output is correct
4 Correct 410 ms 53092 KB Output is correct
5 Correct 27 ms 5556 KB Output is correct
6 Correct 345 ms 78900 KB Output is correct
7 Correct 336 ms 78748 KB Output is correct
8 Correct 347 ms 78776 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 12 ms 896 KB Output is correct
11 Correct 776 ms 65740 KB Output is correct
12 Correct 768 ms 65868 KB Output is correct
13 Correct 38 ms 3492 KB Output is correct
14 Correct 1083 ms 78776 KB Output is correct
15 Correct 1086 ms 78776 KB Output is correct
16 Correct 1159 ms 78772 KB Output is correct
17 Correct 132 ms 2808 KB Output is correct
18 Correct 13 ms 896 KB Output is correct
19 Correct 784 ms 53096 KB Output is correct
20 Correct 790 ms 53092 KB Output is correct
21 Correct 50 ms 3752 KB Output is correct
22 Correct 1526 ms 78644 KB Output is correct
23 Correct 1633 ms 78776 KB Output is correct
24 Correct 1744 ms 78772 KB Output is correct