oj.uz

Submission #256028

# Submission time Handle Problem Language Result Execution time Memory
256028 2020-08-02T08:37:08 Z 반딧불(#5032) Mixture (BOI20_mixture) C++17
60 / 100
 19 ms 896 KB 
#include <bits/stdc++.h>

using namespace std;

typedef __int128 ll;

inline ll abbs(ll x){
    if(x < ll(0)) return -x;
    return x;
}

struct Frac{
    ll a, b;
    Frac(){}
    Frac(ll _a, ll _b){
        if(_a || _b){
            ll g = abbs(__gcd(abbs(_a), abbs(_b)));
            a = lldiv(_a, g).quot, b = lldiv(_b, g).quot;
//            printf("%lld %lld -> %lld %lld\n", _a, _b, a, b);
        }
        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(ll(0), ll(0))) ^ (make_pair(r.a, r.b) > make_pair(ll(0), ll(0))))
            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 == 0 && b == 0) return r;
        if(r.a == 0 && r.b == 0) return *this;
        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);
    }

    void change(){
        if(!a && b) b /= abbs(b);
        if(!b && a) a /= abbs(a);
    }
};
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));
}

__int128 read() {
    __int128 x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

void inputFrac(Frac &a, Frac &b){
    ll x, y, z;
    x = read();
    y = read();
    z = read();
    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 tmp1 = (a[cnt] - pa);
            Frac tmp2 = (b[cnt] - pb);
            Frac tmp = tmp1 / tmp2;
            tmp.change();
            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] - pa) / (b[d] - pb);
            tmp.change();
            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:52:16: warning: '*' in boolean context, suggest '&&' instead [-Wint-in-bool-context]
         if(!!(a*r.a) || !!(b*r.b))
              ~~^~~~~
Mixture.cpp:52:29: warning: '*' in boolean context, suggest '&&' instead [-Wint-in-bool-context]
         if(!!(a*r.a) || !!(b*r.b))
                           ~~^~~~~
Mixture.cpp: In function 'int main()':
Mixture.cpp:117:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
Mixture.cpp:121:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %c", &com);
         ~~~~~^~~~~~~~~~~~~
Mixture.cpp:161:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &d);
             ~~~~~^~~~~~~~~~

Subtask #1
13.0 / 13.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 Correct 1 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 0 ms 384 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 0 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 0 ms 384 KB Output is correct
14 Correct 0 ms 384 KB Output is correct
15 Correct 0 ms 384 KB Output is correct
16 Correct 0 ms 384 KB Output is correct
17 Correct 0 ms 384 KB Output is correct
18 Correct 0 ms 384 KB Output is correct
19 Correct 0 ms 384 KB Output is correct

Subtask #2
17.0 / 17.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 Correct 1 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 0 ms 384 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 0 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 0 ms 384 KB Output is correct
14 Correct 0 ms 384 KB Output is correct
15 Correct 0 ms 384 KB Output is correct
16 Correct 0 ms 384 KB Output is correct
17 Correct 0 ms 384 KB Output is correct
18 Correct 0 ms 384 KB Output is correct
19 Correct 0 ms 384 KB Output is correct
20 Correct 1 ms 384 KB Output is correct
21 Correct 1 ms 384 KB Output is correct
22 Correct 1 ms 384 KB Output is correct
23 Correct 2 ms 384 KB Output is correct
24 Correct 1 ms 384 KB Output is correct
25 Correct 1 ms 384 KB Output is correct
26 Correct 1 ms 384 KB Output is correct
27 Correct 1 ms 384 KB Output is correct
28 Correct 1 ms 384 KB Output is correct
29 Correct 1 ms 384 KB Output is correct
30 Correct 1 ms 384 KB Output is correct
31 Correct 1 ms 384 KB Output is correct
32 Correct 1 ms 384 KB Output is correct
33 Correct 1 ms 384 KB Output is correct
34 Correct 1 ms 384 KB Output is correct
35 Correct 1 ms 384 KB Output is correct
36 Correct 1 ms 384 KB Output is correct

