QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#241550#6570. Who Watches the Watchmen?MovingUpWA 1140ms9112kbC++146.9kb2023-11-06 11:07:572023-11-06 11:07:58

Judging History

你现在查看的是最新测评结果

  • [2023-11-06 11:07:58]
  • 评测
  • 测评结果:WA
  • 用时:1140ms
  • 内存:9112kb
  • [2023-11-06 11:07:57]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
const int maxn = 2e5 + 10;
const int mod = 1e9 + 7;

int sgn(ll a) {
	return (a > 0) - (a < 0);
}
struct point {
	ll x, y, z;
	point() {}
	point(ll a, ll b, ll c) {
		x = a, y = b, z = c;
	}
	point operator+(point o) {
		return {x + o.x, y + o.y, z + o.z};
	}
	point operator-(point o) {
		return {x - o.x, y - o.y, z - o.z};
	}
	point operator*(ll d) {
		return {x * d, y * d, z * d};
	}
	ll lensq() {
		return x * x + y * y + z * z;
	}
};

point cross(point a, point b) {
	return {
		a.y * b.z - a.z * b.y,
		a.z * b.x - a.x * b.z,
		a.x * b.y - a.y * b.x
	};
}

bool is_zero(point p) {
	return !p.x && !p.y && !p.z;
}

bool collinear(point a, point b) {
	point p = cross(a, b);
	return is_zero(p);
}

bool collinear(point a, point b, point c, point d) {
	return collinear(b - a, d - c);
}

bool same_direction(point a, point b) {
	return sgn(a.x) == sgn(b.x) && sgn(a.y) == sgn(b.y) && sgn(a.z) == sgn(b.z);
}

bool correct_orientation(point a, point dir, point b) {
	point vec_ab = b - a;
	return collinear(vec_ab, dir) && same_direction(vec_ab, dir);
}

bool intersect(point a, point dir_a, point b, point dir_b) {
	point X = cross(dir_a, dir_b);
	point Y = cross(b - a, dir_b);

	if (is_zero(X)) {
		return false;
	}

	if (!collinear(X, Y)) {
		return false;
	}

	if (sgn(X.x) != sgn(Y.x) || sgn(X.y) != sgn(Y.y) || sgn(X.z) != sgn(Y.z)) {
		return false;
	}

	return true;
}

const ll inf = LLONG_MAX;
struct minimum_cost_bipartite_matching {
	int nl, nr;
	ll mc = 0;
	vector<int>ml, mr, ly;
	minimum_cost_bipartite_matching(int nl, int nr, vector<vector<ll>> &c) : 
		nl(nl), nr(nr), ml(nl, -1), mr(nr, -1), ly(nr) {
		vector<ll> s(nl), t(nr);
		for (int i = 0; i < nl; i++) {
			int x = i, y = -1;
			vector<bool> u(nr);
			vector<ll> md(nr, inf);
			while (x != -1) {
				ll ny = -1, d = inf;
				for (int j = 0; j < nr; j++)
					if (!u[j]) {
						ll v = c[x][j] - s[x] - t[j];
						if (v < md[j])
							md[j] = v, ly[j] = y;
						if (md[j] < d)
							d = md[j], ny = j;
					} 
				s[i] += d; mc += d;
				for (int j = 0; j < nr; j++)
					if (u[j])
						s[mr[j]] += d, t[j] -= d;
					else
						md[j] -= d;
				y = ny; u[y] = true; x = mr[y];
			}
			while (y != -1) {
				mr[y] = ly[y] != -1 ? mr[ly[y]] : i; ml[mr[y]] = y;
				y = ly[y];
			}
		}
	}
};

