oj.uz

Submission #157226

# Submission time Handle Problem Language Result Execution time Memory
157226 2019-10-10T08:03:19 Z combi1k1 별자리 2 (JOI14_constellation2) C++14
55 / 100
 336 ms 504 KB 
#include<bits/stdc++.h>

using namespace std;

#define ll      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  1ll * xa * yb >= 1ll * ya * xb;
}

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

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

    ll  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 376 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 252 KB Output is correct
5 Correct 2 ms 504 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 256 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 256 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 3 ms 376 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 5 ms 376 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 376 KB Output is correct
9 Correct 14 ms 376 KB Output is correct
10 Correct 11 ms 376 KB Output is correct
11 Correct 14 ms 376 KB Output is correct
12 Correct 14 ms 376 KB Output is correct

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 376 KB Output is correct
2 Correct 115 ms 424 KB Output is correct
3 Correct 148 ms 420 KB Output is correct
4 Correct 153 ms 376 KB Output is correct
5 Incorrect 336 ms 504 KB Output isn't correct
6 Halted 0 ms 0 KB -