Subtask #3
30.0 / 30.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 Correct 1 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 0 ms 384 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 0 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 0 ms 384 KB Output is correct
14 Correct 0 ms 384 KB Output is correct
15 Correct 0 ms 384 KB Output is correct
16 Correct 0 ms 384 KB Output is correct
17 Correct 0 ms 384 KB Output is correct
18 Correct 0 ms 384 KB Output is correct
19 Correct 0 ms 384 KB Output is correct
20 Correct 1 ms 384 KB Output is correct
21 Correct 1 ms 384 KB Output is correct
22 Correct 1 ms 384 KB Output is correct
23 Correct 2 ms 384 KB Output is correct
24 Correct 1 ms 384 KB Output is correct
25 Correct 1 ms 384 KB Output is correct
26 Correct 1 ms 384 KB Output is correct
27 Correct 1 ms 384 KB Output is correct
28 Correct 1 ms 384 KB Output is correct
29 Correct 1 ms 384 KB Output is correct
30 Correct 1 ms 384 KB Output is correct
31 Correct 1 ms 384 KB Output is correct
32 Correct 1 ms 384 KB Output is correct
33 Correct 1 ms 384 KB Output is correct
34 Correct 1 ms 384 KB Output is correct
35 Correct 1 ms 384 KB Output is correct
36 Correct 1 ms 384 KB Output is correct
37 Correct 2 ms 384 KB Output is correct
38 Correct 2 ms 384 KB Output is correct
39 Correct 2 ms 384 KB Output is correct
40 Correct 2 ms 384 KB Output is correct
41 Correct 3 ms 384 KB Output is correct
42 Correct 2 ms 384 KB Output is correct
43 Correct 2 ms 512 KB Output is correct
44 Correct 2 ms 512 KB Output is correct
45 Correct 3 ms 512 KB Output is correct
46 Correct 7 ms 640 KB Output is correct
47 Correct 8 ms 640 KB Output is correct
48 Correct 4 ms 512 KB Output is correct
49 Correct 4 ms 512 KB Output is correct
50 Correct 5 ms 512 KB Output is correct
51 Correct 12 ms 768 KB Output is correct
52 Correct 6 ms 640 KB Output is correct
53 Correct 9 ms 896 KB Output is correct
54 Correct 10 ms 896 KB Output is correct
55 Correct 4 ms 640 KB Output is correct
56 Correct 3 ms 640 KB Output is correct

Subtask #4
0 / 40.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 Correct 1 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 0 ms 384 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 0 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 0 ms 384 KB Output is correct
14 Correct 0 ms 384 KB Output is correct
15 Correct 0 ms 384 KB Output is correct
16 Correct 0 ms 384 KB Output is correct
17 Correct 0 ms 384 KB Output is correct
18 Correct 0 ms 384 KB Output is correct
19 Correct 0 ms 384 KB Output is correct
20 Correct 1 ms 384 KB Output is correct
21 Correct 1 ms 384 KB Output is correct
22 Correct 1 ms 384 KB Output is correct
23 Correct 2 ms 384 KB Output is correct
24 Correct 1 ms 384 KB Output is correct
25 Correct 1 ms 384 KB Output is correct
26 Correct 1 ms 384 KB Output is correct
27 Correct 1 ms 384 KB Output is correct
28 Correct 1 ms 384 KB Output is correct
29 Correct 1 ms 384 KB Output is correct
30 Correct 1 ms 384 KB Output is correct
31 Correct 1 ms 384 KB Output is correct
32 Correct 1 ms 384 KB Output is correct
33 Correct 1 ms 384 KB Output is correct
34 Correct 1 ms 384 KB Output is correct
35 Correct 1 ms 384 KB Output is correct
36 Correct 1 ms 384 KB Output is correct
37 Correct 2 ms 384 KB Output is correct
38 Correct 2 ms 384 KB Output is correct
39 Correct 2 ms 384 KB Output is correct
40 Correct 2 ms 384 KB Output is correct
41 Correct 3 ms 384 KB Output is correct
42 Correct 2 ms 384 KB Output is correct
43 Correct 2 ms 512 KB Output is correct
44 Correct 2 ms 512 KB Output is correct
45 Correct 3 ms 512 KB Output is correct
46 Correct 7 ms 640 KB Output is correct
47 Correct 8 ms 640 KB Output is correct
48 Correct 4 ms 512 KB Output is correct
49 Correct 4 ms 512 KB Output is correct
50 Correct 5 ms 512 KB Output is correct
51 Correct 12 ms 768 KB Output is correct
52 Correct 6 ms 640 KB Output is correct
53 Correct 9 ms 896 KB Output is correct
54 Correct 10 ms 896 KB Output is correct
55 Correct 4 ms 640 KB Output is correct
56 Correct 3 ms 640 KB Output is correct
57 Correct 8 ms 768 KB Output is correct
58 Correct 19 ms 896 KB Output is correct
59 Incorrect 19 ms 896 KB Output isn't correct
60 Halted 0 ms 0 KB -