Submission #296631

#	Time	Username	Problem	Language	Result	Execution time	Memory
296631		crackersamdjam	Mixture (BOI20_mixture)	C++17	0 / 100	2078 ms	512 KiB

Mixture

#include <bits/stdc++.h>
#define difs(x) (x).begin(), (x).end()
#define gc getchar()
#define pc(x) putchar(x)
template<typename T> void scan(T &x){x = 0;bool _=0;T c=gc;_=c==45;c=_?gc:c;while(c<48||c>57)c=gc;for(;c<48||c>57;c=gc);for(;c>47&&c<58;c=gc)x=(x<<3)+(x<<1)+(c&15);x=_?-x:x;}
template<typename T> void printn(T n){bool _=0;_=n<0;n=_?-n:n;char snum[65];int i=0;do{snum[i++]=char(n%10+48);n/= 10;}while(n);--i;if (_)pc(45);while(i>=0)pc(snum[i--]);}
template<typename First, typename ... Ints> void scan(First &arg, Ints&... rest){scan(arg);scan(rest...);}
template<typename T> void print(T n){printn(n);pc(10);}
template<typename First, typename ... Ints> void print(First arg, Ints... rest){printn(arg);pc(32);print(rest...);}

#ifndef ONLINE_JUDGE
template<typename T>
void pr(T a){std::cerr<<a<<std::endl;}
template<typename T,typename... Args>
void pr(T a, Args... args) {std::cerr<<a<<' ',pr(args...);}
#else
template<typename... Args>
void pr(Args... args){}
#endif

using namespace std;
using ld = double;
const int MM = 1e5+5;
const ld pi = acos(-1), eps = 1e-9;

int n, ptr, cnt;
ld x[MM], y[MM];
multiset<ld> angs, difs;
multiset<pair<ld, ld>> pts;

void up(ld f, ld s, bool b){
	ld dif = s-f;
	pr("dif", dif, b);
	if(dif < -eps)
		dif += 2*pi;
	if(b)
		difs.insert(dif);
	else
		difs.erase(difs.lower_bound(dif-eps));
}

int main(){
#ifdef CLION
	freopen("../in", "r", stdin);
#endif
	int a, b, c;
	scan(a, b, c, n);
	x[0] = (ld)a/(a+b+c);
	y[0] = (ld)b/(a+b+c);
	pr("pi", pi);
	pr("init", a, b, c, x[0], y[0]);
	
	for(int t = 0,i; t < n; t++){
		if(gc == 'A'){
			scan(a, b, c);
			i = ++ptr;
			x[i] = (ld)a/(a+b+c)-x[0];
			y[i] = (ld)b/(a+b+c)-y[0];
			pr("ins", a, b, c, x[i], y[i]);
			pts.insert({x[i], y[i]});
			ld ang = atan2(y[i], x[i]);
			pr("ang", ang, y[i], x[i]);
			ld opp = ang-pi;
			if(opp < -eps){
				opp += 2*pi;
			}
			auto it = angs.lower_bound(opp-eps);
			if(it != angs.end() and abs(*it-opp) < eps)
				cnt++;
			
			if(size(angs)){
				it = angs.lower_bound(ang-eps);
				auto pre = it, nx = it;
				if(pre == angs.begin())
					pre = --angs.end();
				else pre--;
				if(nx == angs.end())
					nx = angs.begin();
				
				if(pre != angs.end()){
					//do nothing for the first time
					if(size(angs) > 1)
						up(*pre, *nx, 0);
					up(*pre, ang, 1);
					up(ang, *nx, 1);
				}
			}
			angs.insert(ang);
		}
		else{
			scan(i);
			pr("del", i);

			pts.erase(pts.lower_bound({x[i], y[i]})); // eps?
			ld ang = atan2(y[i], x[i]);
			pr("ang", ang, y[i], x[i]);
			ld opp = ang-pi;
			if(opp < -eps)
				opp += 2*pi;
			
			auto it = angs.lower_bound(opp-eps);
			if(it != angs.end() and abs(*it-opp) < eps)
				cnt--;
			
			if(size(angs)){
				it = angs.lower_bound(ang-eps);
				auto pre = it, nx = it;
				if(pre == angs.begin())
					pre = --angs.end();
				else pre--;
				if(nx == angs.end())
					nx = angs.begin();
				
				if(pre != angs.end()){
					//do nothing for the first time
					if(size(angs) > 1)
						up(*pre, *nx, 1);
					up(*pre, ang, 0);
					up(ang, *nx, 0);
				}
			}
			angs.erase(angs.lower_bound(ang-eps)); //eps
		}
		
		auto it = pts.lower_bound({0, 0});
		pr("f", it->first, it->second);
		pr("cnt", cnt);
		if(it != pts.end() and abs(it->first) < eps and abs(it->second) < eps){
			print(1);
			continue;
		}
		if(cnt){
			print(2);
			continue;
		}
		if(size(difs)){
			auto itr = --difs.end();
			if(itr != difs.end() and *itr < pi){
				print(3);
				continue;
			}
		}
		print(0);
	}
}

• Subtask 1: 0 / 13
• Subtask 2: 0 / 17
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40