Submission #257264

#	Time	Username	Problem	Language	Result	Execution time	Memory
257264		maximath_1	Mixture (BOI20_mixture)	C++11	100 / 100	394 ms	8548 KiB

Mixture

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

#define ll long long
#define pt pair<ll, ll>

int sign(ll x){
	if(x > 0) return 1;
	if(x < 0) return -1;
	return 0;
}
int half(pt x){
	if(x.second != 0)
		return sign(x.second);
	return -sign(x.first);
}

__int128_t cross(pt a, pt b){
	return (__int128_t)a.first * b.second - (__int128_t)a.second * b.first;
}
bool angCmp(pt a, pt b){
	int A = half(a), B = half(b);
	if(A == B) return cross(a, b) > 0;
	return A < B;
}

typedef array<ll, 3> T;

T a;
int eq = 0, neg = 0;
vector<pt> cat;

struct cmp{
	bool operator()(const pt&a, const pt&b) const{
		return angCmp(a, b);
	}
};

map<pair<ll, ll>, int, cmp> mp;

T operator*(T a, ll b){
	for(int i = 0; i < 3; i ++) 
		a[i] *= b;
	return a;
}
T operator+(T a, T b){
	for(int i = 0; i < 3; i ++)
		a[i] += b[i];
	return a;
}
T operator-(T a, T b){
	for(int i = 0; i < 3; i ++)
		a[i] -= b[i];
	return a;
}
ll sum(T a){return a[0] + a[1] + a[2];}

ll dot(T a, T b){
	ll res = 0;
	for(int i = 0; i < 3; i ++)
		res += a[i] * b[i];
	return res;
}

pair<ll, ll> lst;

bool bad(pt a, pt b){
	return a == b || cross(a, b) < 0;
}

void add(pair<ll, ll> p, int x){
	if(p.first == 0 && p.second == 0){
		eq += x; return;
	}
	vector<pair<ll, ll> > cand = {lst, p};
	if(x == 1){
		if(!mp.count(p) && mp.count({-p.first, -p.second})) neg ++;
		mp[p] ++;
	}else{
		if(mp[p] == 1 && mp.count({-p.first, -p.second})) neg --;
		auto it = mp.find(p);
		if(it == mp.begin()) it = mp.end();
		it --; cand.push_back(it -> first);
		mp[p] --;
		if(!mp[p]) mp.erase(p);
	}

	lst = {0, 0};
	for(pair<ll, ll> i : cand){
		auto it = mp.find(i);
		if(it == mp.end()) continue;
		auto nx = next(it);
		if(nx == mp.end()) nx = mp.begin();

		if(bad(i, nx -> first))
			lst = i;
	}
}

int ans(){
	if(eq) return 1;
	if(neg) return 2;
	if(mp.size() && lst.first == 0 && lst.second == 0)
		return 3;
	return 0;
}

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

	long long rd;
	cin >> rd; a[0] = rd;
	cin >> rd; a[1] = rd;
	cin >> rd; a[2] = rd;
	int q; cin >> q;
	for(char c; q --;){
		cin >> c;
		if(c == 'A'){
			T x;
			cin >> rd; x[0] = rd;
			cin >> rd; x[1] = rd;
			cin >> rd; x[2] = rd;
			
			x = x * sum(a) - a * sum(x);
			pt p = {dot(x, {1, -1, 0}), dot(x, {1, 1, -2})};
			ll gc = __gcd(abs(p.first), abs(p.second));
			if(p.first || p.second) p.first /= gc, p.second /= gc;
			cat.push_back(p);
			add(cat.back(), 1);
		}else{
			int r; cin >> r; r --;
			add(cat[r], -1);
		}
		ll get = (ll)ans();
		cout << get << endl;
	}
	return 0;
}

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