Submission #299522

#	Time	Username	Problem	Language	Result	Execution time	Memory
299522		E869120	Mixture (BOI20_mixture)	C++14	60 / 100	1777 ms	9268 KiB

Mixture

#include <bits/stdc++.h>
using namespace std;
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("Ofast")

__int128 gcd(__int128 a, __int128 b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}

// ------------------------------ Fraction Class ----------------------------
struct Fraction {
	__int128 r1, r2;
};

Fraction operator+(const Fraction &a1, const Fraction &a2) {
	__int128 v1 = a1.r1 * a2.r2 + a1.r2 * a2.r1;
	__int128 v2 = a1.r2 * a2.r2;
	//__int128 vv = gcd(v1, v2); if (vv < 0) vv = -vv;
	return Fraction{v1, v2};
}

Fraction operator-(const Fraction &a1, const Fraction &a2) {
	__int128 v1 = a1.r1 * a2.r2 - a1.r2 * a2.r1;
	__int128 v2 = a1.r2 * a2.r2;
	//__int128 vv = gcd(v1, v2); if (vv < 0) vv = -vv;
	return Fraction{v1, v2};
}

Fraction operator*(const Fraction &a1, const Fraction &a2) {
	__int128 v1 = a1.r1 * a2.r1;
	__int128 v2 = a1.r2 * a2.r2;
	//__int128 vv = gcd(v1, v2); if (vv < 0) vv = -vv;
	return Fraction{v1, v2};
}

bool operator<(const Fraction &a1, const Fraction &a2) {
	__int128 v1 = a1.r1 * a2.r2 - a1.r2 * a2.r1;
	if (v1 < 0) return true;
	return false;
}

bool operator>(const Fraction &a1, const Fraction &a2) {
	__int128 v1 = a1.r1 * a2.r2 - a1.r2 * a2.r1;
	if (v1 > 0) return true;
	return false;
}

bool operator==(const Fraction &a1, const Fraction &a2) {
	__int128 v1 = a1.r1 * a2.r2 - a1.r2 * a2.r1;
	if (v1 == 0) return true;
	return false;
}

Fraction seikika(Fraction a1) {
	__int128 vv = gcd(a1.r1, a1.r2); if (vv < 0) vv = -vv;
	return Fraction{a1.r1 / vv, a1.r2 / vv};
}

// --------------------------------- Point Class --------------------------
struct Point {
	Fraction px, py;
};

bool operator==(const Point &a1, const Point &a2) {
	if (a1.px == a2.px && a1.py == a2.py) return true;
	return false;
}

bool operator<(const Point &a1, const Point &a2) {
	if (a1.px < a2.px) return true;
	if (a1.px > a2.px) return false;
	if (a1.py < a2.py) return true;
	return false;
}

Point operator+(const Point &a1, const Point &a2) {
	return Point{a1.px + a2.px, a1.py + a2.py};
}

Point operator-(const Point &a1, const Point &a2) {
	return Point{a1.px - a2.px, a1.py - a2.py};
}

Fraction dot(Point a1, Point a2) {
	return (a1.px * a2.px) + (a1.py * a2.py);
}

Fraction crs(Point a1, Point a2) {
	Fraction t1 = (a1.px * a2.py);
	Fraction t2 = (a1.py * a2.px);
	return t1 - t2;
}

// ----------------------------------- Variables ---------------------------
Fraction ZERO = Fraction{0LL, 1LL};
long long SX, SY, SZ;
long long Q;
long long D1[1 << 18], D2[1 << 18], D3[1 << 18];
long long DD[1 << 18];
long long idx[1 << 18];
char C[1 << 18];

// Geometry Part
int N;
Point BASE;
Point H[1 << 18], HH[1 << 18];
vector<pair<Point, int>> G;

// Maeshori
bool used[5009];
bool r1[5009];
bool r2[5009][5009];
int cntw = 0;

bool solve1() {
	vector<int> vec;
	for (int i = 0; i < N; i++) { if (used[i] == true) vec.push_back(i); }
	for (int i = 0; i < (int)vec.size(); i++) {
		if (r1[vec[i]] == true) return true;
	}
	return false;
}

bool solve2() {
	if (cntw >= 1) return true;
	return false;
}

