| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 256026 |
2020-08-02T08:35:54 Z |
반딧불(#5032) |
Mixture (BOI20_mixture) |
C++17 |
|
0 ms |
0 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 /= 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 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 member function 'void Frac::change()':
Mixture.cpp:68: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:69: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: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);
~~~~~^~~~~~~~~~
