oj.uz

Submission #235109

# Submission time Handle Problem Language Result Execution time Memory
235109 2020-05-27T05:30:42 Z rama_pang Circle selection (APIO18_circle_selection) C++14
64 / 100
 3000 ms 35972 KB 
#include <bits/stdc++.h>
using namespace std;

struct Circle {
  int x, y, r, id;
  Circle() {}
  Circle(int x, int y, int r, int id) : x(x), y(y), r(r), id(id) {}
  bool operator < (const Circle &o) const { return r > o.r || (r == o.r && id < o.id); }
};

bool Intersect(Circle a, Circle b) {
  return (1ll * (b.x - a.x) * (b.x - a.x) + 
          1ll * (b.y - a.y) * (b.y - a.y) <= 
          1ll * (b.r + a.r) * (b.r + a.r));
}

using Point = pair<int, int>;

int N;
vector<Circle> circles;

vector<int> revpos;
vector<bool> deleted;
vector<int> answer;

vector<Point> points;
vector<vector<int>> areas;

void Resize(int lg) {
  int side = 1 << lg;
  points.clear();
  for (int i = 0; i < N; i++) if (!deleted[circles[i].id]) {
    points.emplace_back(circles[i].x / side, circles[i].y / side);
  }
  sort(begin(points), end(points));
  points.resize(unique(begin(points), end(points)) - begin(points));

  areas.clear();
  areas.resize(points.size());
  for (int i = 0; i < N; i++) if (!deleted[circles[i].id]) {
    auto pos = lower_bound(begin(points), end(points), Point(circles[i].x / side, circles[i].y / side));
    areas[(pos - begin(points))].emplace_back(circles[i].id);
  }
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);

  cin >> N;
  for (int i = 0; i < N; i++) {
    int x, y, r;
    cin >> x >> y >> r;
    x += 1e9, y += 1e9;
    circles.emplace_back(x, y, r, i);
    deleted.emplace_back(false);
    answer.emplace_back(-1);
  }

  sort(begin(circles), end(circles));
  revpos.resize(N);
  for (int i = 0; i < N; i++) {
    revpos[circles[i].id] = i;
  }  

  int lg = 30;
  Resize(lg);

  for (auto c : circles) if (!deleted[c.id]) {
    while ((1 << (lg - 1)) >= c.r) {
      Resize(--lg);
    }
    int side = 1 << lg;
    int x = c.x / side;
    int y = c.y / side;
    for (int dx = -2; dx <= 2; dx++) {
      for (int dy = -2; dy <= 2; dy++) {
        auto it = lower_bound(begin(points), end(points), Point(x + dx, y + dy));
        if (it == end(points) || *it != make_pair(x + dx, y + dy)) {
          continue;
        }
        for (auto j : areas[it - begin(points)]) {
          if (Intersect(c, circles[revpos[j]]) && !deleted[j]) {
            answer[j] = c.id;
            deleted[j] = true;
          }
        }
      }
    }
  }

  for (int i = 0; i < N; i++) {
    cout << answer[i] + 1 << " \n"[i + 1 == N];
  }
  return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Correct 6 ms 256 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 5 ms 512 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 5 ms 384 KB Output is correct
