QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#338578#6570. Who Watches the Watchmen?ckisekiWA 1ms3820kbC++234.3kb2024-02-26 01:10:472024-02-26 01:10:48

Judging History

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

  • [2024-02-26 01:10:48]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3820kb
  • [2024-02-26 01:10:47]
  • 提交

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'