oj.uz

Submission #48096

# Submission time Handle Problem Language Result Execution time Memory
48096 2018-05-10T04:55:06 Z choikiwon 별자리 2 (JOI14_constellation2) C++17
100 / 100
 1563 ms 1896 KB 
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

ll cross(pii a, pii b) {
    return 1LL * a.first * b.second - 1LL * a.second * b.first;
}

int N;
struct Point {
    int x, y, c;
};
Point P[3010];
vector<pair<pii, int> > Q;
int cnt[2][3];

bool cmp(pair<pii, int> a, pair<pii, int> b) {
    return cross(a.first, b.first) > 0;
}

int main() {
    scanf("%d", &N);

    for(int i = 0; i < N; i++) {
        scanf("%d %d %d", &P[i].x, &P[i].y, &P[i].c);
    }

    ll ans = 0;
    for(int i = 0; i < N; i++) {
        Q.clear();
        for(int j = 0; j < N; j++) {
            if(i == j) continue;
            int dx = P[j].x - P[i].x;
            int dy = P[j].y - P[i].y;
            if(dy < 0) dy = -dy, dx = -dx;
            else if(dy == 0 && dx < 0) dx = -dx;

            Q.push_back({ {dx, dy}, j });
        }
        sort(Q.begin(), Q.end(), cmp);

        memset(cnt, 0, sizeof(cnt));
        for(int j = 1; j < Q.size(); j++) {
            int idx = Q[j].second;
            int dy = P[idx].y - P[i].y;
            if(dy > 0) cnt[1][ P[idx].c ]++;
            else cnt[0][ P[idx].c ]++;
        }

        int idx = Q[0].second;
        ll tmp = 1;
        for(int j = 0; j < 3; j++) if(j != P[idx].c) tmp *= cnt[0][j];
        for(int j = 0; j < 3; j++) if(j != P[i].c) tmp *= cnt[1][j];
        ans += tmp;

        for(int j = 1; j < Q.size(); j++) {
            int dx = P[idx].x - P[i].x;
            int dy = P[idx].y - P[i].y;
            if(dy > 0 || (dy == 0 && dx > 0)) cnt[0][ P[idx].c ]++;
            else cnt[1][ P[idx].c ]++;

            idx = Q[j].second;
            dy = P[idx].y - P[i].y;
            if(dy > 0) cnt[1][ P[idx].c ]--;
            else cnt[0][ P[idx].c ]--;

            ll tmp = 1;
            for(int k = 0; k < 3; k++) if(k != P[idx].c) tmp *= cnt[0][k];
            for(int k = 0; k < 3; k++) if(k != P[i].c) tmp *= cnt[1][k];
            ans += tmp;
        }
    }
    ans /= 2;
    printf("%lld", ans);
}

Compilation message

constellation2.cpp: In function 'int main()':
constellation2.cpp:45:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 1; j < Q.size(); j++) {
                        ~~^~~~~~~~~~
constellation2.cpp:58:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 1; j < Q.size(); j++) {
                        ~~^~~~~~~~~~
constellation2.cpp:24:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &N);
     ~~~~~^~~~~~~~~~
constellation2.cpp:27:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d", &P[i].x, &P[i].y, &P[i].c);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 808 KB Output is correct
2 Correct 2 ms 808 KB Output is correct
3 Correct 3 ms 864 KB Output is correct
4 Correct 5 ms 872 KB Output is correct
5 Correct 7 ms 876 KB Output is correct
6 Correct 15 ms 880 KB Output is correct
7 Correct 23 ms 884 KB Output is correct
8 Correct 14 ms 888 KB Output is correct
9 Correct 15 ms 896 KB Output is correct
10 Correct 10 ms 1024 KB Output is correct
11 Correct 16 ms 1024 KB Output is correct
12 Correct 14 ms 1024 KB Output is correct

Subtask #3
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 1080 KB Output is correct
2 Correct 126 ms 1240 KB Output is correct
3 Correct 162 ms 1268 KB Output is correct
4 Correct 155 ms 1284 KB Output is correct
5 Correct 359 ms 1284 KB Output is correct
6 Correct 651 ms 1404 KB Output is correct
7 Correct 1106 ms 1524 KB Output is correct
8 Correct 1515 ms 1524 KB Output is correct
9 Correct 1563 ms 1524 KB Output is correct
10 Correct 1534 ms 1652 KB Output is correct
11 Correct 1546 ms 1692 KB Output is correct
12 Correct 1479 ms 1736 KB Output is correct
13 Correct 1477 ms 1784 KB Output is correct
14 Correct 1545 ms 1828 KB Output is correct
15 Correct 1509 ms 1876 KB Output is correct
16 Correct 1449 ms 1896 KB Output is correct