oj.uz

Submission #259109

# Submission time Handle Problem Language Result Execution time Memory
259109 2020-08-07T08:17:14 Z 반딧불(#5071) None (JOI12_constellation) C++17
90 / 100
 76 ms 7152 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const ll MOD = 1000000007;

struct vector2{
    ll x, y, col;
    explicit vector2(double x_ = 0, double y_ = 0): x(x_), y(y_){}

    bool operator==(const vector2 &r)const{
        return x == r.x && y == r.y;
    }
    bool operator<(const vector2 &r)const{
        return x != r.x ? x < r.x : y < r.y;
    }
    bool operator>(const vector2 &r)const{
        return r < *this;
    }

    vector2 operator+(const vector2 &r)const{
        return vector2(x+r.x, y+r.y);
    }
    vector2 operator-(const vector2 &r)const{
        return vector2(x - r.x, y - r.y);
    }
    vector2 operator*(double r)const{
        return vector2(x*r, y*r);
    }

    double norm() const { return hypot(x, y); }

    ll dot(vector2 &r)const{
        return x*r.x + y*r.y;
    }
    ll cross(vector2 &r)const{
        return x*r.y - y*r.x;
    }
};

ll ccw(vector2 a, vector2 b){
    return a.cross(b);
}
ll ccw(vector2 a, vector2 b, vector2 c){
    return ccw(b-a, c-a);
}

int n;
vector2 arr[100002];
ll power2[100002] = {1};
vector<int> hull;
ll ans;
vector<int> col;
int c1, c2;
int fc1, fc2;

void convexHull(){
    sort(arr+1, arr+n+1);
    sort(arr+2, arr+n+1, [&](const vector2 &a, const vector2 &b){
		return ccw(a, arr[1], b) > 0;
	});
	hull.push_back(1);
	for(int i=2; i<=n; i++){
        while(hull.size() >= 2 && ccw(arr[hull[(int)hull.size()-2]], arr[hull[(int)hull.size()-1]], arr[i]) >= 0){
            hull.pop_back();
        }
        hull.push_back(i);
	}
}

int main(){
    scanf("%d", &n);
    for(int i=1; i<=n; i++){
        scanf("%lld %lld %lld", &arr[i].x, &arr[i].y, &arr[i].col);
        power2[i] = power2[i-1] * 2 % MOD;
        if(arr[i].col == 1) c1++;
        else if(arr[i].col == 2) c2++;
    }
    fc1 = c1, fc2 = c2;

    if(n==2){
        int ans[3][3] = {{2, 1, 0}, {1, 1, 0}, {0, 0, 0}};
        printf("%d\n", ans[c1][c2]);
        return 0;
    }

    convexHull();
    int k = (int)hull.size();

    int colExist = 0;
    for(auto &x: hull){
        vector2 tmp = arr[x];
        if(tmp.col == 1) c1--, colExist = 1;
        if(tmp.col == 2){
            c2--;
            if(!colExist) colExist = 2;
        }

        col.push_back(tmp.col);
    }

    if(!colExist) col[0] = 1;
    else if(colExist == 2){
        for(auto &x: col) if(x == 2) x = 1;
    }

    int pnt1 = 0;
    for(int i=0; i<k; i++){
        if(col[i] == 1){
            pnt1 = i;
            break;
        }
        if(i == k-1) return 1;
    }

    vector<int> tmpv (col.begin() + pnt1, col.end());
    tmpv.insert(tmpv.end(), col.begin(), col.begin()+pnt1);
    col = tmpv;

    ll flipCnt = 0;
    ll nowCol = 1;
    vector<ll> zeroCnt;
    vector<ll> realZeroCnt;
    ll zeroCount = 0;
    for(int i=0; i<=k; i++){
        if(i == k || col[i] == 1){
            if(zeroCount) zeroCnt.push_back(zeroCount+1);
            if(nowCol == 2){
                flipCnt++;
                realZeroCnt.push_back(zeroCount+1);
                nowCol = 1;
            }
            zeroCount = 0;
        }
        else if(col[i] == 2){
            if(zeroCount) zeroCnt.push_back(zeroCount+1);
            if(nowCol == 1){
                flipCnt++;
                realZeroCnt.push_back(zeroCount+1);
                nowCol = 2;
            }
            zeroCount = 0;
        }
        else{
            zeroCount++;
        }
    }

    if(flipCnt > 2){
        printf("0"); return 0;
    }

    if(flipCnt == 0){
        for(auto &x: zeroCnt){
            ans += (x-1) * x / 2;
            ans %= MOD;
        }
        ans++;
        ans %= MOD;
    }
    else{
        ans = 1;
        for(auto &x: realZeroCnt) ans *= x, ans %= MOD;
    }

    ans *= power2[n - k - c1 - c2];
    ans %= MOD;

    if(!fc1 || !fc2) ans--;
    if(ans < 0) ans += MOD;
    if(!colExist) ans *= 2, ans %= MOD;

    printf("%lld", ans);
}

Compilation message

constellation.cpp: In function 'int main()':
constellation.cpp:73:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
constellation.cpp:75:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld %lld %lld", &arr[i].x, &arr[i].y, &arr[i].col);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 1 ms 2688 KB Output is correct
3 Correct 2 ms 2688 KB Output is correct
4 Correct 1 ms 2688 KB Output is correct
5 Correct 2 ms 2688 KB Output is correct
6 Correct 1 ms 2688 KB Output is correct
7 Correct 2 ms 2688 KB Output is correct
8 Correct 1 ms 2688 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 2 ms 2816 KB Output is correct
4 Correct 2 ms 2688 KB Output is correct
5 Correct 2 ms 2688 KB Output is correct
6 Correct 2 ms 2688 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 3 ms 2688 KB Output is correct
3 Correct 2 ms 2688 KB Output is correct
4 Correct 2 ms 2688 KB Output is correct
5 Correct 2 ms 2688 KB Output is correct
6 Correct 3 ms 2688 KB Output is correct

Subtask #4
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 3 ms 2688 KB Output is correct
3 Correct 2 ms 2688 KB Output is correct
4 Correct 2 ms 2688 KB Output is correct
5 Correct 2 ms 2688 KB Output is correct
6 Incorrect 2 ms 2688 KB Output isn't correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 2 ms 2688 KB Output is correct
4 Correct 2 ms 2688 KB Output is correct
5 Correct 3 ms 2688 KB Output is correct
6 Correct 3 ms 2688 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2688 KB Output is correct
2 Correct 5 ms 2816 KB Output is correct
3 Correct 4 ms 2816 KB Output is correct
4 Correct 8 ms 2944 KB Output is correct
5 Correct 5 ms 2816 KB Output is correct
6 Correct 4 ms 2688 KB Output is correct
7 Correct 5 ms 2816 KB Output is correct
8 Correct 7 ms 2816 KB Output is correct
9 Correct 5 ms 2944 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 73 ms 3448 KB Output is correct
3 Correct 2 ms 2688 KB Output is correct
4 Correct 76 ms 3576 KB Output is correct
5 Correct 65 ms 7152 KB Output is correct
6 Correct 3 ms 2688 KB Output is correct
7 Correct 5 ms 2944 KB Output is correct
8 Correct 6 ms 2960 KB Output is correct
9 Correct 5 ms 2944 KB Output is correct
10 Correct 66 ms 6768 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 74 ms 3576 KB Output is correct
3 Correct 3 ms 2688 KB Output is correct
4 Correct 75 ms 5628 KB Output is correct
5 Correct 68 ms 7152 KB Output is correct
6 Correct 2 ms 2688 KB Output is correct
7 Correct 6 ms 2944 KB Output is correct
8 Correct 5 ms 2944 KB Output is correct
9 Correct 7 ms 2944 KB Output is correct
10 Correct 64 ms 7152 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 74 ms 3448 KB Output is correct
3 Correct 64 ms 4852 KB Output is correct
4 Correct 65 ms 4976 KB Output is correct
5 Correct 68 ms 5468 KB Output is correct
6 Correct 2 ms 2688 KB Output is correct
7 Correct 4 ms 2816 KB Output is correct
8 Correct 5 ms 2816 KB Output is correct
9 Correct 5 ms 2816 KB Output is correct
10 Correct 65 ms 4976 KB Output is correct
11 Correct 65 ms 4720 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 76 ms 3452 KB Output is correct
3 Correct 74 ms 3456 KB Output is correct
4 Correct 66 ms 4720 KB Output is correct
5 Correct 67 ms 4976 KB Output is correct
6 Correct 68 ms 5036 KB Output is correct
7 Correct 5 ms 2816 KB Output is correct
8 Correct 5 ms 2816 KB Output is correct
9 Correct 5 ms 2816 KB Output is correct
10 Correct 26 ms 3708 KB Output is correct