Submission #291898

#	Time	Username	Problem	Language	Result	Execution time	Memory
291898		Berted	Mixture (BOI20_mixture)	C++14	100 / 100	339 ms	21624 KiB

Mixture

#include <iostream>
#include <set>
#include <map>
#include <cmath>
#define ll long long
#define pii pair<ll, ll>
#define fst first
#define snd second
#define ell __int128_t
using namespace std;

ell gcd(ell a, ell b) 
{
	return (b ? gcd(b, a % b) : a);
}

ell abs(ell a)
{
	return ((a < 0) ? -a : a);
}

/*
	We could transform the mixtures into points
	(A / (A + B + C), B / (A + B + C)) describing the ratios of the mixtures

	Observe that given X points, we can make any mixture that is 
	the convex hull of the points.

	Therefore, there are 3 possibilities :
	Answer is 1, 2, or 3.
*/

struct frac
{
	ell a, b;
	frac() {a = 0; b = 0;}
	frac(ell n, ell d)
	{
		ell g = gcd(abs(n), abs(d));
		if (g)
		{
			n /= g; d /= g;
			if (d < 0) {n = -n; d = -d;}
			if (d == 0) {n = abs(n);}
		}
		a = n; b = d;
	}

	inline frac operator-(const frac &s) const
	{
		return frac(a * s.b - b * s.a, b * s.b);
	}

	inline frac operator/(const frac &s) const
	{
		return frac(a * s.b, b * s.a);
	}

	inline bool operator<(const frac& s) const
	{
		if (b == s.b && b == 0) {return a < s.a;}
		else if (b == 0) {return 1;}
		else if (s.b == 0) {return 0;}
		else return a * s.b < b * s.a;
	}

	inline bool operator>(const frac& s) const
	{
		if (b == s.b && b == 0) {return a > s.a;}
		else if (b == 0) {return 0;}
		else if (s.b == 0) {return 1;}
		else return a * s.b > b * s.a;
	}

	inline bool operator==(const frac& s) const
	{
		if (b == s.b && b == 0) {return a == s.a;}
		else if (b == 0) {return 0;}
		else if (s.b == 0) {return 0;}
		else return a * s.b == b * s.a;
	}

	inline long double toDec()
	{
		return (long double)a / b;
	}
};

#define pdd pair<frac, frac>

inline pdd getVec(pdd p1, pdd p2) 
{
	return {p2.fst - p1.fst, p2.snd - p1.snd};
}

const long double PI = acosl(0.0) * 2;

int n, sz = 0; pdd c;
pdd ar[100001]; 
map<frac, pii> mp;
multiset<long double> s;
int suc = 0;

inline int qry()
{
	if (mp[frac(0, 0)].fst) {return 1;}
	else if (suc) {return 2;}
	else
	{
		long double f = *s.begin();
		auto it = s.upper_bound(f + PI);
		//cout << (it == s.end()) << " " << *s.begin() << " " << *it << "\n";
		if (it != s.end() && it != s.begin() && prev(it) != s.begin() && *it - *prev(it) <= PI) return 3;
	}
	return 0;
}

inline void ins(pdd p)
{
	//cout << "Insert P : " << (ll)p.fst.a << "/" << (ll)p.fst.b << ", " << (ll)p.snd.a << "/" << (ll)p.snd.b << "\n";

	ar[sz++] = p;
	p = getVec(c, p); 
	//cout << "Insert CC : " << (ll)p.fst.a << "/" << (ll)p.fst.b << ", " << (ll)p.snd.a << "/" << (ll)p.snd.b << "\n";
	//cout << "FRACFRAC : " << (ll)((p.fst / p.snd).a) << "/" << (ll)((p.fst / p.snd).b) << "\n";
	int cur = 0;
	if (p.fst.a > 0) {cur = 0;}
	else if (p.fst.a < 0) {cur = 1;}
	else if (p.snd.a >= 0) {cur = 0;}
	else {cur = 1;}
	if (cur) 
	{
		mp[p.fst / p.snd].snd++;
		if (mp[p.fst / p.snd].snd == 1 && mp[p.fst / p.snd].fst > 0) {suc++;}
	}
	else 
	{
		mp[p.fst / p.snd].fst++;
		if (mp[p.fst / p.snd].fst == 1 && mp[p.fst / p.snd].snd > 0) {suc++;}
	}
	

	//cout << "INS S : " << atan2l(p.snd.toDec(), p.fst.toDec()) << "\n";
	s.insert(atan2l(p.snd.toDec(), p.fst.toDec()));
}

inline void del(pdd p)
{
	//cout << "Delete P : " << (ll)p.fst.a << "/" << (ll)p.fst.b << ", " << (ll)p.snd.a << "/" << (ll)p.snd.b << "\n";
	p = getVec(c, p); int cur = 0;
	
	//cout << "Delete CC : " << (ll)p.fst.a << "/" << (ll)p.fst.b << ", " << (ll)p.snd.a << "/" << (ll)p.snd.b << "\n";
	//cout << "FRACFRAC : " << (ll)((p.fst / p.snd).a) << "/" << (ll)((p.fst / p.snd).b) << "\n";
	if (p.fst.a > 0) {cur = 0;}
	else if (p.fst.a < 0) {cur = 1;}
	else if (p.snd.a >= 0) {cur = 0;}
	else {cur = 1;}
	if (cur) 
	{
		mp[p.fst / p.snd].snd--;
		if (mp[p.fst / p.snd].snd == 0 && mp[p.fst / p.snd].fst > 0) {suc--;}
	}
	else 
	{
		mp[p.fst / p.snd].fst--;
		if (mp[p.fst / p.snd].fst == 0 && mp[p.fst / p.snd].snd > 0) {suc--;}
	}

	//cout << "DELET S : " << atan2l(p.snd.toDec(), p.fst.toDec()) << "\n";
	s.erase(s.find(atan2l(p.snd.toDec(), p.fst.toDec())));
}

int main()
{
	ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int x, y, z;
	cin >> x >> y >> z;
	c = make_pair(frac(x, x + y + z), frac(y, x + y + z));
	
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		char q; cin >> q;
		if (q == 'A')
		{
			cin >> x >> y >> z;
			ins(make_pair(frac(x, x + y + z), frac(y, x + y + z)));
		}
		else
		{
			int k; cin >> k;
			del(ar[k - 1]);
		}
		cout << qry() << '\n';
	}
	return 0;
}

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