Submission #256025

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
256025	2020-08-02T08:34:41 Z	반딧불(#5032)	Mixture (BOI20_mixture)	C++17	Compilation error	0 ms	0 KB

Mixture

#include <bits/stdc++.h>

using namespace std;

typedef __int128 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;
//            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 /= abs(b);
        if(!b && a) a /= abs(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 constructor 'Frac::Frac(ll, ll)':
Mixture.cpp:12:36: error: call of overloaded 'abs(ll&)' is ambiguous
             ll g = abs(__gcd(abs(_a), abs(_b)));
                                    ^
In file included from /usr/include/c++/7/bits/std_abs.h:38:0,
                 from /usr/include/c++/7/cmath:47,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:41,
                 from Mixture.cpp:1:
/usr/include/stdlib.h:774:12: note: candidate: int abs(int)
 extern int abs (int __x) __THROW __attribute__ ((__const__)) __wur;
            ^~~
In file included from /usr/include/c++/7/cmath:47:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:41,
                 from Mixture.cpp:1:
/usr/include/c++/7/bits/std_abs.h:56:3: note: candidate: long int std::abs(long int)
   abs(long __i) { return __builtin_labs(__i); }
   ^~~
/usr/include/c++/7/bits/std_abs.h:61:3: note: candidate: long long int std::abs(long long int)
   abs(long long __x) { return __builtin_llabs (__x); }
   ^~~
/usr/include/c++/7/bits/std_abs.h:70:3: note: candidate: constexpr double std::abs(double)
   abs(double __x)
   ^~~
/usr/include/c++/7/bits/std_abs.h:74:3: note: candidate: constexpr float std::abs(float)
   abs(float __x)
   ^~~
/usr/include/c++/7/bits/std_abs.h:78:3: note: candidate: constexpr long double std::abs(long double)
   abs(long double __x)
   ^~~
Mixture.cpp:12:45: error: call of overloaded 'abs(ll&)' is ambiguous
             ll g = abs(__gcd(abs(_a), abs(_b)));
                                             ^
In file included from /usr/include/c++/7/bits/std_abs.h:38:0,
                 from /usr/include/c++/7/cmath:47,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:41,
                 from Mixture.cpp:1:
/usr/include/stdlib.h:774:12: note: candidate: int abs(int)
 extern int abs (int __x) __THROW __attribute__ ((__const__)) __wur;
            ^~~
In file included from /usr/include/c++/7/cmath:47:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:41,
                 from Mixture.cpp:1:
/usr/include/c++/7/bits/std_abs.h:56:3: note: candidate: long int std::abs(long int)
   abs(long __i) { return __builtin_labs(__i); }
   ^~~
/usr/include/c++/7/bits/std_abs.h:61:3: note: candidate: long long int std::abs(long long int)
   abs(long long __x) { return __builtin_llabs (__x); }
   ^~~
/usr/include/c++/7/bits/std_abs.h:70:3: note: candidate: constexpr double std::abs(double)
   abs(double __x)
   ^~~
/usr/include/c++/7/bits/std_abs.h:74:3: note: candidate: constexpr float std::abs(float)
   abs(float __x)
   ^~~
/usr/include/c++/7/bits/std_abs.h:78:3: note: candidate: constexpr long double std::abs(long double)
   abs(long double __x)
   ^~~
Mixture.cpp: In member function 'Frac Frac::operator*(const Frac&) const':
Mixture.cpp:47:16: warning: '*' in boolean context, suggest '&&' instead [-Wint-in-bool-context]
         if(!!(a*r.a) || !!(b*r.b))
              ~~^~~~~
Mixture.cpp:47:29: warning: '*' in boolean context, suggest '&&' instead [-Wint-in-bool-context]
         if(!!(a*r.a) || !!(b*r.b))
                           ~~^~~~~
Mixture.cpp: In member function 'void Frac::change()':
Mixture.cpp:63:31: error: call of overloaded 'abs(ll&)' is ambiguous
         if(!a && b) b /= abs(b);
                               ^
In file included from /usr/include/c++/7/bits/std_abs.h:38:0,
                 from /usr/include/c++/7/cmath:47,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:41,
                 from Mixture.cpp:1:
/usr/include/stdlib.h:774:12: note: candidate: int abs(int)
 extern int abs (int __x) __THROW __attribute__ ((__const__)) __wur;
            ^~~
In file included from /usr/include/c++/7/cmath:47:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:41,
                 from Mixture.cpp:1:
/usr/include/c++/7/bits/std_abs.h:56:3: note: candidate: long int std::abs(long int)
   abs(long __i) { return __builtin_labs(__i); }
   ^~~
/usr/include/c++/7/bits/std_abs.h:61:3: note: candidate: long long int std::abs(long long int)
   abs(long long __x) { return __builtin_llabs (__x); }
   ^~~
/usr/include/c++/7/bits/std_abs.h:70:3: note: candidate: constexpr double std::abs(double)
   abs(double __x)
   ^~~
/usr/include/c++/7/bits/std_abs.h:74:3: note: candidate: constexpr float std::abs(float)
   abs(float __x)
   ^~~
/usr/include/c++/7/bits/std_abs.h:78:3: note: candidate: constexpr long double std::abs(long double)
   abs(long double __x)
   ^~~
Mixture.cpp:64:31: error: call of overloaded 'abs(ll&)' is ambiguous
         if(!b && a) a /= abs(a);
                               ^
In file included from /usr/include/c++/7/bits/std_abs.h:38:0,
                 from /usr/include/c++/7/cmath:47,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:41,
                 from Mixture.cpp:1:
/usr/include/stdlib.h:774:12: note: candidate: int abs(int)
 extern int abs (int __x) __THROW __attribute__ ((__const__)) __wur;
            ^~~
In file included from /usr/include/c++/7/cmath:47:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:41,
                 from Mixture.cpp:1:
/usr/include/c++/7/bits/std_abs.h:56:3: note: candidate: long int std::abs(long int)
   abs(long __i) { return __builtin_labs(__i); }
   ^~~
/usr/include/c++/7/bits/std_abs.h:61:3: note: candidate: long long int std::abs(long long int)
   abs(long long __x) { return __builtin_llabs (__x); }
   ^~~
/usr/include/c++/7/bits/std_abs.h:70:3: note: candidate: constexpr double std::abs(double)
   abs(double __x)
   ^~~
/usr/include/c++/7/bits/std_abs.h:74:3: note: candidate: constexpr float std::abs(float)
   abs(float __x)
   ^~~
/usr/include/c++/7/bits/std_abs.h:78:3: note: candidate: constexpr long double std::abs(long double)
   abs(long double __x)
   ^~~
Mixture.cpp: In function 'int main()':
Mixture.cpp:112:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
Mixture.cpp:116:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %c", &com);
         ~~~~~^~~~~~~~~~~~~
Mixture.cpp:156:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &d);
             ~~~~~^~~~~~~~~~