QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#138473#6570. Who Watches the Watchmen?hulahula3247WA 221ms5528kbC++178.1kb2023-08-11 19:52:362023-08-11 19:52:53

Judging History

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

  • [2023-08-11 19:52:53]
  • 评测
  • 测评结果:WA
  • 用时:221ms
  • 内存:5528kb
  • [2023-08-11 19:52:36]
  • 提交

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'