oj.uz

Submission #256942

# Submission time Handle Problem Language Result Execution time Memory
256942 2020-08-03T12:25:59 Z easrui Mixture (BOI20_mixture) C++17
0 / 100
 0 ms 384 KB 
#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(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); }
};

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};
    		m[p[num]]++;
    		if(x||y||z){
    			cnt += m[inv(p[num])];
    			s.insert(p[num]);
    		}
    	}
    	if(C=='R'){
    		cin >> t;
    		m[p[t]]--;
    		if(p[t].x||p[t].y||p[t].z){
    			cnt -= m[inv(p[t])];
    			s.erase(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
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Incorrect 0 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Incorrect 0 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Incorrect 0 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Incorrect 0 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -