Submission #951727

#	Time	Username	Problem	Language	Result	Execution time	Memory
951727		koukirocks	Mixture (BOI20_mixture)	C++17	100 / 100	128 ms	9876 KiB

Mixture

#include <bits/stdc++.h>
#define speed ios_base::sync_with_stdio(0); cin.tie(0)
#define all(x) (x).begin(),(x).end()
#define F first
#define S second
 
using namespace std;
typedef long long ll;
typedef double db;
typedef long double ldb;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
const ll MAX=1e5+10,P=1e9+7;
const ll INF=0x3f3f3f3f,oo=0x3f3f3f3f3f3f3f3f;

ldb x,y,z;
ll n;
int s0=0;
int s1=0;
pair<ldb,ldb> btl[MAX];
const ldb PI=acos(-1.0),eps=1e-15;
struct cmp{
	bool operator()(const ldb& ax,const ldb& ay)const{
		return ax+eps<ay;
	}
};
multiset<ldb,cmp> agl;


bool eq(ldb a,ldb b) {
	return abs(a-b)<=eps;
}

ldb cal(ldb a,ldb b) {
	ldb ans=atan2(a,b);
//	cout<<a<<" "<<b<<" "<<ans<<" ang\n";
	if (ans<0) ans+=PI+PI;
	return ans;
}

ldb rev(ldb now) {
	if (now>PI) return now-PI;
	else return now+PI;
}

void isrt(ldb dx,ldb dy) {
	if (eq(dx,0) and eq(dy,0)) s0++;
	else {
		ldb now=cal(dx,dy);
//		cout<<now<<" "<<rev(now)<<" rev\n";
		if (agl.find(now)==agl.end() and agl.find(rev(now))!=agl.end()) s1++;
		agl.insert(now);
	}
}

void del(int id) {
	auto [dx,dy]=btl[id];
	if (eq(dx,0) and eq(dy,0)) s0--;
	else {
		ldb now=cal(dx,dy);
		agl.erase(agl.find(now));
		if (agl.find(now)==agl.end() and agl.find(rev(now))!=agl.end()) s1--;
	}
}

int main() {
	speed;
//	cout<<PI<<"\n"<<flush;
	cin>>x>>y>>z;
	ldb tsum=x+y+z;
	x/=tsum;
	y/=tsum;
//	cout<<x<<" "<<y<<" xy\n";
	cin>>n;
	int now=1;
	for (int i=1;i<=n;i++) {
		char c;
		cin>>c;
		if (c=='A') {
			ldb tx,ty,tz;
			cin>>tx>>ty>>tz;
			ldb sum=tx+ty+tz;
			tx/=sum;
			ty/=sum;
//			cout<<now<<" "<<tx<<" "<<ty<<" xy1\n";
			tx-=x;
			ty-=y;
//			cout<<now<<" "<<tx<<" "<<ty<<" xy2\n";
			btl[now++]={tx,ty};
			isrt(tx,ty);
		} else {
			int id;
			cin>>id;
			del(id);
		}
//		for (auto k:agl) cout<<k<<" ";
//		cout<<" st\n";
//		cout<<s1<<" s1\n";
		if (s0>0) cout<<"1\n";
		else if (s1>0) cout<<"2\n";
		else if (agl.size()>=3) {
			bool yes=true;
			yes&=((PI+PI-*agl.rbegin()+*agl.begin())<PI);
			auto it=agl.lower_bound(PI);
			if (it==agl.begin()) yes=false;
			else {
				yes&=((*it-*prev(it))<PI);
			}
			if (yes) cout<<"3\n";
			else cout<<"0\n";
		} else {
			cout<<"0\n";
		}
	}
	return 0;
}

/*
5 5 5
5
A 2 2 1
A 2 2 3
A 2 2 3
R 3
R 2
*/

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