oj.uz

Submission #526706

# Submission time Handle Problem Language Result Execution time Memory
526706 2022-02-16T02:25:10 Z pokmui9909 별자리 2 (JOI14_constellation2) C++17
55 / 100
 9000 ms 368 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;

    X[j] = Y[i] = 1;
    ans += X[0] * X[1] * X[2] * Y[0] * Y[1] * Y[2];
}
  
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> V;
        for(int j = 1; j < N; j++){
            V.push_back(j);
        }
        sort(V.begin(), V.end(), [&](ll a, ll b) -> bool{
            return CCW(A[0], A[a], A[b]) > 0;
            // return CCW(A[0], A[a], A[b]) < CCW(A[0], A[b], A[a]);
        });
        // test_code
        for(auto j : V){
            vector<ll> X(3), Y(3);
            for(int k = 1; k < N; k++){
                if(k == j) continue;
                ll C = CCW(A[0], A[k], A[j]);
                if(C > 0){
                    X[T[k]]++;
                } else {
                    Y[T[k]]++;
                }
            }
            add(X, Y, T[0], T[j]);
        }
    }
    cout << ans / 4;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 280 KB Output is correct
6 Correct 0 ms 208 KB Output is correct
7 Correct 1 ms 208 KB Output is correct
8 Correct 1 ms 208 KB Output is correct
9 Correct 1 ms 328 KB Output is correct
10 Correct 1 ms 208 KB Output is correct
11 Correct 1 ms 208 KB Output is correct
12 Correct 1 ms 208 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 6 ms 208 KB Output is correct
4 Correct 16 ms 208 KB Output is correct
5 Correct 39 ms 336 KB Output is correct
6 Correct 108 ms 336 KB Output is correct
7 Correct 108 ms 336 KB Output is correct
8 Correct 116 ms 336 KB Output is correct
9 Correct 118 ms 336 KB Output is correct
10 Correct 64 ms 332 KB Output is correct
11 Correct 108 ms 336 KB Output is correct
12 Correct 110 ms 336 KB Output is correct

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1884 ms 348 KB Output is correct
2 Correct 2655 ms 352 KB Output is correct
3 Correct 3614 ms 368 KB Output is correct
4 Correct 3802 ms 364 KB Output is correct
5 Execution timed out 9068 ms 340 KB Time limit exceeded
6 Halted 0 ms 0 KB -