bool solve3() {
	vector<int> vec;
	for (int i = 0; i < N; i++) { if (used[i] == true) vec.push_back(i); }
	if (vec.size() <= 2) return false;
	
	vector<Point> G1;
	G1.push_back(H[vec[0]]);
	G1.push_back(H[vec[1]]);
	for (int i = 2; i < (int)vec.size(); i++) {
		while (G1.size() >= 2) {
			Point H1 = G1[G1.size() - 2];
			Point H2 = G1[G1.size() - 1];
			if (crs(H1 - H[vec[i]], H2 - H[vec[i]]) < ZERO) break;
			else G1.pop_back();
		}
		G1.push_back(H[vec[i]]);
	}
	
	vector<Point> G2;
	G2.push_back(H[vec[0]]);
	G2.push_back(H[vec[1]]);
	for (int i = 2; i < (int)vec.size(); i++) {
		while (G2.size() >= 2) {
			Point H1 = G2[G2.size() - 2];
			Point H2 = G2[G2.size() - 1];
			if (crs(H1 - H[vec[i]], H2 - H[vec[i]]) > ZERO) break;
			else G2.pop_back();
		}
		G2.push_back(H[vec[i]]);
	}
	
	vector<Point> I = G1;
	for (int i = (int)G2.size() - 2; i >= 1; i--) I.push_back(G2[i]);
	
	int cnt1 = 0, cnt2 = 0, cnt3 = 0;
	for (int i = 0; i < (int)I.size(); i++) {
		int n1 = i;
		int n2 = (i + 1) % I.size();
		Fraction I2 = crs(I[n1] - BASE, I[n2] - BASE);
		if (I2 > ZERO) cnt1 += 1;
		if (I2 < ZERO) cnt2 += 1;
		if (I2 == ZERO) cnt3 += 1;
	}
	if ((cnt1 == 0 || cnt2 == 0) && cnt3 == 0) return true;
	return false;
}

int main() {
	// Step #1. Input
	cin >> SX >> SY >> SZ;
	cin >> Q;
	for (int i = 1; i <= Q; i++) {
		cin >> C[i];
		if (C[i] == 'A') {
			cin >> D1[i] >> D2[i] >> D3[i];
			Fraction V1 = seikika(Fraction{D1[i], D1[i] + D2[i] + D3[i]});
			Fraction V2 = seikika(Fraction{D2[i], D1[i] + D2[i] + D3[i]});
			G.push_back(make_pair(Point{V1, V2}, N));
			N += 1;
		}
		if (C[i] == 'R') {
			cin >> D1[i];
			D1[i] -= 1;
		}
	}
	sort(G.begin(), G.end());
	
	// Step #2. Index
	int cnts = 0;
	for (int i = 0; i < N; i++) idx[G[i].second] = i;
	for (int i = 1; i <= Q; i++) {
		if (C[i] == 'A') { DD[i] = idx[cnts]; cnts += 1; }
		if (C[i] == 'R') { D1[i] = idx[D1[i]]; }
	}
	for (int i = 0; i < N; i++) H[i] = G[i].first;
	
	// Step #3. Maeshori
	BASE.px = seikika(Fraction{SX, SX + SY + SZ});
	BASE.py = seikika(Fraction{SY, SX + SY + SZ});
	for (int i = 0; i < N; i++) {
		if (BASE == H[i]) { r1[i] = true; }
	}
	for (int i = 0; i < N; i++) HH[i] = (H[i] - BASE);
	for (int i = 0; i < N; i++) {
		for (int j = i + 1; j < N; j++) {
			if (crs(HH[i], HH[j]) == ZERO && dot(HH[i], HH[j]) < ZERO) { r2[i][j] = true; }
		}
	}
	
	// Step #4. Answer Query
	for (int i = 1; i <= Q; i++) {
		if (C[i] == 'A') {
			used[DD[i]] = true;
			for (int j = 0; j < N; j++) {
				if (used[j] == true && (r2[DD[i]][j] == true || r2[j][DD[i]] == true)) cntw++;
			}
		}
		if (C[i] == 'R') {
			used[D1[i]] = false;
			for (int j = 0; j < N; j++) {
				if (used[j] == true && (r2[D1[i]][j] == true || r2[j][D1[i]] == true)) cntw--;
			}
		}
		if (solve1() == true) cout << "1" << endl;
		else if (solve2() == true) cout << "2" << endl;
		else if (solve3() == true) cout << "3" << endl;
		else cout << "0" << endl;
	}
	return 0;
}

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