oj.uz

Submission #149741

# Submission time Handle Problem Language Result Execution time Memory
149741 2019-09-01T07:03:53 Z 맞WATLE(#3593, arnold518, ksmzzang2003, songc) Organizing the Best Squad (FXCUP4_squad) C++17
0 / 100
 430 ms 53100 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; };
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;
    vector<Point> arr;
    vector<Point> CH;
    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 return dist(s, p)<dist(s, q);
        });

        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();

        for(i=0; i<N; i++)
        {
            Point t=CH[(i+1)%N]-CH[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(N==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;

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

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

        if(uy>dy) return ut;
        else return dt;
    }
} 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();
}

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++)
    {
        if(CA[i].num==CB[i].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:53:16: warning: unused variable 'j' [-Wunused-variable]
         int i, j;
                ^
squad.cpp: In member function 'int Snipe::query(ll, ll)':
squad.cpp:81:13: warning: unused variable 'i' [-Wunused-variable]
         int i, j;
             ^
squad.cpp:81: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:120: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:124: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:106:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
squad.cpp: In function 'll BestSquad(int, int)':
squad.cpp:152: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:152: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
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 7 ms 512 KB Output is correct
3 Correct 430 ms 53096 KB Output is correct
4 Correct 419 ms 53100 KB Output is correct
5 Incorrect 26 ms 4532 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 7 ms 512 KB Output is correct
3 Correct 430 ms 53096 KB Output is correct
4 Correct 419 ms 53100 KB Output is correct
5 Incorrect 26 ms 4532 KB Output isn't correct
6 Halted 0 ms 0 KB -