QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#338597#6570. Who Watches the Watchmen?ckisekiWA 0ms4320kbC++236.2kb2024-02-26 03:08:312024-02-26 03:08:32

Judging History

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

  • [2024-02-26 03:08:32]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:4320kb
  • [2024-02-26 03:08:31]
  • 提交

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';

}

Details

Tip: Click on the bar to expand more detailed information

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'