QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#277471#6570. Who Watches the Watchmen?ucup-team1198TL 767ms3660kbC++208.4kb2023-12-06 19:14:182023-12-06 19:14:18

Judging History

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

  • [2023-12-06 19:14:18]
  • 评测
  • 测评结果:TL
  • 用时:767ms
  • 内存:3660kb
  • [2023-12-06 19:14:18]
  • 提交

answer

#include <map>
#include <set>
#include <array>
#include <cmath>
#include <deque>
#include <bitset>
#include <random>
#include <string>
#include <vector>
#include <cassert>
#include <complex>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>

#pragma GCC optimize("unroll-loops","Ofast")

using namespace std;

// #define int int64_t

struct Vector {
  int x;
  int y;
  int z;

  Vector(int x = 0, int y = 0, int z = 0): x(x), y(y), z(z) {}
  Vector(const Vector& a, const Vector& b): x(b.x - a.x), y(b.y - a.y), z(b.z - a.z) {}
};

Vector operator-(const Vector& a, const Vector& b) {
  return Vector(b, a);
}

Vector operator+(const Vector& a, const Vector& b) {
  return {a.x + b.x, a.y + b.y, a.z + b.z};
}

int64_t operator*(const Vector& a, const Vector& b) {
  return a.x * b.x + a.y * b.y + a.z * b.z;
}

__int128 dot(const Vector& a, const Vector& b) {
  return (__int128)a.x * b.x + (__int128)a.y * b.y + (__int128)a.z * b.z;
}

Vector operator%(const Vector& a, const Vector& b) {
  return Vector(a.y * b.z - a.z * b.y, a.z * b.x - a.x * b.z, a.x * b.y - a.y * b.x);
}

int64_t vol(const Vector& a, const Vector& b, const Vector& c) {
  return a * (b % c);
}

__int128 vol128(const Vector& a, const Vector& b, const Vector& c) {
  return  dot(a, (b % c));
}

istream& operator>>(istream& in, Vector& v) {
  in >> v.x >> v.y >> v.z;
  return in;
}

bool operator==(const Vector& a, const Vector& b) {
  return a.x == b.x && a.y == b.y && a.z == b.z;
}

bool coplane(const Vector& a, const Vector& b, const Vector& c, const Vector& d) {
  return vol(b - a, c - a, d - a) == 0;
}

const int MAXN = 600;
Vector p[MAXN], dir[MAXN];

struct CostEdge {
  int from, to, cap, cost, nxt;
  int flow = 0;
  CostEdge() {}
  CostEdge(int from, int to, int cap, int cost, int nxt): from(from), to(to), cap(cap), cost(cost), nxt(nxt) {}
};

struct CostFlow {
  static constexpr int INF = 1e9;

  int n;
  int s, t;
  vector<CostEdge> e;
  vector<int> head;

  CostFlow(int n, int s = -1, int t = -1): n(n), s(s), t(t), head(vector<int>(n, -1)) {}

  void add_edge(int from, int to, int cap, int cost) {
    /// cerr << from << " " << to << " " << cap << " " << cost << endl;
    e.emplace_back(from, to, cap, cost, head[from]);
    head[from] = e.size() - 1;
    e.emplace_back(to, from, 0, -cost, head[to]);
    head[to] = e.size() - 1;
  }

  vector<int> pot;
  int cost = 0;
  int flow = 0;

  void calc_pot() {
    pot = vector<int>(n, 0);
    // pot[s] = 0;
    // for (int i = 0; i < n; ++i) {
    //   for (auto e1 : e) {
    //     if (e1.flow < e1.cap) {
    //       pot[e1.to] = min(pot[e1.to], pot[e1.from] + e1.cost);
    //     }
    //   }
    // }
  }

