oj.uz

Submission #157229

# Submission time Handle Problem Language Result Execution time Memory
157229 2019-10-10T08:05:22 Z combi1k1 별자리 2 (JOI14_constellation2) C++14
100 / 100
 1424 ms 940 KB 
#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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 380 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 5 ms 348 KB Output is correct
5 Correct 7 ms 376 KB Output is correct
6 Correct 14 ms 376 KB Output is correct
7 Correct 14 ms 376 KB Output is correct
8 Correct 14 ms 456 KB Output is correct
9 Correct 13 ms 376 KB Output is correct
10 Correct 10 ms 376 KB Output is correct
11 Correct 13 ms 376 KB Output is correct
12 Correct 14 ms 376 KB Output is correct

Subtask #3
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 376 KB Output is correct
2 Correct 113 ms 376 KB Output is correct
3 Correct 146 ms 504 KB Output is correct
4 Correct 150 ms 376 KB Output is correct
5 Correct 340 ms 632 KB Output is correct
6 Correct 592 ms 604 KB Output is correct
7 Correct 970 ms 792 KB Output is correct
8 Correct 1411 ms 836 KB Output is correct
9 Correct 1424 ms 864 KB Output is correct
10 Correct 1407 ms 880 KB Output is correct
11 Correct 1422 ms 904 KB Output is correct
12 Correct 1394 ms 936 KB Output is correct
13 Correct 1398 ms 768 KB Output is correct
14 Correct 1419 ms 856 KB Output is correct
15 Correct 1410 ms 700 KB Output is correct
16 Correct 1400 ms 940 KB Output is correct