제출 #299496

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
299496		E869120	Mixture (BOI20_mixture)	C++14	30 / 100	1120 ms	49144 KiB

Mixture

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

struct Point {
	long long px, py, pz;
};

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

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

// Input
Point G;
Point GG = {10011LL, 86912LL, 123456LL};
long long Q;
char C[1 << 18];
long long D1[1 << 18], D2[1 << 18], D3[1 << 18];
long long DD[1 << 18];

// Points
long long N;
Point H[1 << 18];

// Tansaku
bool used[509];
bool dokuritsu[509][509];
bool r1[509];
bool r2[509][509];
bool r3[509][509][509];

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

int calc(Point v1, Point v2) {
	long long f1 = gcd(v1.px, gcd(v1.py, v1.pz));
	long long f2 = gcd(v2.px, gcd(v2.py, v2.pz));
	Point w1 = Point{v1.px / f1, v1.py / f1, v1.pz / f1};
	Point w2 = Point{v2.px / f2, v2.py / f2, v2.pz / f2};
	if (w1 == w2) return 1;
	return 0;
}

int hantei(Point v1, Point v2, Point v3) {
	long long u1 = v1.px * v2.py * v3.pz;
	long long u2 = v1.py * v2.pz * v3.px;
	long long u3 = v1.pz * v2.px * v3.py;
	long long u4 = v1.px * v2.pz * v3.py;
	long long u5 = v1.py * v2.px * v3.pz;
	long long u6 = v1.pz * v2.py * v3.px;
	long long uu = u1 + u2 + u3 - u4 - u5 - u6;
	if (uu > 0) return 1;
	if (uu == 0) return 0;
	return -1;
}

bool solve1() {
	vector<int> vec;
	for (int i = 1; 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() {
	vector<int> vec;
	for (int i = 1; i <= N; i++) { if (used[i] == true) vec.push_back(i); }
	for (int i = 0; i < (int)vec.size(); i++) {
		for (int j = i + 1; j < (int)vec.size(); j++) {
			if (r2[vec[i]][vec[j]] == true) { return true; }
		}
	}
	return false;
}

bool solve3() {
	vector<int> vec;
	for (int i = 1; i <= N; i++) { if (used[i] == true) vec.push_back(i); }
	for (int i = 0; i < (int)vec.size(); i++) {
		for (int j = i + 1; j < (int)vec.size(); j++) {
			for (int k = j + 1; k < (int)vec.size(); k++) {
				if (r3[vec[i]][vec[j]][vec[k]] == true) return true;
			}
		}
	}
	return false;
}

int main() {
	// Step #1. Input
	cin >> G.px >> G.py >> G.pz;
	cin >> Q;
	assert(G.px + G.py + G.pz <= 1000);
	for (int i = 1; i <= Q; i++) {
		cin >> C[i];
		if (C[i] == 'A') {
			cin >> D1[i] >> D2[i] >> D3[i];
			N += 1;
			DD[i] = N;
			H[N] = Point{D1[i], D2[i], D3[i]};
		}
		if (C[i] == 'R') {
			cin >> D1[i];
		}
	}
	
	// Step #2. Tansaku
	for (int i = 1; i <= N; i++) {
		if (calc(H[i], G) == 1) r1[i] = true;
		for (int j = 1; j <= N; j++) {
			if (calc(H[i], H[j]) == 0) dokuritsu[i][j] = true;
		}
	}
	for (int i = 1; i <= N; i++) {
		for (int j = i + 1; j <= N; j++) {
			if (dokuritsu[i][j] == false) continue;
			if (hantei(H[i], H[j], G) == 0) {
				int v1 = hantei(H[i] + GG, G + GG, GG);
				int v2 = hantei(H[j] + GG, G + GG, GG);
				if (v1 != v2) r2[i][j] = true;
				//cout << "#" << i << " " << j << " " << v1 << " " << v2 << endl;
			}
			for (int k = j + 1; k <= N; k++) {
				if (dokuritsu[j][k] == false) continue;
				if (dokuritsu[k][i] == false) continue;
				int cnt1 = 0, cnt2 = 0, cnt3 = 0;
				int u1 = hantei(H[i], H[j], G); if (u1 == 1) cnt1 += 1; if (u1 == -1) cnt2 += 1; if (u1 == 0) cnt3 += 1;
				int u2 = hantei(H[j], H[k], G); if (u2 == 1) cnt1 += 1; if (u2 == -1) cnt2 += 1; if (u2 == 0) cnt3 += 1;
				int u3 = hantei(H[k], H[i], G); if (u3 == 1) cnt1 += 1; if (u3 == -1) cnt2 += 1; if (u3 == 0) cnt3 += 1;
				if ((cnt1 == 0 || cnt2 == 0) && cnt3 == 0) r3[i][j][k] = true;
			}
		}
	}
	
	// Step #3. Answer Query
	for (int i = 1; i <= Q; i++) {
		if (C[i] == 'A') used[DD[i]] = true;
		if (C[i] == 'R') used[D1[i]] = false;
		bool f1 = solve1();
		bool f2 = solve2();
		bool f3 = solve3();
		if (f1 == true) cout << "1" << endl;
		else if (f2 == true) cout << "2" << endl;
		else if (f3 == true) cout << "3" << endl;
		else cout << "0" << endl;
	}
	return 0;
}

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