oj.uz

Submission #157213

# Submission time Handle Problem Language Result Execution time Memory
157213 2019-10-10T06:36:23 Z Flying_dragon_02 별자리 2 (JOI14_constellation2) C++14
100 / 100
 1986 ms 504 KB 
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define pb push_back
#define mp make_pair

typedef pair<int, int> ii;
typedef pair<ii, int> iii;

const int N = 3005;

int n;

long long sum;

iii x[N];

vector<iii> vec;

int ccw(iii a, iii b, iii p) {
    long long sum = (1ll * b.fi.fi - 1ll * a.fi.fi) * (1ll * b.fi.se - 1ll * p.fi.se) - (1ll * b.fi.se - 1ll * a.fi.se) * (1ll * b.fi.fi - 1ll * p.fi.fi);
    if(sum < 0) // ben trai
        return -1;
    else if(sum == 0) // thang long
        return 0;
    else // ben phai
        return 1;
}

bool compare(iii x) {
    if(x.fi.se > 0)
        return 1;
    else if(x.fi.se == 0 && x.fi.fi > 0)
        return 1;
    return 0;
}

iii lmao;

bool cmp(iii a, iii b) {
    if(compare(a) != compare(b)) return compare(a) > compare(b);
    return ccw(lmao, a, b) > 0;
}

long long used[5], total[5];

long long calc(int x, int y) {
    long long val1, val2;
    total[y]--;
    total[x]--;
    if(x == 0)
        val1 = used[1] * used[2];
    if(x == 1)
        val1 = used[0] * used[2];
    if(x == 2)
        val1 = used[0] * used[1];
    if(y == 0)
        val2 = (total[1] - used[1]) * (total[2] - used[2]);
    if(y == 1)
        val2 = (total[0] - used[0]) * (total[2] - used[2]);
    if(y == 2)
        val2 = (total[0] - used[0]) * (total[1] - used[1]);
    total[y]++;
    total[x]++;
    //cout << val1 * val2 << "\n";
    return val1 * val2;
}

void process(int id) {
    vec.clear();
    memset(used, 0, sizeof(used));
    for(int i = 1; i <= n; i++) {
        if(i != id)
            vec.pb({{x[i].fi.fi - x[id].fi.fi, x[i].fi.se - x[id].fi.se}, x[i].se});
    }
    sort(vec.begin(), vec.end(), cmp);
    /*if(id == 3) {
        for(int i = 0; i < vec.size(); i++)
            cout << vec[i].fi.fi << " " << vec[i].fi.se << " " << vec[i].se << "\n";
    }*/
    int pter1 = 0, m = vec.size();
    //exit(0);
    //cout << 0 << " " << pter1 << " " << used[0] << " " << used[1] << " " << used[2] << "\n";
    for(int i = 0; i < vec.size(); i++) {
        --used[vec[i].se];
        if(i == pter1) {used[vec[pter1].se]++; pter1 = (pter1 + 1) % m;}
        while(ccw(lmao, vec[i], vec[pter1]) > 0) {
            //cout << "wtf\n";
            used[vec[pter1].se]++;
            pter1 = (pter1 + 1) % m;
        }
        //if(ccw(lmao, vec[i], vec[i - 1]) < 0)
            //used[vec[i - 1].se]--;
        //cout << i << " " << pter1 << " " << used[0] << " " << used[1] << " " << used[2] << " " << vec[i - 1].se << "\n";
        sum += calc(x[id].se, vec[i].se);
    }
    //cout << sum << "\n";
    //exit(0);
}

int main() {
    cin.tie(0), ios::sync_with_stdio(0);
    //freopen("test.inp", "r", stdin);
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> x[i].fi.fi >> x[i].fi.se >> x[i].se;
        total[x[i].se]++;
    }
    for(int i = 1; i <= n; i++)
        process(i);
    cout << sum / 2;
}
/*7
0 0 0
2 0 1
1 2 2
-2 1 0
-2 -3 0
0 -2 1
2 -2 2*/

Compilation message

constellation2.cpp: In function 'void process(int)':
constellation2.cpp:87:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < vec.size(); i++) {
                    ~~^~~~~~~~~~~~
constellation2.cpp: In function 'long long int calc(int, int)':
constellation2.cpp:69:19: warning: 'val2' may be used uninitialized in this function [-Wmaybe-uninitialized]
     return val1 * val2;
                   ^~~~
constellation2.cpp:69:19: warning: 'val1' may be used uninitialized in this function [-Wmaybe-uninitialized]

Subtask #1
15.0 / 15.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 4 ms 376 KB Output is correct
4 Correct 6 ms 504 KB Output is correct
5 Correct 9 ms 376 KB Output is correct
6 Correct 18 ms 376 KB Output is correct
7 Correct 18 ms 376 KB Output is correct
8 Correct 18 ms 376 KB Output is correct
9 Correct 18 ms 376 KB Output is correct
10 Correct 13 ms 380 KB Output is correct
11 Correct 18 ms 376 KB Output is correct
12 Correct 18 ms 376 KB Output is correct

Subtask #3
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 416 KB Output is correct
2 Correct 161 ms 416 KB Output is correct
3 Correct 204 ms 420 KB Output is correct
4 Correct 202 ms 504 KB Output is correct
5 Correct 461 ms 380 KB Output is correct
6 Correct 840 ms 456 KB Output is correct
7 Correct 1324 ms 496 KB Output is correct
8 Correct 1907 ms 504 KB Output is correct
9 Correct 1950 ms 504 KB Output is correct
10 Correct 1983 ms 496 KB Output is correct
11 Correct 1974 ms 500 KB Output is correct
12 Correct 1986 ms 504 KB Output is correct
13 Correct 1910 ms 500 KB Output is correct
14 Correct 1956 ms 500 KB Output is correct
15 Correct 1985 ms 504 KB Output is correct
16 Correct 1928 ms 500 KB Output is correct