#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;
}
// Input
Point G;
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) r2[i][j] = true;
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;
int u1 = hantei(H[i], H[j], G); if (u1 == 1) cnt1 += 1; if (u1 == -1) cnt2 += 1;
int u2 = hantei(H[j], H[k], G); if (u2 == 1) cnt1 += 1; if (u2 == -1) cnt2 += 1;
int u3 = hantei(H[k], H[i], G); if (u3 == 1) cnt1 += 1; if (u3 == -1) cnt2 += 1;
if (cnt1 == 0 || cnt2 == 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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
