QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#338582#6570. Who Watches the Watchmen?ckisekiWA 2ms3880kbC++234.5kb2024-02-26 01:17:022024-02-26 01:17:02

Judging History

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

  • [2024-02-26 01:17:02]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3880kb
  • [2024-02-26 01:17:02]
  • 提交

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; _++) {
      orange(all(idx));

      for (int s = 0; s < n; s++) {

        auto tmp = idx;
        tmp.erase(find(all(tmp), s));

        auto V = p[tmp[1]] - p[tmp[0]];

        int cur = 1000;
        for (int i = 0; i + 1 < n - 1; i++) {
          if (!same_dir(v[tmp[i]], V)) {
            ++cur;
          }
        }

        Ray A(p[tmp[0]], -v[s]);
        Ray B(p[tmp[n - 2]], v[tmp[n - 2]]);

        if (same_dir(-v[s], V) || same_dir(v[tmp[n - 2]], -V)) {
          cur += same_dir(-v[s], V);
          cur += same_dir(v[tmp[n - 2]], -V);
        } else if (!intersect(A, B))
          ++cur;
        debug(s, 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: 100
Accepted
time: 0ms
memory: 3880kb

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: 3660kb

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: 3656kb

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: 3812kb

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: 3596kb

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: 3652kb

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: 3620kb

input:

1
0 0 0 3 1 4

output:

-1

result:

ok single line: '-1'

Test #9:

score: 0
Accepted
time: 0ms
memory: 3580kb

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: 2ms
memory: 3620kb

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:

1242

result:

wrong answer 1st lines differ - expected: '250', found: '1242'