oj.uz

답안 #149965

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
149965 2019-09-01T07:28:43 Z 맞WATLE(#3593, arnold518, ksmzzang2003, songc) 최적의 팀 구성 (FXCUP4_squad) C++17
0 / 100
 435 ms 53096 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;

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

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;
        //printf("%d %d\n", CA[i].num, CB[i].num);
        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:138: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:142: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:124:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
squad.cpp: In function 'll BestSquad(int, int)':
squad.cpp:170: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:170: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

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 432 KB Output is correct
2 Correct 7 ms 512 KB Output is correct
3 Correct 435 ms 53096 KB Output is correct
4 Correct 415 ms 53016 KB Output is correct
5 Incorrect 25 ms 5428 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 432 KB Output is correct
2 Correct 7 ms 512 KB Output is correct
3 Correct 435 ms 53096 KB Output is correct
4 Correct 415 ms 53016 KB Output is correct
5 Incorrect 25 ms 5428 KB Output isn't correct
6 Halted 0 ms 0 KB -