oj.uz

답안 #256006

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
256006 2020-08-02T07:55:12 Z 반딧불(#5032) Mixture (BOI20_mixture) C++17
0 / 100
 1 ms 384 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct Frac{
    ll a, b;
    Frac(){}
    Frac(ll _a, ll _b){
        if(_a || _b){
            ll g = abs(__gcd(abs(_a), abs(_b)));
            a = lldiv(_a, g).quot, b = lldiv(_b, g).quot;
        }
        else{
            a = _a, b = _b;
        }
    }

    ll ccw(const Frac &r)const{
        return a*r.b - b*r.a;
    }

    bool operator==(const Frac &r)const{
        return a == r.a && b == r.b;
    }
    bool operator<(const Frac &r)const{
		if((make_pair(a, b) > make_pair(0LL, 0LL)) ^ (make_pair(r.a, r.b) > make_pair(0LL, 0LL)))
            return make_pair(a, b) > make_pair(r.a, r.b);
		return ccw(r) > 0;
	}

    Frac operator-()const{
        return Frac(-a, b);
    }

    Frac operator+(const Frac &r)const{
        return Frac(a*r.b+b*r.a, b*r.b);
    }
    Frac operator-(const Frac &r)const{
        return Frac(a*r.b-b*r.a, b*r.b);
    }
    Frac operator*(const Frac &r)const{
        if(!!(a*r.a) || !!(b*r.b)) return Frac(a*r.a, b*r.b);
        return Frac(a == 0 ? r.a : a, b == 0 ? r.b : b);
    }
    Frac operator/(const Frac &r)const{
        return (*this) * Frac(r.b, r.a);
    }

    Frac operator*(const ll &r)const{
        return Frac(a*r, b);
    }
    Frac rev(){
        return Frac(-a, -b);
    }
};
const Frac orig (0, 0);

int n;
ll den;
ll rden;
Frac pa, pb;
Frac a[100002], b[100002];
bool use[100002];

map<Frac, ll> segmentMap;
ll point;
ll linear;
ll bigger;

ll ccw(Frac x, Frac y, Frac z){
    return Frac(y.a-x.a, y.b-x.b).ccw(Frac(z.a-x.a, z.b-x.b));
}

void inputFrac(Frac &a, Frac &b){
    ll x, y, z;
    scanf("%lld %lld %lld", &x, &y, &z);
    a = Frac(x, x+y+z), b = Frac(y, x+y+z);
    rden = x;
}

int main(){
    inputFrac(pa, pb);
    den = rden;

    scanf("%d", &n);
    int cnt = 0;
    while(n--){
        char com;
        scanf(" %c", &com);
        if(com == 'A'){
            cnt++;
            inputFrac(a[cnt], b[cnt]);
            use[cnt] = 1;

            Frac tmp = (a[cnt] * den - pa * den) / (b[cnt] * den - pb * den);
            if(a[cnt] == pa && b[cnt] == pb){
                point++;
            }
            else{
                if(segmentMap.find(tmp.rev()) != segmentMap.end()){
                    linear += segmentMap[tmp.rev()];
                }

                if(segmentMap.find(tmp) == segmentMap.end()){
                    if(segmentMap.size() == 1){
                        if(linear) bigger = 0;
                        else bigger = 1;
                    }
                    else if(segmentMap.size()){
                        auto it = segmentMap.lower_bound(tmp);
                        auto it2 = prev(segmentMap.end());
                        if(it == segmentMap.end()) it = segmentMap.begin();
                        if(it != segmentMap.begin()) it2 = prev(it);
                        swap(it, it2);

                        if(ccw(it->first, orig, it2->first) > 0) bigger--;
                        if(ccw(it->first, orig, tmp) > 0) bigger++;
                        if(ccw(tmp, orig, it2->first) > 0) bigger++;
                    }
                }
                segmentMap[tmp]++;
            }
        }
        else{
            int d;
            scanf("%d", &d);
            use[d] = 0;

            Frac tmp = (a[d] * den - pa * den) / (b[d] * den - pb * den);
            if(a[d] == pa && b[d] == pb){
                point--;
            }
            else{
                if(segmentMap.find(tmp.rev()) != segmentMap.end()){
                    linear -= segmentMap[tmp.rev()];
                }
                segmentMap[tmp]--;
                if(segmentMap[tmp] == 0) segmentMap.erase(segmentMap.find(tmp));

                if(segmentMap.find(tmp) == segmentMap.end()){
                    if(segmentMap.size() == 1){
                        bigger = 0;
                    }
                    else if(segmentMap.size()){
                        auto it = segmentMap.lower_bound(tmp);
                        auto it2 = prev(segmentMap.end());
                        if(it == segmentMap.end()) it = segmentMap.begin();
                        if(it != segmentMap.begin()) it2 = prev(it);
                        swap(it, it2);

                        if(ccw(it->first, orig, it2->first) > 0) bigger++;
                        if(ccw(it->first, orig, tmp) > 0) bigger--;
                        if(ccw(tmp, orig, it2->first) > 0) bigger--;
                    }
                }
            }
        }

        if(point){
            printf("1\n");
        }
        else if(linear){
            printf("2\n");
        }
        else if((int)segmentMap.size() > 2 && !bigger){
            printf("3\n");
        }
        else{
            printf("0\n");
        }
    }
}

Compilation message

Mixture.cpp: In member function 'Frac Frac::operator*(const Frac&) const':
Mixture.cpp:44:16: warning: '*' in boolean context, suggest '&&' instead [-Wint-in-bool-context]
         if(!!(a*r.a) || !!(b*r.b)) return Frac(a*r.a, b*r.b);
              ~~^~~~~
Mixture.cpp:44:29: warning: '*' in boolean context, suggest '&&' instead [-Wint-in-bool-context]
         if(!!(a*r.a) || !!(b*r.b)) return Frac(a*r.a, b*r.b);
                           ~~^~~~~
Mixture.cpp: In function 'void inputFrac(Frac&, Frac&)':
Mixture.cpp:78:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld %lld %lld", &x, &y, &z);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Mixture.cpp: In function 'int main()':
Mixture.cpp:87:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
Mixture.cpp:91:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %c", &com);
         ~~~~~^~~~~~~~~~~~~
Mixture.cpp:128:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &d);
             ~~~~~^~~~~~~~~~

Subtask #1
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 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 256 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 0 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Incorrect 1 ms 384 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 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 256 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 0 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Incorrect 1 ms 384 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 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 256 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 0 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Incorrect 1 ms 384 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 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 256 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 0 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Incorrect 1 ms 384 KB Output isn't correct
17 Halted 0 ms 0 KB -