oj.uz

Submission #299492

# Submission time Handle Problem Language Result Execution time Memory
299492 2020-09-15T04:16:06 Z E869120 Mixture (BOI20_mixture) C++14
0 / 100
 2 ms 640 KB 
#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 = {0LL, 1001LL, 8691LL};
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;
	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
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 640 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Correct 1 ms 416 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 512 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 1 ms 512 KB Output is correct
15 Correct 2 ms 512 KB Output is correct
16 Incorrect 2 ms 384 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 640 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Correct 1 ms 416 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 512 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 1 ms 512 KB Output is correct
15 Correct 2 ms 512 KB Output is correct
16 Incorrect 2 ms 384 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 640 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Correct 1 ms 416 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 512 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 1 ms 512 KB Output is correct
15 Correct 2 ms 512 KB Output is correct
16 Incorrect 2 ms 384 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 640 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Correct 1 ms 416 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 512 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 1 ms 512 KB Output is correct
15 Correct 2 ms 512 KB Output is correct
16 Incorrect 2 ms 384 KB Output isn't correct
17 Halted 0 ms 0 KB -