QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#241527#6570. Who Watches the Watchmen?MovingUpWA 1ms3400kbC++145.8kb2023-11-06 10:34:482023-11-06 10:34:48

Judging History

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

  • [2023-11-06 10:34:48]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3400kb
  • [2023-11-06 10:34:48]
  • 提交

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

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;
	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.x < vec_ik.x) {
						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 (!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++;
		}

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

	for (int i = n - 2; i >= 0; i -= 2) {
		int cost = 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++;
		}

		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 (b == i) {
					continue;
				}

				point vec_b = v[i].second * (-1);
				ll cand = 0;
				if (min(a, b) > 0) {
					cand += pref_cost[min(a, b) - 1];
				}
				if (max(a, b) < n - 1) {
					cand += suf_cost[max(a, b) + 1];
				}
				if (a < b) {
					cand += left_cost[a][b];
				} else {
					cand += right_cost[b][a];
				}

				if (!intersect(v[a].first, v[a].second, v[b].first, vec_b))  {
					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: 0
Wrong Answer
time: 1ms
memory: 3400kb

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:

1001

result:

wrong answer 1st lines differ - expected: '1002', found: '1001'