oj.uz

Submission #157203

# Submission time Handle Problem Language Result Execution time Memory
157203 2019-10-10T04:18:46 Z atoiz 별자리 2 (JOI14_constellation2) C++14
100 / 100
 1338 ms 640 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cassert>
#include <numeric>
#include <tuple>
#include <bitset>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <set>
#include <queue>
#include <ios>
#include <iomanip>
#include <random>
#include <chrono>

using namespace std;
using ll = long long;

#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define FORA(i, a) for (auto &i : a)
#define FORB(i, a, b) for (int i = a; i >= b; --i)
#define SZ(a) ((int) a.size());
#define ALL(a) begin(a), end(a)

const int MAXN = 3007;

struct Point
{
    int x, y, c;
    Point(int _x = 0, int _y = 0, int _c = 0): x(_x), y(_y), c(_c) {};
    friend Point operator-(Point p1, Point p2) { return Point(p1.x - p2.x, p1.y - p2.y); }
    friend ll operator^(Point p1, Point p2) { return 1ll * p1.x * p2.y - 1ll * p2.x * p1.y; }
    int ccw(Point p1, Point p2)
    {
        ll x = (p1 - (*this)) ^ (p2 - (*this));
        if (x < 0) return -1;
        if (x > 0) return 1;
        return 0;
    }

} pnts[MAXN], pnts2[MAXN * 2];
int cnt[3], cnt1[3], total[3], N;

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> N;
    FOR(i, 0, N - 1) {
        cin >> pnts[i].x >> pnts[i].y >> pnts[i].c;
        ++total[pnts[i].c];
    }
    ll ans = 0;
    FOR(i, 0, N - 1) {
        Point P = pnts[i];
        FOR(j, 0, i - 1) pnts2[j] = pnts[j];
        FOR(j, i + 1, N - 1) pnts2[j - 1] = pnts[j];
        sort(pnts2, pnts2 + N - 1, [&](Point p1, Point p2) {
            p1 = p1 - P, p2 = p2 - P;
            bool b1 = (p1.y < 0 || p1.y == 0 && p1.x < 0);
            bool b2 = (p2.y < 0 || p2.y == 0 && p2.x < 0);
            if (b1 != b2) return b1 < b2;
            return (p1 ^ p2) > 0;
        });
        copy(pnts2, pnts2 + N - 1, pnts2 + N - 1);

        memset(cnt, 0, sizeof cnt);
        for (int j = 0, k = 0; j < N - 1; ++j) {
            for (; k < j + N - 1 && P.ccw(pnts2[j], pnts2[k]) >= 0; ++k) ++cnt[pnts2[k].c];
            --cnt[pnts2[j].c];

            FOR(k, 0, 2) cnt1[k] = total[k] - cnt[k];
            int c1 = P.c, c2 = pnts2[j].c;
            --cnt1[c1], --cnt1[c2];

            // cerr << i << ": " << j << ' ' << k << endl;
            // FOR(k, 0, 2) cerr << cnt[k] << ' ';
            // FOR(k, 0, 2) cerr << cnt1[k] << ' ';
            // cerr << endl;

            ans += 1ll * cnt[(c1 + 1) % 3] * cnt[(c1 + 2) % 3] * cnt1[(c2 + 1) % 3] * cnt1[(c2 + 2) % 3];
            ans += 1ll * cnt1[(c1 + 1) % 3] * cnt1[(c1 + 2) % 3] * cnt[(c2 + 1) % 3] * cnt[(c2 + 2) % 3];
        }
    }
    cout << ans / 4 << endl;
}

Compilation message

constellation2.cpp: In lambda function:
constellation2.cpp:68:46: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
             bool b1 = (p1.y < 0 || p1.y == 0 && p1.x < 0);
                                    ~~~~~~~~~~^~~~~~~~~~~
constellation2.cpp:69:46: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
             bool b2 = (p2.y < 0 || p2.y == 0 && p2.x < 0);
                                    ~~~~~~~~~~^~~~~~~~~~~

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 376 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 2 ms 508 KB Output is correct
7 Correct 2 ms 480 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 380 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 504 KB Output is correct
12 Correct 2 ms 504 KB Output is correct

Subtask #2
40.0 / 40.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 3 ms 504 KB Output is correct
4 Correct 4 ms 376 KB Output is correct
5 Correct 7 ms 504 KB Output is correct
6 Correct 12 ms 376 KB Output is correct
7 Correct 12 ms 376 KB Output is correct
8 Correct 12 ms 504 KB Output is correct
9 Correct 13 ms 504 KB Output is correct
10 Correct 6 ms 376 KB Output is correct
11 Correct 13 ms 504 KB Output is correct
12 Correct 13 ms 504 KB Output is correct

Subtask #3
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 640 KB Output is correct
2 Correct 104 ms 504 KB Output is correct
3 Correct 130 ms 504 KB Output is correct
4 Correct 131 ms 504 KB Output is correct
5 Correct 304 ms 536 KB Output is correct
6 Correct 554 ms 632 KB Output is correct
7 Correct 908 ms 524 KB Output is correct
8 Correct 1287 ms 540 KB Output is correct
9 Correct 1284 ms 632 KB Output is correct
10 Correct 1254 ms 632 KB Output is correct
11 Correct 1310 ms 632 KB Output is correct
12 Correct 1255 ms 632 KB Output is correct
13 Correct 1313 ms 540 KB Output is correct
14 Correct 1338 ms 528 KB Output is correct
15 Correct 1278 ms 528 KB Output is correct
16 Correct 1307 ms 524 KB Output is correct