제출 #530675

#제출 시각아이디문제언어결과실행 시간메모리
530675c28dnv9q3Mixture (BOI20_mixture)C++17
13 / 100
2 ms336 KiB
#include <iostream> #include <bits/stdc++.h> #define lli long long int #define RBit _Rb_tree_iterator<pair<const pair<lli, lli>, int>> using namespace std; lli a, b, c; lli ggt(lli x, lli y) { return x == 0 ? y : ggt(y % x, x); } pair<lli, lli> toPoint(lli tX, lli tY, lli tZ) { //cout << tX << " " << tY << " " << tZ << "\n"; lli x, y; if (a != 0) { x = tY * a - tX * b; y = tZ * a - tX * c; } else if (b != 0) { x = tX * b - tY * a; y = tZ * b - tY * c; } else { x = tX * c - tZ * a; y = tY * c - tZ * b; } lli d = abs(ggt(x, y)); if (d == 0) return {0, 0}; x /= d; y /= d; //cout << x << " " << y << "\n"; return {x, y}; } pair<lli, lli> inverse(pair<lli, lli> p) { return {- p.first, - p.second}; } struct cmp { bool operator()(const pair<lli, lli>& pA, const pair<lli, lli>& pB) const { if (pA.first >= 0 && pB.first < 0) return true; if (pB.first >= 0 && pA.first < 0) return false; return pA.second * pB.first > pB.second * pA.first; } }; ostream& operator << (ostream& io, const pair<lli, lli>& p) { io << p.first << " " << p.second; return io; } ostream& operator << (ostream& io, const pair<pair<lli, lli>, int>& p) { io << p.first << " x " << p.second << "\n"; return io; } bool okay(map<pair<lli, lli>, int, cmp> circle) { if (circle.empty()) return false; RBit it = circle.begin(); RBit inv = circle.upper_bound(inverse((*it).first)); if (circle.end() == inv) inv = circle.begin(); RBit invinv = circle.upper_bound(inverse((*inv).first)); if (circle.end() == invinv) invinv = circle.begin(); return it != inv && inv != invinv; } int main() { cin >> a >> b >> c; int n = 0, d = 0; pair<lli, lli> p, inv; vector<pair<lli, lli>> regal; map<pair<lli, lli>, int, cmp> circle; int q; cin >> q; string inst; int pos; lli x, y, z; for (int i = 0; i < q; ++i) { //cout << i << "\n"; cin >> inst; if (inst == "A") { cin >> x >> y >> z; p = toPoint(x, y, z); inv = inverse(p); /* cout << "\n"; cout << x << " " << y << " " << z << "\n"; cout << p; cout << "\n\n"; */ /* cout << "adding\n"; cout << p; cout << "\n"; */ if ((*circle.find(p)).first == p && (*circle.find(inv)).first == inv) d--; regal.push_back(p); if (p.first == 0 && p.second == 0) n++; else { circle[p]++; } /* cout << "dtest\n"; cout << *circle.end(); cout << circle[p] << "\n"; cout << *circle.find(p); cout << p << "\n"; cout << *circle.find(inv); cout << inv << "\n"; */ if ((*circle.find(p)).first == p && (*circle.find(inv)).first == inv) d++; } if (inst == "R") { cin >> pos; p = regal[pos - 1]; inv = inverse(p); if ((*circle.find(p)).first == p && (*circle.find(inv)).first == inv) d--; if (p.first == 0 && p.second == 0) n--; else { circle[p]--; if (circle[p] == 0) circle.erase(p); } if ((*circle.find(p)).first == p && (*circle.find(inv)).first == inv) d++; } /* cout << "0 0 x " << n << "\n"; for (pair<pair<lli, lli>, int> j: circle) cout << j; cout << "\n"; */ if (n > 0) { cout << 1; } else { if (d > 0) { cout << 2; } else { if (okay(circle)) { cout << 3; } else { cout << 0; } } } cout << "\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...