oj.uz

Submission #527699

# Submission time Handle Problem Language Result Execution time Memory
527699 2022-02-18T03:56:31 Z pokmui9909 별자리 2 (JOI14_constellation2) C++17
100 / 100
 1280 ms 1348 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using lf = long double;
 
#define x first
#define y second
using Point = pair<ll, ll>;
Point operator+ (Point p, Point q) {return Point(p.x + q.x, p.y + q.y);}
Point operator- (Point p, Point q) {return Point(p.x - q.x, p.y - q.y);}
ll    operator* (Point p, Point q) {return p.x * q.x + p.y * q.y;}
ll    operator/ (Point p, Point q) {return p.x * q.y - q.x * p.y;}
 
ll CCW(Point p, Point q, Point r) {return (q - p) / (r - q);}
 
ll N;
Point A[3005];
ll T[3005];
ll ans = 0;
 
void add(vector<ll> &X, vector<ll> &Y, ll i, ll j){
    ll pxi = X[i], pyj = Y[j];
    X[i] = Y[j] = 1;
    ans += X[0] * X[1] * X[2] * Y[0] * Y[1] * Y[2];
    X[i] = pxi, Y[j] = pyj;
}
ll sign(Point p){
    return Point(0, 0) < p;
}
  
int main(){
    cin.tie(0) -> sync_with_stdio(false);
    
    cin >> N;
    for(int i = 0; i < N; i++){
        cin >> A[i].x >> A[i].y;
        cin >> T[i];
    }
    for(int i = 0; i < N; i++){
        swap(A[0], A[i]);
        swap(T[0], T[i]);
        vector<ll> X(3), Y(3);
        vector<pair<Point, ll>> V;
        for(int j = 1; j < N; j++){
            V.push_back({A[j] - A[0], T[j]});
            X[T[j]]++;
        }
        sort(V.begin(), V.end(), [&](pair<Point, ll> a, pair<Point, ll> b) -> bool{
            if(sign(a.x) != sign(b.x)) return sign(a.x) > sign(b.x);
            else return CCW(Point(0, 0), a.x, b.x) >= 0;
        });
        for(int j = 0; j < N - 1; j++) V.push_back(V[j]);
        for(int j = 0, k = 0; j < N - 1; j++){
            while(k < j + N - 1 && CCW(Point(0, 0), V[j].x, V[k].x) >= 0){
                X[V[k].y]--, Y[V[k].y]++;
                k++;
            }
            add(X, Y, T[0], V[j].y);
            X[V[j].y]++, Y[V[j].y]--;
        }
    }
    cout << ans / 2;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 324 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 324 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 316 KB Output is correct

Subtask #2
40.0 / 40.0

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

Subtask #3
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 416 KB Output is correct
2 Correct 92 ms 428 KB Output is correct
3 Correct 108 ms 436 KB Output is correct
4 Correct 109 ms 460 KB Output is correct
5 Correct 316 ms 548 KB Output is correct
6 Correct 520 ms 1216 KB Output is correct
7 Correct 875 ms 796 KB Output is correct
8 Correct 1222 ms 1320 KB Output is correct
9 Correct 1262 ms 1336 KB Output is correct
10 Correct 1217 ms 1348 KB Output is correct
11 Correct 1254 ms 1076 KB Output is correct
12 Correct 1241 ms 1060 KB Output is correct
13 Correct 1280 ms 1068 KB Output is correct
14 Correct 1223 ms 1044 KB Output is correct
15 Correct 1193 ms 852 KB Output is correct
16 Correct 1239 ms 1240 KB Output is correct