18 Correct 6 ms 384 KB Output is correct
19 Correct 8 ms 768 KB Output is correct
20 Correct 9 ms 768 KB Output is correct
21 Correct 9 ms 896 KB Output is correct
22 Correct 33 ms 1088 KB Output is correct
23 Correct 36 ms 1044 KB Output is correct
24 Correct 31 ms 1104 KB Output is correct
25 Correct 35 ms 1028 KB Output is correct
26 Correct 33 ms 1128 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 225 ms 17044 KB Output is correct
2 Correct 251 ms 16916 KB Output is correct
3 Correct 249 ms 16664 KB Output is correct
4 Correct 202 ms 16916 KB Output is correct
5 Correct 973 ms 16788 KB Output is correct
6 Correct 1639 ms 19476 KB Output is correct
7 Correct 1018 ms 16788 KB Output is correct
8 Correct 1220 ms 16792 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 668 ms 11956 KB Output is correct
3 Correct 2685 ms 33884 KB Output is correct
4 Correct 2689 ms 34116 KB Output is correct
5 Correct 2158 ms 26120 KB Output is correct
6 Correct 904 ms 15792 KB Output is correct
7 Correct 461 ms 7564 KB Output is correct
8 Correct 93 ms 2484 KB Output is correct
9 Correct 2506 ms 32372 KB Output is correct
10 Correct 1865 ms 27560 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2870 ms 34016 KB Output is correct
2 Execution timed out 3095 ms 35972 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Correct 6 ms 256 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 5 ms 512 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 5 ms 384 KB Output is correct
18 Correct 6 ms 384 KB Output is correct
19 Correct 8 ms 768 KB Output is correct
20 Correct 9 ms 768 KB Output is correct
21 Correct 9 ms 896 KB Output is correct
22 Correct 33 ms 1088 KB Output is correct
23 Correct 36 ms 1044 KB Output is correct
24 Correct 31 ms 1104 KB Output is correct
25 Correct 35 ms 1028 KB Output is correct
26 Correct 33 ms 1128 KB Output is correct
27 Correct 13 ms 1216 KB Output is correct
28 Correct 13 ms 1216 KB Output is correct
29 Correct 12 ms 1216 KB Output is correct
30 Correct 66 ms 1816 KB Output is correct
31 Correct 61 ms 1820 KB Output is correct
32 Correct 66 ms 1792 KB Output is correct
33 Correct 76 ms 5800 KB Output is correct
34 Correct 75 ms 5804 KB Output is correct
35 Correct 95 ms 5800 KB Output is correct
36 Correct 765 ms 11968 KB Output is correct
37 Correct 826 ms 12044 KB Output is correct
38 Correct 742 ms 12144 KB Output is correct
39 Correct 572 ms 9588 KB Output is correct
40 Correct 538 ms 9332 KB Output is correct
41 Correct 542 ms 9332 KB Output is correct
42 Correct 413 ms 8104 KB Output is correct
43 Correct 748 ms 11488 KB Output is correct
44 Correct 735 ms 11528 KB Output is correct
45 Correct 717 ms 11608 KB Output is correct
46 Correct 715 ms 11608 KB Output is correct
47 Correct 730 ms 11636 KB Output is correct
48 Correct 719 ms 11736 KB Output is correct
49 Correct 715 ms 11600 KB Output is correct
50 Correct 733 ms 11480 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Correct 6 ms 256 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 5 ms 512 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 5 ms 384 KB Output is correct
18 Correct 6 ms 384 KB Output is correct
19 Correct 8 ms 768 KB Output is correct
20 Correct 9 ms 768 KB Output is correct
21 Correct 9 ms 896 KB Output is correct
22 Correct 33 ms 1088 KB Output is correct
23 Correct 36 ms 1044 KB Output is correct
24 Correct 31 ms 1104 KB Output is correct
25 Correct 35 ms 1028 KB Output is correct
26 Correct 33 ms 1128 KB Output is correct
27 Correct 225 ms 17044 KB Output is correct
28 Correct 251 ms 16916 KB Output is correct
29 Correct 249 ms 16664 KB Output is correct
30 Correct 202 ms 16916 KB Output is correct
31 Correct 973 ms 16788 KB Output is correct
32 Correct 1639 ms 19476 KB Output is correct
33 Correct 1018 ms 16788 KB Output is correct
34 Correct 1220 ms 16792 KB Output is correct
35 Correct 5 ms 384 KB Output is correct
36 Correct 668 ms 11956 KB Output is correct
37 Correct 2685 ms 33884 KB Output is correct
38 Correct 2689 ms 34116 KB Output is correct
39 Correct 2158 ms 26120 KB Output is correct
40 Correct 904 ms 15792 KB Output is correct
41 Correct 461 ms 7564 KB Output is correct
42 Correct 93 ms 2484 KB Output is correct
43 Correct 2506 ms 32372 KB Output is correct
44 Correct 1865 ms 27560 KB Output is correct
45 Correct 2870 ms 34016 KB Output is correct
46 Execution timed out 3095 ms 35972 KB Time limit exceeded
47 Halted 0 ms 0 KB -