제출 #1276382

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1276382		wjankowski	Mixture (BOI20_mixture)	C++20	13 / 100	2095 ms	576 KiB

Mixture

#include <bits/stdc++.h>
using namespace std;

#define f first
#define s second
#define ll long long
#define pi pair<ll,ll>
constexpr int maxn = 502;

int it;
pi x[maxn], y[maxn];
bool del[maxn];

pi skr(pi a)
{
	ll nwd = __gcd(abs(a.f),abs(a.s));
	a.f /= nwd; a.s /= nwd;
	if(a.s < 0) a.f *= (-1LL), a.s *= (-1LL);
	return a;
}

int comp(pi a, pi b)
{
	ll val = a.f*b.s-b.f*a.s;
	if(val > 0) return 1;
	if(val == 0) return 0;
	return -1;
}

pi D(pi a, pi b)
{
	return skr({a.f*b.s-b.f*a.s,a.s*b.s});
}
pi M(pi a, pi b)
{
	return skr({a.f*b.f,a.s*b.s});
}

pi C(int p, int a, int b)
{
	return D(M(D(x[a],x[p]),D(y[b],y[p])),M(D(x[b],x[p]),D(y[a],y[p])));
}

int check()
{
	for(int i=1; i<=it; i++)
		if(!del[i] && x[i]==x[0] && y[i]==y[0]) return 1;

	for(int i=1; i<=it; i++)
	{
		if(del[i]) continue;
		for(int j=i+1; j<=it; j++)
		{
			if(del[j]) continue;
			if(C(i,0,j).first) continue;
			if(comp(x[0],x[i]) == comp(x[0],x[j])
				&& comp(x[0],x[i]) != 0) continue;
			if(comp(y[0],y[i]) == comp(y[0],y[j])
				&& comp(y[0],y[i]) != 0) continue;

			return 2;
		}
	}

	for(int i=1; i<=it; i++)
	{
		if(del[i]) continue;
		for(int j=1; j<=it; j++)
		{
			if(del[j]) continue;
			for(int k=1; k<=it; k++)
			{
				if(del[k]) continue;
				ll c1 = C(0,i,j).first;
				ll c2 = C(0,j,k).first;
				ll c3 = C(0,k,i).first;
				if(c1 > 0 && c2 > 0 && c3 > 0) return 3;
				if(c1 < 0 && c2 < 0 && c3 < 0) return 3;
			}
		}
	}
	return 0;
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	ll S,P,G,n; cin >> S >> P >> G >> n;
	x[0] = skr({S,S+P+G}); y[0] = skr({P,S+P+G});

	while(n--)
	{
		char ch; cin >> ch;
		if(ch == 'A')
		{
			ll A,B,C; cin >> A >> B >> C;
			x[++it] = skr({A,A+B+C});
			y[it] = skr({B,A+B+C});
		}
		else
		{
			int i; cin >> i;
			del[i]=1;
		}
		cout << check() << '\n';
	}
}

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