QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#338578 | #6570. Who Watches the Watchmen? | ckiseki | WA | 1ms | 3820kb | C++23 | 4.3kb | 2024-02-26 01:10:47 | 2024-02-26 01:10:48 |
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;
}
};
lld dot(const P3 &a, const P3 &b) {
return a.x*b.x+a.y*b.y+a.z*b.z;
}
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));
}
struct HK {
vector<int> l, r, a, p; int ans;
HK(int n, int m, auto &g) : l(n,-1), r(m,-1), ans(0) {
for (bool match = true; match;) {
match = false; a.assign(n, -1); p.assign(n, -1);
queue<int> q;
for (int i = 0; i < n; i++)
if (l[i] == -1) q.push(a[i] = p[i] = i);
// bitset<maxn> nvis, t; nvis.set();
while (!q.empty()) {
int z, x = q.front(); q.pop();
if (l[a[x]] != -1) continue;
for (int y : g[x]) { // or iterate t = g[x]&nvis
// nvis.reset(y);
if (r[y] == -1) {
for (z = y; z != -1; )
r[z] = x, swap(l[x], z), x = p[x];
match = true; ++ans; break;
} else if (p[r[y]] == -1)
q.push(z = r[y]), p[z] = x, a[z] = a[x];
}
}
}
}
};
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;
}
if (n == 2) {
int ans = 0;
if (!same_dir(v[0], p[1] - p[0])) {
++ans;
}
if (!same_dir(v[1], p[0] - p[1])) {
++ans;
}
cout << ans << '\n';
}
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) {
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; _++) {
for (int s = 0; s < n; s++) {
auto tmp = idx;
tmp.erase(find(all(tmp), s));
int cur = 1000;
for (int i = 0; i + 1 < n - 1; i++) {
if (!same_dir(v[tmp[i]], p[tmp[1]] - p[tmp[0]])) {
++cur;
}
}
Ray A(p[tmp[0]], -v[s]);
Ray B(p[tmp[n - 2]], v[s]);
if (!intersect(A, B))
++cur;
ans = min(ans, cur);
}
reverse(all(idx));
}
cout << ans << '\n';
return 0;
}
set<int> rs;
for (int i = 0; i < n; i++) {
lld cur_mn = 1e18;
int r = -1;
for (int j = 0; j < n; j++) if (j != i) {
if (same_dir(p[j] - p[i], v[i])) {
lld d = dot(p[j] - p[i], v[i]);
if (cur_mn > d) {
cur_mn = d;
r = j;
}
}
}
debug(i, r);
if (r != -1) {
rs.insert(r);
}
}
cout << n - rs.size() << '\n';
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3820kb
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'