oj.uz

답안 #259064

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
259064 2020-08-07T06:30:06 Z 강태규(#5095) 별자리 (JOI12_constellation) C++17
100 / 100
 49 ms 6024 KB 
#include <bits/stdc++.h>
#define x first
#define y second

using namespace std;
typedef long long llong;
typedef pair<int, int> pii;

void fail() {
    printf("0\n");
    exit(0);
}

const int mod = 1e9 + 7;
int n;
pair<pii, int> P[100001];

pii operator-(pii a, pii b) {
    return pii(a.x - b.x, a.y - b.y);
}

int ccw(pii a, pii b) {
    llong v = 1ll * a.x * b.y - 1ll * a.y * b.x;
    if (v < 0) return -1;
    if (v > 0) return 1;
    return 0;
}

int ccw(pii a, pii b, pii c) {
    return ccw(b - a, c - b);
}

int L[200001], R[200001];
bool used[200001];
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    int cnt[3] = {};
    for (int i = 1; i <= n; ++i) {
        cin >> P[i].x.x >> P[i].x.y >> P[i].y;
        ++cnt[P[i].y];
    }
    sort(P + 1, P + (n + 1));
    vector<pair<pii, int>> up, dn;
    for (int i = 1; i <= n; ++i) {
        pii p = P[i].x;
        int sz;
        while ((sz = up.size()) > 1 && ccw(up[sz - 2].x, up[sz - 1].x, p) > 0) up.pop_back();
        while ((sz = dn.size()) > 1 && ccw(dn[sz - 2].x, dn[sz - 1].x, p) < 0) dn.pop_back();
        up.push_back(P[i]);
        dn.push_back(P[i]);
    }
    dn.pop_back();
    while (int(dn.size()) > 1) up.push_back(dn.back()), dn.pop_back();
    int hcnt[3] = {};
    for (auto [_, c] : up) ++hcnt[c];
    int sz = up.size();
    int ans = 0;
    if (!hcnt[1] && !hcnt[2]) ans = (2 + sz * (sz - 1ll)) % mod;
    else if (hcnt[1] && hcnt[2]) {
        int ab = -1, ba = -1;
        for (int i = 0; i < sz; ++i) {
            if (!up[i].y) continue;
            int j;
            for (j = (i + 1) % sz; !up[j].y; j = (j + 1) % sz);
            if (up[i].y == up[j].y) continue;
            int v = (j - i + sz - 1) % sz;
            if (up[i].y == 1) {
                if (ab != -1) fail();
                ab = v;
            }
            else {
                if (ba != -1) fail();
                ba = v;
            }
        }
        ans = (ab + 1ll) * (ba + 1ll) % mod;
    }
    else {
        ans = 1;
        for (int i = 0; i < sz; ++i) {
            if (up[i].y || used[i]) continue;
            int l = i, r = i;
            while (!up[l].y) used[l] = 1, l = (l + sz - 1) % sz;
            while (!up[r].y) used[r] = 1, r = (r + 1) % sz;
            int v = (r - l + sz - 1) % sz;
            ans = (ans + v * (v + 1ll) / 2) % mod;
        }
    }
    for (int i = 0; i < cnt[0] - hcnt[0]; ++i) ans = (ans + ans) % mod;
    if (!cnt[1]) ans = (ans + mod - 1) % mod;
    if (!cnt[2]) ans = (ans + mod - 1) % mod;
    printf("%d\n", ans);
    return 0;
}

Compilation message

constellation.cpp: In function 'int main()':
constellation.cpp:56:20: warning: unused variable '_' [-Wunused-variable]
     for (auto [_, c] : up) ++hcnt[c];
                    ^

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 3 ms 640 KB Output is correct
4 Correct 3 ms 640 KB Output is correct
5 Correct 3 ms 512 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 3 ms 512 KB Output is correct
8 Correct 3 ms 512 KB Output is correct
9 Correct 3 ms 640 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 46 ms 1528 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 46 ms 3584 KB Output is correct
5 Correct 45 ms 6024 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 3 ms 644 KB Output is correct
8 Correct 3 ms 640 KB Output is correct
9 Correct 4 ms 640 KB Output is correct
10 Correct 46 ms 5752 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 44 ms 1528 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 46 ms 3576 KB Output is correct
5 Correct 47 ms 5960 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 3 ms 640 KB Output is correct
8 Correct 3 ms 640 KB Output is correct
9 Correct 3 ms 640 KB Output is correct
10 Correct 47 ms 5880 KB Output is correct

Subtask #9
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 44 ms 1528 KB Output is correct
3 Correct 46 ms 3704 KB Output is correct
4 Correct 44 ms 3884 KB Output is correct
5 Correct 47 ms 4396 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 2 ms 640 KB Output is correct
8 Correct 4 ms 512 KB Output is correct
9 Correct 3 ms 512 KB Output is correct
10 Correct 47 ms 3692 KB Output is correct
11 Correct 46 ms 3692 KB Output is correct

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 49 ms 1528 KB Output is correct
3 Correct 43 ms 1528 KB Output is correct
4 Correct 47 ms 3692 KB Output is correct
5 Correct 46 ms 3752 KB Output is correct
6 Correct 46 ms 4012 KB Output is correct
7 Correct 3 ms 512 KB Output is correct
8 Correct 3 ms 512 KB Output is correct
9 Correct 3 ms 512 KB Output is correct
10 Correct 20 ms 2552 KB Output is correct