  bool step() {
    vector<int> dist(n, INF);
    vector<int> pred(n, -1);
    vector<int> used(n, 0);
    dist[s] = 0;
    while (true) {
      int v = -1;
      for (int i = 0; i < n; ++i) {
        if (used[i]) continue;
        if (v == -1 || dist[i] < dist[v]) {
          v = i;
        }
      }
      if (v == -1) break;
      used[v] = true;
      for (int i = head[v]; i != -1; i = e[i].nxt) {
        if (e[i].flow == e[i].cap) continue;
        if (dist[e[i].to] > dist[v] + e[i].cost + pot[v] - pot[e[i].to]) {
          dist[e[i].to] = dist[v] + e[i].cost + pot[v] - pot[e[i].to];
          pred[e[i].to] = i;
        }
      }
    }

    /**for (int i = 0; i < n; ++i) {
      cerr << dist[i] << " ";
    }
    cerr << endl;*/

    if (dist[t] == INF) return false;
    int mn = INF;
    int at = t;
    int pr = pred[at];
    while (pr != -1) {
      mn = min(mn, e[pr].cap - e[pr].flow);
      at = e[pr].from;
      pr = pred[at];
    }

    at = t;
    pr = pred[at];
    while (pr != -1) {
      e[pr].flow += mn;
      e[pr ^ 1].flow -= mn;
      at = e[pr].from;
      pr = pred[at];
    }

    flow += mn;
    cost += mn * (dist[t] + pot[t]);

    for (int i = 0; i < n; ++i) {
      pot[i] += dist[i];
    }
    return true;
  }

  pair<int, int> get() {
    calc_pot();
    while (step()) {
      /// cerr << "step" << endl;
    }
    return {flow, cost};
  }
};

signed main() {
#ifdef DEBUG
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
#else
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
#endif

  int n;
  cin >> n;
  for (int i = 0; i < n; ++i) {
    cin >> p[i] >> dir[i];
  }

  if (n == 1) {
    cout << "-1\n";
    return 0;
  }

  bool is_col = (n % 2 != 0);
  for (int i = 2; i < n; ++i) {
    is_col &= ((p[i] - p[0]) % (p[1] - p[0]) == Vector());
  }

  auto add_from_segm = [&](int ind, int start, int fin, Vector go) {
      int cnt = 0;
      if (dir[ind] % go == Vector() && dir[fin] % go == Vector()) {
        cnt += 2;
      } else if (dir[ind] % go == Vector() || dir[fin] % go == Vector()) {
        ++cnt;
      } else {
        if (!coplane(p[start], p[fin], p[fin] + dir[fin], p[start] - dir[ind])) {
          ++cnt;
        } else if (dir[fin] % dir[ind] == Vector()) {
          ++cnt;
        } else {
          Vector norm = go % dir[ind];
          __int128 a = vol128(norm, go, dir[fin]);
          __int128 b = vol128(norm, go, dir[ind]);
          if (a < 0 && b < 0) {
            ++cnt;
          } else if (a > 0 && b > 0) {
            ++cnt;
          }
        }
      }
      return cnt;
  };

  if (is_col) {
    int ans = 2000;
    Vector start = p[0];
    Vector go = p[1] - p[0];
    vector<int> ord(n);
    iota(ord.begin(), ord.end(), 0);
    sort(ord.begin(), ord.end(), [&](int i, int j) {
      return (p[i] - start) * go < (p[j] - start) * go;
    });
    for (int i = 0; i < n; ++i) {
      vector<int> lft;
      for (int j = 0; j < n; ++j) {
        if (j != i) {
          lft.push_back(j);
        }
      }
      vector<int> pref_cnt_both_dirs(n);
      for (int i = 0; i < n - 1; ++i) {
        int delta = 0;
        if (i % 2 == 0) {
          if (dir[ord[lft[i]]] % go == Vector() && dir[ord[lft[i]]] * go > 0) {

          } else {
            ++delta;
          }
        } else {
          if (dir[ord[lft[i]]] % go == Vector() && dir[ord[lft[i]]] * go < 0) {

          } else {
            ++delta;
          }
        }
        pref_cnt_both_dirs[i + 1] = pref_cnt_both_dirs[i] + delta;
      }
      vector<int> pref_cnt_dir1(n);
      for (int i = 0; i < n - 1; ++i) {
        int delta = 0;
        if (dir[ord[lft[i]]] % go == Vector() && dir[ord[lft[i]]] * go > 0) {

          } else {
            ++delta;
          }
        pref_cnt_dir1[i + 1] = pref_cnt_dir1[i] + delta;
      }
      vector<int> pref_cnt_dir2(n);
      for (int i = 0; i < n - 1; ++i) {
        int delta = 0;
        if (dir[ord[lft[i]]] % go == Vector() && dir[ord[lft[i]]] * go < 0) {

          } else {
            ++delta;
          }
        pref_cnt_dir2[i + 1] = pref_cnt_dir2[i] + delta;
      }

      int ind = ord[i];

      for (int l = 0; l < n - 1; l += 2) {
        for (int r = l + 1; r < n - 1; r += 2) {
          int cur_ans = add_from_segm(ind, ord[lft[l]], ord[lft[r]], go) + pref_cnt_both_dirs[l] + pref_cnt_both_dirs[n - 1] - pref_cnt_both_dirs[r + 1];
          cur_ans += pref_cnt_dir1[r] - pref_cnt_dir1[l];
          ans = min(ans, 1000 + cur_ans);
        }
      }
      for (int l = 0; l < n - 1; l += 2) {
        for (int r = l + 1; r < n - 1; r += 2) {
          int cur_ans = add_from_segm(ind, ord[lft[r]], ord[lft[l]], go) + pref_cnt_both_dirs[l] + pref_cnt_both_dirs[n - 1] - pref_cnt_both_dirs[r + 1];
          cur_ans += pref_cnt_dir2[r + 1] - pref_cnt_dir2[l + 1];
          ans = min(ans, 1000 + cur_ans);
        }
      }
    }
    cout << ans << "\n";
    return 0;
  }

  CostFlow mincost(2 * n + 2, 2 * n, 2 * n + 1);
  for (int i = 0; i < n; ++i) {
    mincost.add_edge(mincost.s, 2 * i + 1, 1, 0);
    mincost.add_edge(2 * i, mincost.t, 1, 0);
  }

  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      if (i == j) continue;
      bool has_veiw = true;
      for (int k = 0; k < n; ++k) {
        if (k == i || k == j) continue;
        if ((p[k] - p[i]) % (p[j] - p[i]) == Vector()) {
          if ((p[i] - p[k]) * (p[j] - p[k]) < 0) {
            has_veiw = false;
            break;
          }
        }
      }
      if (!has_veiw) continue;
      int cost = 1;
      if (dir[i] % (p[j] - p[i]) == Vector() && dir[i] * (p[j] - p[i]) > 0) {
        cost = 0;
      }
      mincost.add_edge(2 * i + 1, 2 * j, 1, cost);
    }
  }

  /// cerr << "start mincost" << endl;

  auto res = mincost.get();
  /// cerr << res.first << endl;
  assert(res.first == n);
  cout << res.second << "\n";
  
  return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3468kb

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

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

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

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

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

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: 1ms
memory: 3512kb

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: 1ms
memory: 3516kb

