제출 #1262280

#제출 시각아이디문제언어결과실행 시간메모리
1262280Zbyszek99Mixture (BOI20_mixture)C++20
100 / 100
534 ms40136 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define ll long long #define ld long double #define ull unsigned long long #define ff first #define ss second #define pii pair<int,int> #define pll pair<long long, long long> #define vi vector<int> #define vl vector<long long> #define pb push_back #define rep(i, b) for(int i = 0; i < (b); ++i) #define rep2(i,a,b) for(int i = a; i <= (b); ++i) #define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c) #define count_bits(x) __builtin_popcountll((x)) #define all(x) (x).begin(),(x).end() #define siz(x) (int)(x).size() #define forall(it,x) for(auto& it:(x)) using namespace __gnu_pbds; using namespace std; typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set; //mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());} //ll los(ll a, ll b) {return a + (mt() % (b-a+1));} const int INF = 1e9+50; const ll INF_L = 1e18+40; const ll MOD = 1e9+7; struct point { ld x,y; int ind = -1; bool operator<(const point& other) const { if(ind > 0) return ind < other.ind; if(x == 0 && y == 0) return 0; if(other.x == 0 && other.y == 0) return 1; if(x == other.x && y == other.y) return 0; int d1 = y > 0; int d2 = other.y > 0; if(d1 != d2) { if(y <= 0) return 0; return 1; } if(x*other.y-other.x*y != 0) { return x*other.y-other.x*y < 0; } else { int d1 = y > 0; int d2 = other.y > 0; if(d1 != d2) { if(y > 0) return 0; return 1; } if(y == other.y && y == 0) { return x>other.x; } return (abs(x)+abs(y))>(abs(other.x)+abs(other.y)); } } }; bool is180(point p1, point p2) { return p1.x*p2.y-p2.x*p1.y>0; } map<ld,int> lines[2]; set<ld> dif_lines; int lines_cnt; int cnt_180; pair<ld,ld> points[100001]; int cur = 1; multiset<point> sort_points; map<pair<ld,ld>,int> point_cnt; int rel_ind[100001]; void add(ld x, ld y, int c) { int type = 0; if((x == 0 && y <= 0) || x > 0) type = 1; ld p = round(x/y*1e12); dif_lines.insert(p); if(y == 0) p = -1; lines[type][p]++; if(lines[type][p] == 1 && lines[type^1][p] >= 1) lines_cnt++; point_cnt[{x,y}]++; if(siz(sort_points) == 0) { sort_points.insert({x,y,c}); cnt_180++; } else { auto nxt = sort_points.upper_bound({x,y,c}); point nx; if(nxt == sort_points.end()) { nx = *(sort_points.begin()); } else { nx = *nxt; } point pv; if(nxt != sort_points.begin()) { nxt--; pv = *nxt; } else { pv = *(--sort_points.end()); } point p = {x,y,c}; if(is180(pv,nx) || siz(sort_points) == 1) cnt_180--; if(is180(pv,p)) cnt_180++; if(is180(p,nx)) cnt_180++; sort_points.insert(p); } } void del(ld x, ld y, int c) { int type = 0; if((x == 0 && y <= 0) || x > 0) type = 1; ld p = round(x/y*1e12); if(y == 0) p = -1; if(lines[type][p] == 1 && lines[type^1][p] >= 1) lines_cnt--; lines[type][p]--; if(lines[type][p]+lines[type^1][p] == 0) dif_lines.erase(p); point_cnt[{x,y}]--; if(siz(sort_points) == 1) { sort_points.erase(sort_points.find({x,y,c})); cnt_180--; } else { sort_points.erase(sort_points.find({x,y,c})); auto nxt = sort_points.upper_bound({x,y,c}); point nx; if(nxt == sort_points.end()) { nx = *(sort_points.begin()); } else { nx = *nxt; } point pv; if(nxt != sort_points.begin()) { nxt--; pv = *nxt; } else { pv = *(--sort_points.end()); } point p = {x,y,c}; if(is180(pv,nx) || siz(sort_points) == 1) cnt_180++; if(is180(pv,p)) cnt_180--; if(is180(p,nx)) cnt_180--; } } int main() { ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); //random_start(); ld x1,y1,z1; cin >> x1 >> y1 >> z1; int cyc = 0; while(z1 == 0) { cyc++; swap(z1,y1); swap(y1,x1); } bool is_zero = (z1 == 0); if(x1 != 0 || y1 != 0) { ll g = __gcd((ll)x1,(ll)y1); x1 /= g; y1 /= g; z1 /= g; } if(!is_zero) { x1 /= z1; y1 /= z1; } int n; cin >> n; vector<pair<char,int>> opers; rep(i,n) { char z; cin >> z; if(z == 'A') { ld x,y,z; cin >> x >> y >> z; opers.pb({'A',-1}); rep(i,cyc) { swap(z,y); swap(y,x); } if(x != 0 && y != 0) { ll g = __gcd((ll)x,(ll)y); x /= g; y /= g; z /= g; } if(z != 0) { x /= z; y /= z; x -= x1; y -= y1; } add(x,y,-cur); points[cur++] = {x,y}; } else { int x; cin >> x; opers.pb({'R',x}); } } int p = 1; forall(it,sort_points) { rel_ind[-it.ind] = p++; } lines_cnt = 0; cnt_180 = 0; dif_lines = {}; rep(d,2) lines[d] = {}; point_cnt = {}; sort_points = {}; cur = 1; forall(it,opers) { if(it.ff == 'A') { add(points[cur].ff,points[cur].ss,rel_ind[cur]); cur++; } else { del(points[it.ss].ff,points[it.ss].ss,rel_ind[it.ss]); } if(point_cnt[{0,0}]) cout << "1\n"; else if(lines_cnt > 0) cout << "2\n"; else if(cnt_180 == 0 && siz(sort_points) > 2 && siz(dif_lines) > 1) cout << "3\n"; else cout << "0\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...