int main()
{
	ios_base::sync_with_stdio(false), cin.tie(0);
	int n;
	cin >> n;
	if (n == 1) {
		cout << "-1\n";
		return 0;
	}
	vector<pair<point, point>> v;
	for (int i = 0; i < n; i++) {
		point p;
		cin >> p.x >> p.y >> p.z;
		point dir;
		cin >> dir.x >> dir.y >> dir.z;
		v.push_back({p, dir});
	}

	vector<vector<ll>> edges(n, vector<ll>(n));
	for (int i = 0; i < n; i++) {
		vector<bool> reachable(n, true);
		for (int j = 0; j < n; j++) {
			if (i == j) {
				continue;
			}
			point vec_ij = v[j].first - v[i].first;
			for (int k = 0; k < n; k++) {
				if (i == k || j == k) {
					continue;
				}

				point vec_ik = v[k].first - v[i].first;
				if (collinear(vec_ij, vec_ik)) {
					if (vec_ij.lensq() < vec_ik.lensq()) {
						reachable[k] = false;
					}
				}
			}
		}

		for (int j = 0; j < n; j++) {
			if (i == j || !reachable[j]) {
				edges[i][j] = mod;
				continue;
			}

			if (correct_orientation(v[i].first, v[i].second, v[j].first)) {
				edges[i][j] = 0;
			} else {
				edges[i][j] = 1;
			}
 		}
	}

	minimum_cost_bipartite_matching matching(n, n, edges);
	if (matching.mc < mod) {
		cout << matching.mc << "\n";
		return 0;
	}

	assert(n % 2 == 1);

	sort(v.begin(), v.end(), [](pair<point, point> A, pair<point, point> B) {
		if (A.first.x != B.first.x) {
			return A.first.x < B.first.x;
		}
		if (A.first.y != B.first.y) {
			return A.first.y < B.first.y;
		}
		return A.first.z < B.first.z; 
	});

	vector<ll> pref_cost(n, mod), suf_cost(n, mod);
	for (int i = 1; i < n; i += 2) {
		int cost = 0;
		if ((i - 1) % 2 == 0) {
			if (!correct_orientation(v[i - 1].first, v[i - 1].second, v[i].first)) {
				cost++;
			}
			if (!correct_orientation(v[i].first, v[i].second, v[i - 1].first)) {
				cost++;
			}
		} else {
			if (i + 2 >= n) {
				continue;
			}
			if (!correct_orientation(v[i + 2].first, v[i + 2].second, v[i].first)) {
				cost++;
			}
			if (!correct_orientation(v[i].first, v[i].second, v[i + 2].first)) {
				cost++;
			}
		}

		pref_cost[i] = cost;
		if (i - 2 >= 0) {
			pref_cost[i] += pref_cost[i - 2];
		}
	}

	for (int i = n - 2; i >= 0; i--) {
		int cost = 0;
		if ((n - 2 - i) % 2 == 0) {
			if (!correct_orientation(v[i + 1].first, v[i + 1].second, v[i].first)) {
				cost++;
			}
			if (!correct_orientation(v[i].first, v[i].second, v[i + 1].first)) {
				cost++;
			}
		} else {
			if (i - 2 < 0) {
				continue;
			}
			if (!correct_orientation(v[i - 2].first, v[i - 2].second, v[i].first)) {
				cost++;
			}
			if (!correct_orientation(v[i].first, v[i].second, v[i - 2].first)) {
				cost++;
			}
		}

		suf_cost[i] = cost;
		if (i + 2 < n) {
			suf_cost[i] += suf_cost[i + 2];
		}
	}

	vector<vector<ll>> right_cost(n, vector<ll>(n, mod)), left_cost(n, vector<ll>(n, mod));
	for (int i = 0; i < n; i++) {
		right_cost[i][i] = left_cost[i][i] = 0;
		ll cur_costR = 0, cur_costL = 0;
		for (int j = i + 1; j < n; j++) {
			if (!correct_orientation(v[j - 1].first, v[j - 1].second, v[j].first)) {
				cur_costR++;
			}
			if (!correct_orientation(v[j].first, v[j].second, v[j - 1].first)) {
				cur_costL++;
			}
			right_cost[i][j] = cur_costR;
			left_cost[i][j] = cur_costL;
		}
	}

	ll answer = LLONG_MAX;
	for (int i = 0; i < n; i++) {
		// will move i
		for (int a = 0; a < n; a++) {
			// a will point to i
			if (a == i) {
				continue;
			}
			point vec_a = v[a].first;
			for (int b = 0; b < n; b++) {
				// i will point to b
				if (a == b || b == i) {
					continue;
				}

				point vec_b = v[i].second * (-1);
				ll cand = 0;
				int L = min(a, b) - 1;
				if (L == i) {
					L--;
				}

				if (L > 0) {
					cand += pref_cost[min(a, b) - 1];
				}

				int R = max(a, b) + 1;
				if (R == i) {
					R++;
				}

				if (R < n - 1) {
					cand += suf_cost[max(a, b) + 1];
				}
				if (a < b) {
					cand += left_cost[a][b];
				} else {
					cand += right_cost[b][a];
				}

				if (collinear(v[a].second, v[a].first - v[i].first)) {
					if (!collinear(v[i].second, v[a].first - v[i].first)) {
						cand++;
					} else {
						cand += 2;
					}
				} else {
					if (!collinear(v[i].second, v[a].first - v[i].first)) {
						if (!intersect(v[a].first, v[a].second, v[b].first, vec_b))  {
							cand++;
						}
					} else {
						cand++;
					}
				}
				cand += 1000;

				answer = min(answer, cand);
			}
		}
	}


	cout << answer << "\n";
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3652kb

input:

7
0 0 0 1 0 0
1 0 0 -1 0 0
2 0 0 1 0 0
3 0 0 1 0 0
4 0 0 1 0 0
5 0 0 1 0 0
6 0 0 -1 0 0

output:

1002

result:

ok single line: '1002'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3620kb

input:

4
66 45 10 73 39 36
95 14 26 47 84 59
14 66 89 89 36 78
16 27 94 79 24 24

output:

4

result:

ok single line: '4'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3560kb

input:

3
0 0 0 1 0 0
1 1 1 1 0 0
2 2 2 1 0 0

output:

1002

result:

ok single line: '1002'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3848kb

input:

3
0 0 0 1 1 1
1 1 1 1 0 0
2 2 2 1 0 0

output:

1001

result:

ok single line: '1001'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3628kb

input:

3
0 0 0 1 0 0
1 1 1 1 0 0
2 2 2 -1 -1 -1

output:

1001

result:

ok single line: '1001'

Test #6:

score: 0
Accepted
time: 0ms
memory: 3824kb

input:

3
0 0 0 1 0 0
1 1 1 1 2 2
2 2 2 -1 -1 -1

output:

1000

result:

ok single line: '1000'

Test #7:

score: 0
Accepted
time: 0ms
memory: 3576kb

input:

3
0 0 0 1 0 0
1 1 1 1 2 2
2 2 2 1 1 1

output:

1001

result:

ok single line: '1001'

Test #8:

score: 0
Accepted
time: 0ms
memory: 3544kb

input:

1
0 0 0 3 1 4

output:

-1

result:

ok single line: '-1'

Test #9:

score: 0
Accepted
time: 0ms
memory: 3564kb

input:

4
0 0 0 1 1 1
1 0 0 -1 0 0
1 1 1 0 -1 0
1 0 1 0 1 0

output:

1

result:

ok single line: '1'

Test #10:

score: 0
Accepted
time: 369ms
memory: 5236kb

input:

500
0 0 0 1 0 0
1 0 0 1 0 0
2 0 0 -1 0 0
3 0 0 1 0 0
4 0 0 1 0 0
5 0 0 1 0 0
6 0 0 1 0 0
7 0 0 1 0 0
8 0 0 1 0 0
9 0 0 1 0 0
10 0 0 -1 0 0
11 0 0 -1 0 0
12 0 0 1 0 0
13 0 0 -1 0 0
14 0 0 1 0 0
15 0 0 1 0 0
16 0 0 1 0 0
17 0 0 -1 0 0
18 0 0 -1 0 0
19 0 0 -1 0 0
20 0 0 -1 0 0
21 0 0 1 0 0
22 0 0 1 0 0...

output:

250

result:

ok single line: '250'

Test #11:

score: 0
Accepted
time: 361ms
memory: 5276kb

input:

500
0 0 0 0 1 0
0 1 0 0 1 0
0 2 0 0 -1 0
0 3 0 0 1 0
0 4 0 0 1 0
0 5 0 0 1 0
0 6 0 0 1 0
0 7 0 0 1 0
0 8 0 0 1 0
0 9 0 0 1 0
0 10 0 0 -1 0
0 11 0 0 -1 0
0 12 0 0 1 0
0 13 0 0 -1 0
0 14 0 0 1 0
0 15 0 0 1 0
0 16 0 0 1 0
0 17 0 0 -1 0
0 18 0 0 -1 0
0 19 0 0 -1 0
0 20 0 0 -1 0
0 21 0 0 1 0
0 22 0 0 1 0...

output:

250

result:

ok single line: '250'

Test #12:

score: 0
Accepted
time: 365ms
memory: 5152kb

input:

500
0 0 0 0 0 1
0 0 1 0 0 1
0 0 2 0 0 -1
0 0 3 0 0 1
0 0 4 0 0 1
0 0 5 0 0 1
0 0 6 0 0 1
0 0 7 0 0 1
0 0 8 0 0 1
0 0 9 0 0 1
0 0 10 0 0 -1
0 0 11 0 0 -1
0 0 12 0 0 1
0 0 13 0 0 -1
0 0 14 0 0 1
0 0 15 0 0 1
0 0 16 0 0 1
0 0 17 0 0 -1
0 0 18 0 0 -1
0 0 19 0 0 -1
0 0 20 0 0 -1
0 0 21 0 0 1
0 0 22 0 0 1...

output:

250

result:

ok single line: '250'

Test #13:

score: 0
Accepted
time: 0ms
memory: 3784kb

input:

5
1 0 0 1 -1 0
2 0 0 0 1 0
3 0 0 -1 0 0
4 0 0 -1 0 0
5 0 0 -1 0 0

output:

1000

result:

ok single line: '1000'

Test #14:

score: 0
Accepted
time: 0ms
memory: 3628kb

input:

5
1 0 0 1 0 0
2 0 0 1 0 0
3 0 0 1 0 0
4 0 0 0 1 0
5 0 0 -1 -1 0

output:

1000

result:

ok single line: '1000'

Test #15:

score: 0
Accepted
time: 0ms
memory: 3828kb

input:

6
0 1 0 1 0 0
0 2 0 0 2 0
0 3 0 0 3 0
0 4 0 0 4 0
0 5 0 0 5 0
0 6 0 0 6 0

output:

4

result:

ok single line: '4'

Test #16:

score: 0
Accepted
time: 0ms
memory: 3836kb

input:

9
1 0 0 1 0 0
2 0 0 1 0 0
3 0 0 1 0 0
0 1 0 0 1 0
0 2 0 0 1 0
0 3 0 0 1 0
0 0 1 0 0 1
0 0 2 0 0 1
0 0 3 0 0 1

output:

3

result:

ok single line: '3'

Test #17:

score: -100
Wrong Answer
time: 1140ms
memory: 9112kb

input:

499
0 0 0 1 0 0
1 0 0 1 0 0
2 0 0 -1 0 0
3 0 0 1 0 0
4 0 0 1 0 0
5 0 0 1 0 0
6 0 0 1 0 0
7 0 0 1 0 0
8 0 0 1 0 0
9 0 0 1 0 0
10 0 0 -1 0 0
11 0 0 -1 0 0
12 0 0 1 0 0
13 0 0 -1 0 0
14 0 0 1 0 0
15 0 0 1 0 0
16 0 0 1 0 0
17 0 0 -1 0 0
18 0 0 -1 0 0
19 0 0 -1 0 0
20 0 0 -1 0 0
21 0 0 1 0 0
22 0 0 1 0 0...

output:

1234

result:

wrong answer 1st lines differ - expected: '1220', found: '1234'