QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#338597 | #6570. Who Watches the Watchmen? | ckiseki | WA | 0ms | 4320kb | C++23 | 6.2kb | 2024-02-26 03:08:31 | 2024-02-26 03:08:32 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define all(x) begin(x), end(x)
#ifdef CKISEKI
#define safe cerr << __PRETTY_FUNCTION__ << " line " << __LINE__ << " safe\n"
#define debug(a...) debug_(#a, a)
#define orange(a...) orange_(#a, a)
#include <experimental/iterator>
void debug_(auto s, auto ...a) {
cerr << "\e[1;32m(" << s << ") = (";
int f = 0;
(..., (cerr << (f++ ? ", " : "") << a));
cerr << ")\e[0m\n";
}
void orange_(auto s, auto L, auto R) {
cerr << "\e[1;33m[ " << s << " ] = [ ";
using namespace experimental;
copy(L, R, make_ostream_joiner(cerr, ", "));
cerr << " ]\e[0m\n";
}
#else
#define safe ((void)0)
#define debug(...) safe
#define orange(...) safe
#endif
using lld = int64_t;
struct P3 {
lld x, y, z;
P3 operator+(const P3 &b) const {
return {x+b.x, y+b.y, z+b.z};
}
P3 operator-(const P3 &b) const {
return {x-b.x, y-b.y, z-b.z};
}
P3 operator-() const {
return {-x, -y, -z};
}
bool operator==(const P3 &b) const {
return x==b.x && y==b.y && z==b.z;
}
bool operator<(const P3 &b) const {
return x < b.x && y < b.y && z < b.z;
}
};
P3 reduced(const P3 &p) {
lld g = abs(gcd(gcd(p.x, p.y), p.z));
return {p.x / g, p.y / g, p.z / g};
}
lld dot(const P3 &a, const P3 &b) {
return a.x*b.x+a.y*b.y+a.z*b.z;
}
lld norm(const P3 &p) {
return dot(p, p);
}
P3 cross(const P3 &a, const P3 &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 same_dir(const P3 &a, const P3 &b) {
return cross(a, b) == P3(0, 0, 0) && dot(a, b) > 0;
}
struct Ray {
P3 s, dir;
Ray(P3 t_s, P3 t_dir) : s(t_s), dir(t_dir) {}
};
bool intersect(const Ray &a, const Ray &b) {
if (dot(a.s - b.s, cross(a.dir, b.dir)) != 0)
return false;
return
same_dir(cross(b.s - a.s, b.dir), cross(a.dir, b.dir)) &&
same_dir(cross(a.s - b.s, a.dir), cross(b.dir, a.dir));
}
const lld INF = 1e18;
bool chmin(auto &x, auto v) {
if (x > v) return x = v, true;
return false;
}
struct KM { // maximize, test @ UOJ 80
int n, l, r; lld ans; // fl and fr are the match
vector<lld> hl, hr; vector<int> fl, fr, pre, q;
void bfs(const auto &w, int s) {
vector<int> vl(n), vr(n); vector<lld> slk(n, INF);
l = r = 0; vr[q[r++] = s] = true;
const auto check = [&](int x) -> bool {
if (vl[x] || slk[x] > 0) return true;
vl[x] = true; slk[x] = INF;
if (fl[x] != -1) return (vr[q[r++] = fl[x]] = true);
while (x != -1) swap(x, fr[fl[x] = pre[x]]);
return false;
};
while (true) {
while (l < r)
for (int x = 0, y = q[l++]; x < n; ++x) if (!vl[x])
if (chmin(slk[x], hl[x] + hr[y] - w[x][y]))
if (pre[x] = y, !check(x)) return;
lld d = ranges::min(slk);
for (int x = 0; x < n; ++x)
vl[x] ? hl[x] += d : slk[x] -= d;
for (int x = 0; x < n; ++x) if (vr[x]) hr[x] -= d;
for (int x = 0; x < n; ++x) if (!check(x)) return;
}
}
KM(int n_, const auto &w) : n(n_), ans(0),
hl(n), hr(n), fl(n, -1), fr(fl), pre(n), q(n) {
for (int i = 0; i < n; ++i) hl[i]=ranges::max(w[i]);
for (int i = 0; i < n; ++i) bfs(w, i);
for (int i = 0; i < n; ++i) ans += w[i][fl[i]];
}
};
const int inf = 1e9;
signed main() {
cin.tie(nullptr)->sync_with_stdio(false);
int n;
cin >> n;
vector<P3> p(n), v(n);
for (int i = 0; i < n; i++) {
cin >> p[i].x >> p[i].y >> p[i].z;
cin >> v[i].x >> v[i].y >> v[i].z;
}
if (n == 1) {
cout << -1 << '\n';
return 0;
}
bool colinear = true;
for (int i = 2; i < n; i++) {
if (cross(p[i] - p[0], p[1] - p[0]) != P3(0, 0, 0)) {
colinear = false;
break;
}
}
if (colinear && n % 2 == 1) {
auto solveTwo = [&](int i, int j) {
int res = 0;
if (!same_dir(p[i] - p[j], v[j]))
++res;
if (!same_dir(p[j] - p[i], v[i]))
++res;
return res;
};
vector<int> idx(n);
iota(all(idx), 0);
sort(all(idx), [&](int a, int b) {
return dot(p[a] - p[0], p[1] - p[0]) < dot(p[b] - p[0], p[1] - p[0]);
});
int ans = 1e9;
for (int _ = 0; _ < 2; _++) {
orange(all(idx));
auto V = p[idx[1]] - p[idx[0]];
for (int s = 0; s < n; s++) {
auto tmp = idx;
tmp.erase(find(all(tmp), s));
vector<int> pre(n, inf);
pre[0] = 0;
for (int l = 0; l + 1 < ssize(tmp); l += 2) {
pre[l + 2] = pre[l] + solveTwo(tmp[l], tmp[l + 1]);
}
for (int l = 0; l < n; l += 2) {
int middle = 0;
for (int r = l; r < n; r++) {
if (r != l && r % 2 == 0) {
int cur = middle + pre[l] + (pre[n - 1] - pre[r]);
if (!same_dir(v[tmp[r - 1]], V)) {
--cur;
}
Ray A(p[tmp[l]], -v[s]);
Ray B(p[tmp[r - 1]], v[tmp[r - 1]]);
bool left_colinear = cross(v[s], V) == P3(0, 0, 0);
bool right_colinear = cross(v[tmp[r - 1]], V) == P3(0, 0, 0);
debug(cur, l, r);
debug(s, pre[l], pre[n - 1] - pre[r], middle);
if (left_colinear || right_colinear) {
cur += left_colinear;
cur += right_colinear;
} else if (!intersect(A, B)) {
++cur;
}
ans = min(ans, cur + 1000);
}
if (!same_dir(v[tmp[r]], V)) {
++middle;
}
}
}
}
reverse(all(idx));
}
cout << ans << '\n';
return 0;
}
auto w = vector(n, vector(n, -inf));
for (int i = 0; i < n; i++) {
map<P3, int> mp;
for (int j = 0; j < n; j++) if (j != i) {
auto r = reduced(p[j] - p[i]);
if (auto it = mp.find(r); it != mp.end()) {
if (norm(p[it->second] - p[i]) > norm(p[j] - p[i])) {
it->second = j;
}
} else {
mp[r] = j;
}
}
for (auto [_, j] : mp) {
if (same_dir(p[j] - p[i], v[i])) {
w[i][j] = 1;
} else {
w[i][j] = 0;
}
}
}
auto ma = KM(n, w);
cout << n - ma.ans << '\n';
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3552kb
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: 3608kb
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: 0ms
memory: 3580kb
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: 3808kb
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: 3620kb
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: 3624kb
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: 3452kb
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: 0ms
memory: 3548kb
input:
1 0 0 0 3 1 4
output:
-1
result:
ok single line: '-1'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3608kb
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: -100
Wrong Answer
time: 0ms
memory: 4320kb
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:
1000000242
result:
wrong answer 1st lines differ - expected: '250', found: '1000000242'