input:

1
0 0 0 3 1 4

output:

-1

result:

ok single line: '-1'

Test #9:

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

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: 0
Accepted
time: 767ms
memory: 3612kb

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:

250

result:

ok single line: '250'

Test #11:

score: 0
Accepted
time: 763ms
memory: 3660kb

input:

500
0 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...

output:

250

result:

ok single line: '250'

Test #12:

score: 0
Accepted
time: 766ms
memory: 3632kb

input:

500
0 0 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...

output:

250

result:

ok single line: '250'

Test #13:

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

input:

5
1 0 0 1 -1 0
2 0 0 0 1 0
3 0 0 -1 0 0
4 0 0 -1 0 0
5 0 0 -1 0 0

output:

1000

result:

ok single line: '1000'

Test #14:

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

input:

5
1 0 0 1 0 0
2 0 0 1 0 0
3 0 0 1 0 0
4 0 0 0 1 0
5 0 0 -1 -1 0

output:

1000

result:

ok single line: '1000'

Test #15:

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

input:

6
0 1 0 1 0 0
0 2 0 0 2 0
0 3 0 0 3 0
0 4 0 0 4 0
0 5 0 0 5 0
0 6 0 0 6 0

output:

4

result:

ok single line: '4'

Test #16:

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

input:

9
1 0 0 1 0 0
2 0 0 1 0 0
3 0 0 1 0 0
0 1 0 0 1 0
0 2 0 0 1 0
0 3 0 0 1 0
0 0 1 0 0 1
0 0 2 0 0 1
0 0 3 0 0 1

output:

3

result:

ok single line: '3'

Test #17:

score: 0
Accepted
time: 101ms
memory: 3540kb

input:

499
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:

1220

result:

ok single line: '1220'

