oj.uz

Submission #526248

# Submission time Handle Problem Language Result Execution time Memory
526248 2022-02-14T04:10:42 Z pokmui9909 별자리 2 (JOI14_constellation2) C++17
55 / 100
 9000 ms 360 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];
  
int main(){
    cin.tie(0) -> sync_with_stdio(false);
    
    cin >> N;
    for(int i = 1; i <= N; i++){
        cin >> A[i].x >> A[i].y;
        cin >> T[i];
    }
    ll ans = 0;
    for(int i = 1; i <= N; i++){
        for(int j = i + 1; j <= N; j++){
            vector<ll> X(3), Y(3);
            for(int k = 1; k <= N; k++){
                if(k == i || k == j) continue;
                ll C = CCW(A[i], A[k], A[j]);
                if(C > 0){
                    X[T[k]]++;
                } else {
                    Y[T[k]]++;
                }
            }
            ll pxti = X[T[i]], pytj = Y[T[j]];
            X[T[i]] = Y[T[j]] = 1;

            ans += X[0] * X[1] * X[2] * Y[0] * Y[1] * Y[2];
            X[T[i]] = pxti, Y[T[j]] = pytj;

            X[T[j]] = Y[T[i]] = 1;
            ans += X[0] * X[1] * X[2] * Y[0] * Y[1] * Y[2];
        }
    }
    cout << ans / 2;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 316 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 320 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 204 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 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 3 ms 204 KB Output is correct
4 Correct 8 ms 316 KB Output is correct
5 Correct 20 ms 204 KB Output is correct
6 Correct 60 ms 204 KB Output is correct
7 Correct 67 ms 332 KB Output is correct
8 Correct 60 ms 308 KB Output is correct
9 Correct 60 ms 204 KB Output is correct
10 Correct 35 ms 204 KB Output is correct
11 Correct 57 ms 324 KB Output is correct
12 Correct 61 ms 312 KB Output is correct

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1180 ms 332 KB Output is correct
2 Correct 1669 ms 336 KB Output is correct
3 Correct 2321 ms 332 KB Output is correct
4 Correct 2298 ms 344 KB Output is correct
5 Correct 7792 ms 360 KB Output is correct
6 Execution timed out 9030 ms 332 KB Time limit exceeded
7 Halted 0 ms 0 KB -