Submission #157229

#	Time	Username	Problem	Language	Result	Execution time	Memory
157229		combi1k1	별자리 2 (JOI14_constellation2)	C++14	100 / 100	1424 ms	940 KiB

constellation2

#include<bits/stdc++.h>

using namespace std;

#define int     long long
#define X       first
#define Y       second
#define sz(x)   (int)x.size()
#define all(x)  x.begin(),x.end()

typedef pair<int,int>   ii;
typedef pair<int,ii>    poi;

vector<poi> Star;

bool cmp(poi A,poi B)   {
    int xa = A.Y.X;
    int ya = A.Y.Y;
    int xb = B.Y.X;
    int yb = B.Y.Y;
    return  xa * yb >= ya * xb;
}

int cntLef[3];
int cntRig[3];

signed main()   {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n;  cin >> n;

    for(int i = 0 ; i < n ; ++i)    {
        int x;  cin >> x;
        int y;  cin >> y;
        int c;  cin >> c;

        Star.push_back(poi(c,{x,y}));
    }

    int ans = 0;

    for(poi O : Star)   {
        vector<poi> lef;
        vector<poi> rig;

        memset(cntLef,0,sizeof cntLef);
        memset(cntRig,0,sizeof cntRig);

        for(poi P : Star)   if (P != O) {
            P.Y.X -= O.Y.X;
            P.Y.Y -= O.Y.Y;
            if (P.Y > ii(0,0))
                rig.push_back(P),
                cntRig[P.X]++;
            if (P.Y < ii(0,0))
                P.Y.X = -P.Y.X,
                P.Y.Y = -P.Y.Y,
                lef.push_back(P),
                cntLef[P.X]++;
        }
        sort(all(lef),cmp);
        sort(all(rig),cmp);

        int ptr = 0;

        for(poi P : rig)    {
            cntRig[P.X]--;
            cntLef[P.X]++;
            while(ptr < sz(lef) && cmp(lef[ptr],P))
                cntRig[lef[ptr].X]++,
                cntLef[lef[ptr].X]--,
                ptr++;
            int cur = 1;
            for(int i = 0 ; i < 3 ; ++i)    {
                if (i != O.X)   cur *= cntRig[i];
                if (i != P.X)   cur *= cntLef[i];
            }
            ans += cur;
        }
    }

    cout << ans << endl;
}

• Subtask 1: 15 / 15
• Subtask 2: 40 / 40
• Subtask 3: 45 / 45