Test #18:

score: 0
Accepted
time: 97ms
memory: 3528kb

input:

499
0 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...

output:

1220

result:

ok single line: '1220'

Test #19:

score: 0
Accepted
time: 101ms
memory: 3476kb

input:

499
0 0 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...

output:

1220

result:

ok single line: '1220'

Test #20:

score: 0
Accepted
time: 1ms
memory: 3512kb

input:

5
0 0 0 0 -1 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

output:

1001

result:

ok single line: '1001'

Test #21:

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

input:

5
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 0 1 0

output:

1001

result:

ok single line: '1001'

Test #22:

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

input:

5
0 0 0 1 0 0
1 0 0 1 0 0
2 0 0 0 -1 0
3 0 0 1 0 0
4 0 0 -1 0 0

output:

1001

result:

ok single line: '1001'

Test #23:

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

input:

5
0 0 0 1 0 0
1 0 0 -1 0 0
2 0 0 1 0 0
3 0 0 0 -1 0
4 0 0 1 0 0

output:

1001

result:

ok single line: '1001'

Test #24:

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

input:

5
0 0 0 1 1 0
1 0 0 1 0 0
2 0 0 1 0 0
3 0 0 1 0 0
4 0 0 -1 -1 0

output:

1001

result:

ok single line: '1001'

Test #25:

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

input:

5
0 0 0 1 1 0
1 0 0 1 0 0
2 0 0 1 0 0
3 0 0 1 0 0
4 0 0 1 1 0

output:

1001

result:

ok single line: '1001'

Test #26:

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

input:

5
0 0 0 5 -1 0
1 0 0 1 0 0
2 0 0 1 0 0
3 0 0 1 0 0
4 0 0 1 -1 0

output:

1001

result:

ok single line: '1001'

Test #27:

score: 0
Accepted
time: 1ms
memory: 3536kb

input:

17
0 0 0 0 0 1
0 1 0 0 0 1
0 2 0 0 0 1
0 3 0 0 0 1
0 4 0 0 0 1
0 -1 0 0 0 1
0 -2 0 0 0 1
0 -3 0 0 0 1
0 -4 0 0 0 1
1 3 0 0 0 1
2 3 0 0 0 1
-1 3 0 0 0 1
-2 3 0 0 0 1
1 -3 0 0 0 1
2 -3 0 0 0 1
-1 -3 0 0 0 1
-2 -3 0 0 0 1

output:

17

result:

ok single line: '17'

Test #28:

score: 0
Accepted
time: 1ms
memory: 3492kb

input:

17
0 0 0 0 4 0
0 1 0 0 -1 0
0 2 0 0 -2 0
0 3 0 0 -3 0
0 4 0 0 -4 0
0 -1 0 0 1 0
0 -2 0 0 2 0
0 -3 0 0 3 0
0 -4 0 0 4 0
1 3 0 -1 -3 0
2 3 0 -1 -2 0
-1 3 0 1 -3 0
-2 3 0 2 -3 0
1 -3 0 -1 3 0
2 -3 0 -2 3 0
-1 -3 0 1 3 0
-2 -3 0 2 3 0

output:

10

result:

ok single line: '10'

Test #29:

score: 0
Accepted
time: 1ms
memory: 3544kb

input:

17
0 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 2 -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
1 3 0 -1 0 0
2 3 0 -1 0 0
-1 3 0 -1 0 0
-2 3 0 4 -6 0
1 -3 0 -1 0 0
2 -3 0 -1 0 0
-1 -3 0 -1 0 0
-2 -3 0 2 -1 0

output:

3

result:

ok single line: '3'

Test #30:

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

input:

5
0 0 0 1 1 1
0 0 1 0 0 1
0 0 2 0 0 1
0 0 3 0 0 1
0 0 4 0 -1 1

output:

1001

result:

ok single line: '1001'

Test #31:

score: -100
Time Limit Exceeded

input:

500
-455212 958307 274912 -88656 390687 881409
-498879 -623821 322766 -916023 347922 541726
-594515 -554311 -413504 -881701 -506880 -144667
658945 -503396 791805 314816 -830920 -769486
-200847 845218 468338 -166468 -49854 -287877
-820402 914874 916800 258029 -210000 -296727
702016 -389491 -31529 -52...

output:


result: