Submission #256936

#	Time	Username	Problem	Language	Result	Execution time	Memory
256936		easrui	Mixture (BOI20_mixture)	C++17	0 / 100	0 ms	384 KiB

Mixture

#include <bits/stdc++.h>
#define va first
#define vb second
#define all(x) (x).begin(), (x).end()
#define PI 3.1415926535
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<pii,int> ppi;
typedef pair<int,pii> pip;

const int MN = 1e5+5;
const int MOD = 1e9+7;
const int INF = 1e9;

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(ll x, ll y, ll z)
{
	if(!x&&!y&&!z) return -1;
	double a = acos((x-y/2.0-z/2.0)/sqrt(x*x+y*y+z*z)/sqrt(1.5));
	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); }
};

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

bool solve()
{
	auto it = s.begin();
	if(getA(it->x,it->y,it->z)>PI) return 0;
	point p{-it->x,-it->y,-it->z};
	it = s.lower_bound(p);
	if(it==s.end()) return 0;
	double hi = getA(it->x,it->y,it->z);
	it--;
	if(it==s.begin()) return 0;
	double lo = getA(it->x,it->y,it->z);
	return hi-lo<=PI;
}

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

    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;
    	//cout << m[p[0]] << '\n';
    	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;
    		//cout << x << ' ' << y << ' ' << z << '\n';
    		point dot{x,y,z};
    		point dot2{-x,-y,-z};
    		p[++num] = dot;
    		m[dot]++;
    		if(x||y||z){
    			cnt += m[dot2];
    			s.insert(dot);
    		}
    		//cout << cnt << '\n';
    	}
    	if(C=='R'){
    		cin >> t;
    		m[p[t]]--;
    		if(p[t].x||p[t].y||p[t].z){
    			point dot{-p[t].x,-p[t].y,-p[t].z};
    			cnt -= m[dot];
    			s.erase(p[t]);
    		}
    		//cout << cnt << '\n';
    	}
    	//cout << cnt << '\n';
    	if(m[p[0]]){
    		//cout << m[p[0]] << '\n';
    		cout << 1 << '\n';
    	}
    	else if(cnt){
    		cout << 2 << '\n';
    	}
    	else if(solve()){
    		cout << 3 << '\n';
    	}
    	else{
    		cout << 0 << '\n';
    	}
    }
}

Compilation message (stderr)

Mixture.cpp: In function 'int main()':
Mixture.cpp:61:16: warning: unused variable 'G' [-Wunused-variable]
     ll X,Y,Z,T,G;
                ^

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