QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#138473 | #6570. Who Watches the Watchmen? | hulahula3247 | WA | 221ms | 5528kb | C++17 | 8.1kb | 2023-08-11 19:52:36 | 2023-08-11 19:52:53 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
#define all(v) v.begin(), v.end()
const ll INF = 1e18;
const ll M = 501;
ll N, mat[M][M];
ll hungarian(ll n, ll m, vector<ll> &ret) {
vector<ll> u(n + 1), v(m + 1), p(m + 1), way(m + 1), minv(m + 1), used(m + 1);
for (ll i = 1; i <= n; i++) {
p[0] = i;
ll j0 = 0;
fill(all(minv), INF);
fill(all(used), 0);
do {
used[j0] = 1;
ll i0 = p[j0], j1;
ll delta = INF;
for (ll j = 1; j <= m; j++) {
if (!used[j]) {
ll cur = mat[i0][j] - u[i0] - v[j];
if (cur < minv[j]) minv[j] = cur, way[j] = j0;
if (minv[j] < delta) delta = minv[j], j1 = j;
}
}
for (ll j = 0; j <= m; j++) {
if (used[j]) u[p[j]] += delta, v[j] -= delta;
else minv[j] -= delta;
}
j0 = j1;
} while (p[j0] != 0);
do {
ll j1 = way[j0];
p[j0] = p[j1];
j0 = j1;
} while (j0);
}
ret.clear(); ret.resize(n+1);
for (ll j = 1; j <= m; j++) ret[p[j]] = j;
return -v[0];
}
struct Sentry {
ll x, y, z, vx, vy, vz;
bool operator<(const Sentry &rhs) const {
if (x != rhs.x) return x < rhs.x;
if (y != rhs.y) return y < rhs.y;
return z < rhs.z;
}
};
vector<Sentry> s;
bool check(ll a1, ll b1, ll c1, ll a2, ll b2, ll c2) {
if (a1*b2 != b1*a2) return false;
if (b1*c2 != c1*b2) return false;
if (c1*a2 != a1*c2) return false;
return true;
}
bool co_linear() {
if (N%2 == 0) return false;
ll dx = s[1].x - s[0].x;
ll dy = s[1].y - s[0].y;
ll dz = s[1].z - s[0].z;
for (ll i = 2; i < N; i++) {
ll nx = s[i].x - s[0].x;
ll ny = s[i].y - s[0].y;
ll nz = s[i].z - s[0].z;
if (!check(dx, dy, dz, nx, ny, nz)) return false;
}
return true;
}
bool can_see(ll i, ll j) {
if (s[i].vx != 0) {
if ((s[j].x-s[i].x)*s[i].vx <= 0) return 0;
}
else if (s[i].vy != 0) {
if ((s[j].y-s[i].y)*s[i].vy <= 0) return 0;
}
else {
if ((s[j].z-s[i].z)*s[i].vz <= 0) return 0;
}
ll dx = s[j].x-s[i].x;
ll dy = s[j].y-s[i].y;
ll dz = s[j].z-s[i].z;
if (!check(s[i].vx, s[i].vy, s[i].vz, dx, dy, dz)) return 0;
return 1;
}
ll dis(ll i, ll j) {
if (i == j) return ll(1e9);
for (ll k = 0; k < N; k++) {
if (i == k || j == k) continue;
ll dx1 = s[k].x-s[i].x, dx2 = s[k].x-s[j].x;
ll dy1 = s[k].y-s[i].y, dy2 = s[k].y-s[j].y;
ll dz1 = s[k].z-s[i].z, dz2 = s[k].z-s[j].z;
if (s[i].x != s[j].x) {
if ((dx1*dx2 < 0) && check(dx1, dy1, dz1, dx2, dy2, dz2)) return 1000;
}
else if (s[i].x != s[j].x) {
if ((dy1*dy2 < 0) && check(dx1, dy1, dz1, dx2, dy2, dz2)) return 1000;
}
else {
if ((dz1*dz2 < 0) && check(dx1, dy1, dz1, dx2, dy2, dz2)) return 1000;
}
}
if (can_see(i, j)) return 0;
else return 1;
}
struct Prefix {
ll lps[M], rps[M], lss[M], rss[M];
ll lp[M], rp[M], ls[M], rs[M];
void init() {
for (ll i = 0; i < N; i += 2) {
if (!can_see(i, i+1)) lps[i]++;
if (!can_see(i+1, i)) lps[i+1]++;
}
for (ll i = 1; i < N; i += 2) {
if (!can_see(i, i+1)) rps[i]++;
if (!can_see(i+1, i)) rps[i+1]++;
}
for (ll i = 0; i < N-1; i++) {
if (!can_see(i, i+1)) rss[i]++;
}
for (ll i = 0; i < N-1; i++) {
if (!can_see(i+1, i)) lss[i+1]++;
}
for (ll i = 0; i < N; i++) {
lp[i+1] = lp[i]+lps[i];
rp[i+1] = rp[i]+rps[i];
ls[i+1] = ls[i]+lss[i];
rs[i+1] = rs[i]+rss[i];
}
}
void out() {
for (int i = 0; i <= N; i++) cout << lp[i] << ' ';
cout << '\n';
for (int i = 0; i <= N; i++) cout << rp[i] << ' ';
cout << '\n';
for (int i = 0; i <= N; i++) cout << ls[i] << ' ';
cout << '\n';
for (int i = 0; i <= N; i++) cout << rs[i] << ' ';
cout << '\n';
for (int i = 0; i < N; i++) cout << lss[i] << ' ';
cout << '\n';
for (int i = 0; i < N-1; i++) cout << can_see(i, i+1) << ' ';
}
}pf;
ll lx, ly, lz;
ll not_coplane(ll d, ll a, ll b) {
if (check(s[a].vx, s[a].vy, s[a].vz, s[b].vx, s[b].vy, s[b].vz)) return 1;
if (s[a].vx*s[b].vy - s[a].vy*s[b].vx != 0) {
ll k = s[a].vx*s[b].vy - s[a].vy*s[b].vx;
ll A = d*(s[b].vy*lx-s[b].vx*ly);
ll B = d*(s[a].vx*ly-s[a].vy*lx);
if (k*A < 0 || k*B < 0) return 1;
if (s[a].vz*A + s[b].vz*B != lz*d*k) return 1;
return 0;
}
if (s[a].vy*s[b].vz - s[a].vz*s[b].vy != 0) {
ll k = s[a].vy*s[b].vz - s[a].vz*s[b].vy;
ll A = d*(s[b].vz*ly-s[b].vy*lz);
ll B = d*(s[a].vy*lz-s[a].vz*ly);
if (k*A < 0 || k*B < 0) return 1;
if (s[a].vx*A + s[b].vx*B != lx*d*k) return 1;
return 0;
}
if (s[a].vz*s[b].vx - s[a].vx*s[b].vz != 0) {
ll k = s[a].vz*s[b].vx - s[a].vx*s[b].vz;
ll A = d*(s[b].vx*lz-s[b].vz*lx);
ll B = d*(s[a].vz*lx-s[a].vx*lz);
if (k*A < 0 || k*B < 0) return 1;
if (s[a].vy*A + s[b].vy*B != ly*d*k) return 1;
return 0;
}
return 1;
}
void solve() {
cin >> N;
if (N == 1) cout << -1, exit(0);
s.resize(N);
for (ll i = 0; i < N; i++) {
ll x, y, z, vx, vy, vz;
cin >> x >> y >> z >> vx >> vy >> vz;
s[i] = {x, y, z, vx, vy, vz};
}
if (co_linear()) {
sort(all(s));
pf.init();
lx = s[1].x - s[0].x;
ly = s[1].y - s[0].y;
lz = s[1].z - s[0].z;
ll ans = INF;
for (ll i = 0; i < N; i++) {
for (ll j = 0; j < N; j++) {
for (ll k = j+1; k < N; k++) {
if (j == i || i == k) continue;
if (j < i && i < k) {
if (j%2 == 1 || (N-k)%2 == 0) continue;
ll cur = pf.lp[j] + pf.rp[N] - pf.rp[k+1];
if (cur >= ans) continue;
ll cnt = 0, c1 = 0, c2 = 0;
if (check(lx, ly, lz, s[j].vx, s[j].vy, s[j].vz)) cnt++;
if (check(lx, ly, lz, s[i].vx, s[i].vy, s[i].vz)) cnt++;
if (cnt) c1 += cnt;
else c1 += not_coplane(1, j, i);
c1 += pf.ls[k+1] - pf.ls[j+1] - pf.lss[i];
ans = min(ans, cur+c1);
cnt = 0;
if (check(lx, ly, lz, s[k].vx, s[k].vy, s[k].vz)) cnt++;
if (check(lx, ly, lz, s[i].vx, s[i].vy, s[i].vz)) cnt++;
if (cnt) c2 += cnt;
else c2 += not_coplane(-1, k, i);
c2 += pf.rs[k] - pf.rs[j] - pf.rss[i];
ans = min(ans, cur+c2);
}
else if (i < j) {
if (j%2 == 0 || (N-k)%2 == 0) continue;
ll cur = pf.lp[i] + pf.rp[j] - pf.rp[i+1] + pf.rp[N] - pf.rp[k+1];
if (cur >= ans) continue;
ll cnt = 0, c1 = 0, c2 = 0;
if (check(lx, ly, lz, s[j].vx, s[j].vy, s[j].vz)) cnt++;
if (check(lx, ly, lz, s[i].vx, s[i].vy, s[i].vz)) cnt++;
if (cnt) c1 += cnt;
else c1 += not_coplane(1, j, i);
c1 += pf.ls[k+1] - pf.ls[j+1];
ans = min(ans, cur+c1);
cnt = 0;
if (check(lx, ly, lz, s[k].vx, s[k].vy, s[k].vz)) cnt++;
if (check(lx, ly, lz, s[i].vx, s[i].vy, s[i].vz)) cnt++;
if (cnt) c2 += cnt;
else c2 += not_coplane(-1, k, i);
c2 += pf.rs[k] - pf.rs[j];
ans = min(ans, cur+c2);
}
else {
if (j%2 == 1 || (N-k)%2 == 1) continue;
ll cur = pf.lp[j] + pf.lp[i] - pf.lp[k+1] + pf.rp[N] - pf.rp[i+1];
if (cur >= ans) continue;
ll cnt = 0, c1 = 0, c2 = 0;
if (check(lx, ly, lz, s[j].vx, s[j].vy, s[j].vz)) cnt++;
if (check(lx, ly, lz, s[i].vx, s[i].vy, s[i].vz)) cnt++;
if (cnt) c1 += cnt;
else c1 += not_coplane(1, j, i);
c1 += pf.ls[k+1] - pf.ls[j+1];
ans = min(ans, cur+c1);
cnt = 0;
if (check(lx, ly, lz, s[k].vx, s[k].vy, s[k].vz)) cnt++;
if (check(lx, ly, lz, s[i].vx, s[i].vy, s[i].vz)) cnt++;
if (cnt) c2 += cnt;
else c2 += not_coplane(-1, k, i);
c2 += pf.rs[k] - pf.rs[j];
ans = min(ans, cur+c2);
}
}
}
}
cout << ans+1000 << '\n';
//pf.out();
}
else {
for (ll i = 0; i < N; i++) {
for (ll j = 0; j < N; j++) {
mat[i+1][j+1] = dis(i, j);
}
}
vector<ll> ret;
ll ans = hungarian(N, N, ret);
cout << ans;
}
}
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
ll T = 1;
//cin >> T;
while (T--) solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3496kb
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: 3616kb
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: 3464kb
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: 3560kb
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: 1ms
memory: 3624kb
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: 3612kb
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: 1ms
memory: 3624kb
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: 3596kb
input:
1 0 0 0 3 1 4
output:
-1
result:
ok single line: '-1'
Test #9:
score: 0
Accepted
time: 1ms
memory: 3560kb
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: 65ms
memory: 5508kb
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: -100
Wrong Answer
time: 221ms
memory: 5528kb
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:
0
result:
wrong answer 1st lines differ - expected: '250', found: '0'