Submission #256965

#	Time	Username	Problem	Language	Result	Execution time	Memory
256965		easrui	Mixture (BOI20_mixture)	C++17	100 / 100	1048 ms	24312 KiB

Mixture

#include <bits/stdc++.h>
#define PI 3.1415926535
using namespace std;
typedef long long ll;

const int MN = 1e5+5;

ll gcd(ll a, ll b)
{
	a = abs(a);
	b = abs(b);
	if(a<b) swap(a,b);
	if(a==0) return 1;
	if(b==0) return a;
	return gcd(b,a%b);
}

double getA(double x, double y, double z)
{
	if(!x&&!y&&!z) return -1;
	//x /= 10000.0, y /= 10000.0, z /= 10000.0;
	double a = (x-y/2.0-z/2.0)/sqrt(x*x+y*y+z*z)/sqrt(1.5);
	if(a>1) a = 1;
	if(a<-1) a = -1;
	a = acos(a);
	if(y<z) a = 2*PI-a;
	return a;
}

struct point
{
	ll x,y,z;
	bool operator < (const point& p) const { return getA(x,y,z)<getA(p.x,p.y,p.z); }
};

double getA(point p)
{
	return getA(p.x,p.y,p.z);
}

point inv(point p)
{
	return point{-p.x,-p.y,-p.z};
}

map<point,int> m;
set<point> s;

bool solve()
{
	if(s.empty()) return 0;
	auto it = s.begin();

	if(getA(*it)>PI) return 0;
	it = s.lower_bound(inv(*it));

	if(it==s.end()) return 0;
	double hi = getA(*it);

	it--;

	if(it==s.begin()) return 0;
	double lo = getA(*it);

	return hi-lo<=PI;
}

int main()
{
    ios_base::sync_with_stdio(0),cin.tie(0);
    
    ll X,Y,Z,T;
    cin >> X >> Y >> Z;
    T = X+Y+Z;

    int N;
    cin >> N;
    
    int num = 0;
    ll cnt = 0;
    vector<point> p(N+1);
    vector<double> a(N+1);

    p[0] = point{0,0,0}; 
    while(N--){
    	char C;
    	cin >> C;

    	ll x,y,z,t,g;
    	if(C=='A'){
    		cin >> x >> y >> z;
    		t = x+y+z;
			x = x*T-X*t, y = y*T-Y*t, z = z*T-Z*t;
			g = gcd(gcd(x,y),z);
			x /= g, y /= g, z /= g;
    		p[++num] = point{x,y,z};
    		//if(N==6952) cout << x << ' ' << y << ' ' << z << ' ';
    		m[p[num]]++;
    		//cout << m[p[0]] << '\n';
    		s.insert(p[num]);
    		if(x||y||z){
    			cnt += m[inv(p[num])];
    		}
    	}
    	if(C=='R'){
    		cin >> t;
    		m[p[t]]--;
    		if(!m[p[t]]) s.erase(p[t]);
    		if(p[t].x||p[t].y||p[t].z){
    			cnt -= m[inv(p[t])];
    		}
    	}
     	if(m[p[0]]){
    		cout << 1 << '\n';
    	}
    	else if(cnt){
    		cout << 2 << '\n';
    	}
    	else if(solve()){
    		cout << 3 << '\n';
    	}
    	else{
    		cout << 0 << '\n';
    	}
    }
}

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