oj.uz

Submission #259062

# Submission time Handle Problem Language Result Execution time Memory
259062 2020-08-07T06:19:58 Z 강태규(#5095) None (JOI12_constellation) C++17
0 / 100
 54 ms 5932 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];
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 {
        for (int i = 0; i < sz; ++i) {
            int l = i, r = i;
            while (!up[l].y) l = (l + sz - 1) % sz;
            while (!up[r].y) r = (r + 1) % sz;
            int v = (r - l + sz - 1) % sz;
            ans = (ans + v * (v + 1ll) / 2) % mod;
        }
    }
    if (!cnt[1]) ans = (ans + mod - 1) % mod;
    if (!cnt[2]) ans = (ans + mod - 1) % mod;
    for (int i = 0; i < cnt[0] - hcnt[0]; ++i) ans = (ans + ans) % mod;
    printf("%d\n", ans);
    return 0;
}

Compilation message

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

Subtask #1
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Incorrect 1 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Incorrect 1 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Incorrect 3 ms 640 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 47 ms 3704 KB Output is correct
3 Incorrect 1 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Incorrect 45 ms 3584 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #9
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 49 ms 3576 KB Output is correct
3 Correct 47 ms 5880 KB Output is correct
4 Incorrect 54 ms 5932 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #10
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -