| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 587032 |
2022-07-01T08:32:22 Z |
반딧불(#8396) |
Mixture (BOI20_mixture) |
C++17 |
|
1 ms |
468 KB |
#include <bits/stdc++.h>
using namespace std;
#ifdef TEST
typedef long long ll;
#else
typedef __int128 ll;
#endif
struct vector2{
ll x, y;
vector2(){}
vector2(ll x, ll y): x(x), y(y){}
vector2 operator-()const{
return vector2(-x, -y);
}
vector2 operator-(const vector2 &r)const{
return vector2(x-r.x, y-r.y);
}
ll cross(vector2 r)const{
return x*r.y - y*r.x;
}
bool operator<(const vector2 &r)const{
if((make_pair(y, x) > make_pair(ll(0), ll(0))) ^ (make_pair(r.y, r.x) > make_pair(ll(0), ll(0)))){
return make_pair(y, x) > make_pair(ll(0), ll(0));
}
return (vector2(0, 0) - *this).cross(r - *this) < 0;
}
bool operator==(const vector2 &r)const{
return x==r.x && y==r.y;
}
};
ll ccw(vector2 a, vector2 b){
return a.cross(b);
}
ll ccw(vector2 a, vector2 b, vector2 c){
return (b-a).cross(c-a);
}
ll mabs(ll x){
return x>=0?x:-x;
}
vector2 calc(ll A, ll B, ll C, ll x, ll y, ll z){
C += A+B, z += x+y;
A*=z, B*=z, x*=C, y*=C;
x-=A, y-=B;
ll g = mabs(__gcd(x, y));
if(g) x/=g, y/=g;
return vector2(x, y);
}
long long A, B, C;
int n;
vector2 arr[100002];
int arrCnt;
/// ans=1 ���
int oneCnt;
/// ans=2 ���
map<vector2, ll> twoMp;
ll twoCnt;
/// ans=3 ���
map<vector2, int> threeMp;
int threeCnt; /// 180�� �ʰ��� ������ ����
bool large(vector2 a, vector2 b){
return ccw(a, vector2(0, 0), b) > 0;
}
bool calc3(){
vector2 prv;
if(threeMp.size() <= 2) return false;
for(auto it = threeMp.begin(); it != threeMp.end(); ++it){
if(it == threeMp.begin()){
prv = it->first;
continue;
}
if(large(prv, it->first)) return false;
prv = it->first;
}
if(large(prv, threeMp.begin()->first)) return false;
return true;
}
void addPoint(){
long long x, y, z;
scanf("%lld %lld %lld", &x, &y, &z);
int i = ++arrCnt;
arr[i] = calc(A, B, C, x, y, z);
/// ans=1 update
if(arr[i] == vector2(0, 0)){
oneCnt++;
return;
}
/// ans=2 update
twoMp[arr[i]]++;
twoCnt += twoMp[-arr[i]];
/// ans=3 update
if(threeMp.empty()){
threeMp[arr[i]]++;
threeCnt = 0;
return;
}
if(threeMp.find(arr[i]) != threeMp.end()){
threeMp[arr[i]]++;
return;
}
/// ū ������ ����
auto it = threeMp.lower_bound(arr[i]);
if(it == threeMp.begin() || it == threeMp.end()) threeCnt -= large(threeMp.rbegin()->first, threeMp.begin()->first);
else threeCnt -= large(prev(it)->first, it->first);
assert(threeCnt==0 || threeCnt==1);
threeMp[arr[i]]++;
// for(auto p: threeMp) printf("(%lld, %lld) ", p.first.x, p.first.y);
// puts("");
it = threeMp.lower_bound(arr[i]);
assert(it != threeMp.end());
if(it == prev(threeMp.end())) threeCnt += large(it->first, threeMp.begin()->first);
else threeCnt += large(it->first, next(it)->first);
if(it == threeMp.begin()) threeCnt += large(threeMp.rbegin()->first, it->first);
else threeCnt += large(prev(it)->first, it->first);
assert(threeCnt==0 || threeCnt==1);
}
void delPoint(){
int i;
scanf("%d", &i);
/// ans=1 update
if(arr[i] == vector2(0, 0)){
oneCnt--;
return;
}
/// ans=2 update
twoCnt -= twoMp[-arr[i]];
twoMp[arr[i]]--;
/// ans=3 update
if((int)threeMp.size() == 1 || ((int)threeMp.size() == 2 && threeMp[arr[i]] == 1)){
threeMp[arr[i]]--;
if(!threeMp[arr[i]]) threeMp.erase(arr[i]);
threeCnt = 0;
return;
}
if(threeMp[arr[i]] > 1){
threeMp[arr[i]]--;
return;
}
auto it = threeMp.lower_bound(arr[i]);
if(it == prev(threeMp.end())) threeCnt -= large(it->first, threeMp.begin()->first);
else threeCnt -= large(it->first, next(it)->first);
if(it == threeMp.begin()) threeCnt += large(threeMp.rbegin()->first, it->first);
else threeCnt -= large(prev(it)->first, it->first);
assert(threeCnt==0 || threeCnt==1);
threeMp[arr[i]]--;
threeMp.erase(arr[i]);
it = threeMp.lower_bound(arr[i]);
if(it == threeMp.begin() || it == threeMp.end()) threeCnt += large(threeMp.rbegin()->first, threeMp.begin()->first);
else threeCnt += large(prev(it)->first, it->first);
assert(threeCnt==0 || threeCnt==1);
}
void print(){
if(oneCnt) puts("1");
else if(twoCnt) puts("2");
else if((int)threeMp.size() >= 3 && !threeCnt) puts("3");
else puts("0");
}
int main(){
scanf("%lld %lld %lld %d", &A, &B, &C, &n);
for(int i=1; i<=n; i++){
char c;
scanf(" %c", &c);
if(c=='A') addPoint();
else delPoint();
print();
}
}
Compilation message
Mixture.cpp: In function 'void addPoint()':
Mixture.cpp:98:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
98 | scanf("%lld %lld %lld", &x, &y, &z);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Mixture.cpp: In function 'void delPoint()':
Mixture.cpp:143:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
143 | scanf("%d", &i);
| ~~~~~^~~~~~~~~~
Mixture.cpp: In function 'int main()':
Mixture.cpp:191:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
191 | scanf("%lld %lld %lld %d", &A, &B, &C, &n);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Mixture.cpp:194:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
194 | scanf(" %c", &c);
| ~~~~~^~~~~~~~~~~
Mixture.cpp: In function 'bool calc3()':
Mixture.cpp:21:36: warning: 'prv.vector2::y' may be used uninitialized in this function [-Wmaybe-uninitialized]
21 | return vector2(x-r.x, y-r.y);
| ^
Mixture.cpp:82:13: note: 'prv.vector2::y' was declared here
82 | vector2 prv;
| ^~~
Mixture.cpp:21:36: warning: 'prv.vector2::x' may be used uninitialized in this function [-Wmaybe-uninitialized]
21 | return vector2(x-r.x, y-r.y);
| ^
Mixture.cpp:82:13: note: 'prv.vector2::x' was declared here
82 | vector2 prv;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 4 |
Halted |
0 ms |
0 KB |
- |
