QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#241913#6570. Who Watches the Watchmen?MovingUpWA 1651ms9172kbC++147.0kb2023-11-06 19:31:012023-11-06 19:31:01

Judging History

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

  • [2023-11-06 19:31:01]
  • 评测
  • 测评结果:WA
  • 用时:1651ms
  • 内存:9172kb
  • [2023-11-06 19:31:01]
  • 提交

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;
	}
	bool operator==(point o) {
		return x == o.x && y == o.y && z == o.z;
	}
	bool operator!=(point o) {
		return !(*this == o);
	}
};

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;
	}

	X = cross(dir_b, dir_a);
	Y = cross(a - b, dir_a);

	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; 
	});

	ll answer = LLONG_MAX;
	for (int i = 0; i < n; i++) {
		vector<pair<point, point>> cur_v;
		for (auto p : v) {
			if (p.first != v[i].first) {
				cur_v.push_back(p);
			}
		}
		vector<ll> pref_cost(cur_v.size(), mod), suf_cost(cur_v.size(), mod);
		for (int j = 1; j < cur_v.size(); j += 2) {
			int cost = 0;
			if (!correct_orientation(cur_v[j - 1].first, cur_v[j - 1].second, cur_v[j].first)) {
				cost++;
			}
			if (!correct_orientation(cur_v[j].first, cur_v[j].second, cur_v[j - 1].first)) {
				cost++;
			}

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

		for (int j = cur_v.size() - 2; j >= 0; j -= 2) {
			int cost = 0;
			if (!correct_orientation(cur_v[j + 1].first, cur_v[j + 1].second, cur_v[j].first)) {
				cost++;
			}
			if (!correct_orientation(cur_v[j].first, cur_v[j].second, cur_v[j + 1].first)) {
				cost++;
			}

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

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

		// will move i
		for (int a = 0; a < cur_v.size(); a++) {
			// a will point to i
			point vec_a = cur_v[a].first;
			for (int b = 0; b < cur_v.size(); b++) {
				// i will point to b
				if (a == b) {
					continue;
				}

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

				int R = max(a, b) + 1;
				if (R < cur_v.size()) {
					cand += suf_cost[R];
				}

				if (a < b) {
					cand += left_cost[a][b];
				} else {
					cand += right_cost[b][a];
				}

				if (collinear(cur_v[a].second, cur_v[a].first - v[i].first)) {
					if (!collinear(v[i].second, cur_v[a].first - v[i].first)) {
						cand++;
					} else {
						cand += 2;
					}
				} else {
					if (!collinear(v[i].second, cur_v[a].first - v[i].first)) {
						if (!intersect(cur_v[a].first, cur_v[a].second, cur_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: 1ms
memory: 3440kb

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: 3484kb

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: 1ms
memory: 3488kb

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: 1ms
memory: 3500kb

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: 3412kb

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: 1ms
memory: 3428kb

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: 3432kb

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: 1ms
memory: 3436kb

input:

1
0 0 0 3 1 4

output:

-1

result:

ok single line: '-1'

Test #9:

score: 0
Accepted
time: 1ms
memory: 3436kb

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: 363ms
memory: 5188kb

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: 366ms
memory: 5132kb

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: 371ms
memory: 5084kb

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: 1ms
memory: 3484kb

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: 3416kb

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: 3444kb

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: 1ms
memory: 3468kb

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: 1651ms
memory: 9172kb

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:

1227

result:

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