QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#241913 | #6570. Who Watches the Watchmen? | MovingUp | WA | 1651ms | 9172kb | C++14 | 7.0kb | 2023-11-06 19:31:01 | 2023-11-06 19:31:01 |
Judging History
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'