| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 256031 |
2020-08-02T08:40:40 Z |
반딧불(#5032) |
Mixture (BOI20_mixture) |
C++17 |
|
1 ms |
384 KB |
#include <bits/stdc++.h>
#define sign(x) (x==ll(0)?0:x>ll(0)?1:-1)
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{
if(b==0) return sign(a) * sign(r.b);
if(r.b==0) return sign(r.a) * sign(b);
long double ld = a/b - r.a/r.b;
if(abs(ld) < 1e-15) return 0;
if(ld < 0) return -1;
return 1;
}
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:58:16: warning: '*' in boolean context, suggest '&&' instead [-Wint-in-bool-context]
if(!!(a*r.a) || !!(b*r.b))
~~^~~~~
Mixture.cpp:58: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:123:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
Mixture.cpp:127:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf(" %c", &com);
~~~~~^~~~~~~~~~~~~
Mixture.cpp:167:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &d);
~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
