Submission #826680

#	Time	Username	Problem	Language	Result	Execution time	Memory
826680		QwertyPi	Mixture (BOI20_mixture)	C++14	60 / 100	2068 ms	14920 KiB

Mixture

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

struct V3d{
	int x, y, z;
	void norm(){
		int g = __gcd(__gcd(x, y), z); g = abs(g);
		if(g != 0) x /= g, y /= g, z /= g;
	}
	bool operator< (const V3d o) const {
		if(x != o.x) return x < o.x;
		if(y != o.y) return y < o.y;
		if(z != o.z) return z < o.z;
		return 0;
	}
};

int dot(V3d a, V3d b){
	return a.x * b.x + a.y * b.y + a.z * b.z;
}

__int128_t dot128(V3d a, V3d b){
	return (__int128_t) a.x * b.x + (__int128_t) a.y * b.y + (__int128_t) a.z * b.z;
}

long double triple(V3d a, V3d b, V3d c){
	long double r = 0;
	r += (long double) a.x * b.y * c.z;
	r += (long double) a.z * b.x * c.y;
	r += (long double) a.y * b.z * c.x;
	r -= (long double) a.x * b.z * c.y;
	r -= (long double) a.y * b.x * c.z;
	r -= (long double) a.z * b.y * c.x;
	return r;
}

V3d operator* (V3d a, int n){
	return {a.x * n, a.y * n, a.z * n};
}

V3d operator- (V3d a, V3d b){
	return {a.x - b.x, a.y - b.y, a.z - b.z};
}

V3d operator- (V3d b){
	return {-b.x, -b.y, -b.z};
}

V3d vds[100011]; int ai = 0;
V3d f;

long double deg(V3d a, V3d b){
	__int128_t p = dot128(a, b);
	long double q = sqrt((long double) dot128(a, a)) * sqrt((long double) dot128(b, b));
	return acos(min(1.0L, (long double) p / q)) * (triple(f, a, b) > 0 ? 1 : -1);
}

const long double PI = 3.1415926535;

struct Angle{
	bool init = false;
	multiset<long double> S;
	void add(long double d){
		S.insert(d);
	}
	void rem(long double d){
		S.erase(S.find(d));
	}
	bool qry(){
		if(!init) return false;
		if(S.size() < 3) return false;
		uniform_real_distribution<long double> dist(-PI, PI);
		random_device rd;
		for(int tr = 0; tr < 50; tr++){
			long double d = dist(rd);
			auto ptr = S.lower_bound(d);
			if(ptr != S.begin() && ptr != S.end()){
				long double diff = *ptr - *prev(ptr);
				if(diff > PI) return false;
			}else{
				long double diff = *S.begin() + PI * 2 - *prev(S.end());
				if(diff > PI) return false;
			}
		}
		return true;
	}
} Solver;

struct Handle{
	int c1 = 0, c2 = 0; map<V3d, int> cnt;
	V3d o;
	void add(V3d a){
		a.norm();
		if(a.x == 0 && a.y == 0 && a.z == 0) { c1++; return; }
		if(!Solver.init){
			Solver.init = true;
			o = a; Solver.add(deg(o, a));
		}else{
			Solver.add(deg(o, a));
		}
		cnt[a]++; if(cnt[a] == 1 && cnt[-a] > 0) c2++;
	}
	void rem(V3d a){
		a.norm();
		if(a.x == 0 && a.y == 0 && a.z == 0) { c1--; return; }
		Solver.rem(deg(o, a));
		cnt[a]--; if(cnt[a] == 0 && cnt[-a] > 0) c2--;
	}
	int qry(){
		if(c1 > 0) return 1;
		if(c2 > 0) return 2;
		if(Solver.qry()) return 3;
		return 0;
	}
} handle;

int32_t main(){
	int x, y, z; cin >> x >> y >> z; f = V3d {x, y, z};
	int n; cin >> n;
	for(int i = 0; i < n; i++){
		char c; cin >> c;
		if(c == 'A'){
			int x, y, z; cin >> x >> y >> z;
			V3d a {x, y, z};
			vds[++ai] = a * dot(f, f) - f * dot(a, f);
			handle.add(vds[ai]);
		}else{
			int x; cin >> x;
			handle.rem(vds[x]);
		}
		cout << handle.qry() << endl;
	}
}

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