Submission #897584

#	Time	Username	Problem	Language	Result	Execution time	Memory
897584		pcc	Mixture (BOI20_mixture)	C++17	0 / 100	0 ms	348 KiB

Mixture

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

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>


struct point{
	ll x,y,z;
	point(){x = y = z = 0;}
	point(int a,int b,int c){x = a,y = b,z = c;}
	point operator+(point b)const{return point(x+b.x,y+b.y,z+b.z);}
	point operator-(point b)const{return point(x-b.x,y-b.y,z-b.z);}
	ll operator*(point b)const{return x*b.x+y*b.y+z*b.z;}
	point operator^(point b)const{return point(y*b.z-z*b.y,z*b.x-x*b.z,x*b.y-y*b.x);}
	bool operator<(point b)const{return x== b.x?y == b.y?z<b.z:y<b.y:x<b.x;}
	bool operator==(point b)const{return x==b.x&&y==b.y&&z==b.z;}
	bool operator!=(point b)const{return !((*this) == b);}
};


const int mxn = 5050;
ll Q;
multiset<point> st;
point arr[mxn];
int pt = 0;
point tar;

inline point trans(point tmp){
	ll G = 0;
	if(tmp.x)G = __gcd(G,tmp.x);
	if(tmp.y)G = __gcd(G,tmp.y);
	if(tmp.z)G = __gcd(G,tmp.z);
	if(!G)G = 1;
	tmp.x/=G,tmp.y/=G,tmp.z/=G;
	return tmp;
}

inline int getans(){
	int re = 4;
	for(auto it = st.begin();it != st.end();it++){
		if(*it == tar)re = min(re,1);
		auto ta = *it;
		for(auto jt = next(it);jt != st.end();jt++){
			if(*it == *jt)continue;
			auto tb = *jt;
			if((ta^tb)*tar == 0)re = min(re,2);
		}
	}
	vector<point> id;
	for(auto &i:st){
		if(id.size() == 3)break;
		if(id.empty())id.push_back(i);
		else if(id.size() == 1&&id[0] != i)id.push_back(i);
		else{
			if((id[0]^id[1])*id[2] != 0)id.push_back(i);
		}
	}
	if(id.size() == 3)re = min(re,3);
	if(re == 4)re = 0;
	return re;
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>tar.x>>tar.y>>tar.z;
	tar = trans(tar);
	cin>>Q;
	while(Q--){
		char tp;
		cin>>tp;
		if(tp == 'A'){
			pt++;
			cin>>arr[pt].x>>arr[pt].y>>arr[pt].z;
			arr[pt] = trans(arr[pt]);
			st.insert(arr[pt]);
		}
		else{
			int id;
			cin>>id;
			st.erase(st.find(arr[id]));
		}
		cout<<getans()<<'\n';
	}
	return 0;
}

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