| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 255977 |
2020-08-02T07:25:45 Z |
반딧불(#5032) |
Mixture (BOI20_mixture) |
C++17 |
|
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{
return Frac(a*r.a, b*r.b);
}
Frac operator/(const Frac &r)const{
return Frac(a*r.b, 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(y, x), b = Frac(z, x);
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(tmp == orig){
point++;
}
else{
if(segmentMap.find(tmp) == segmentMap.end()){
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);
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(segmentMap.find(tmp.rev()) != segmentMap.end()){
linear += segmentMap[tmp.rev()];
}
segmentMap[tmp]++;
}
}
else{
int d;
scanf("%d", &d);
use[d] = 0;
Frac tmp = (a[d] * den - pa * den) / (b[d] * den - pb * den);
if(tmp == orig){
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()){
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);
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 function 'void inputFrac(Frac&, Frac&)':
Mixture.cpp:77: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:86:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
Mixture.cpp:90:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf(" %c", &com);
~~~~~^~~~~~~~~~~~~
Mixture.cpp:122: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 |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
0 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 |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
0 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 |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
0 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 |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
0 ms |
384 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
