oj.uz

Submission #235107

# Submission time Handle Problem Language Result Execution time Memory
235107 2020-05-27T05:24:24 Z rama_pang Circle selection (APIO18_circle_selection) C++14
7 / 100
 3000 ms 39064 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; }
};

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<pair<Point, vector<int>>> areas;

void Resize(int lg) {
  int side = 1 << lg;
  vector<Point> points;
  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();
  for (auto p : points) {
    areas.emplace_back(p, vector<int>());
  }
  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))].second.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 = -3; dx <= 3; dx++) {
      for (int dy = -3; dy <= 3; dy++) {
        auto it = lower_bound(begin(areas), end(areas), 
                  pair<Point, vector<int>>{{x + dx, y + dy}, vector<int>()});
        if (it == end(areas) || it->first != make_pair(x + dx, y + dy)) {
          continue;
        }
        for (auto j : it->second) {
          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 5 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 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 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 384 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 5 ms 384 KB Output is correct
18 Correct 5 ms 384 KB Output is correct
19 Correct 8 ms 768 KB Output is correct
20 Correct 8 ms 768 KB Output is correct
21 Correct 8 ms 768 KB Output is correct
22 Correct 35 ms 1088 KB Output is correct
23 Correct 39 ms 1152 KB Output is correct
24 Correct 34 ms 1132 KB Output is correct
25 Correct 37 ms 1152 KB Output is correct
26 Correct 35 ms 1084 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 223 ms 16288 KB Output is correct
2 Correct 249 ms 17172 KB Output is correct
3 Correct 228 ms 18580 KB Output is correct
4 Correct 196 ms 16788 KB Output is correct
5 Incorrect 959 ms 16660 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 777 ms 11416 KB Output is correct
3 Correct 2993 ms 38992 KB Output is correct
4 Correct 2985 ms 39064 KB Output is correct
5 Incorrect 2470 ms 30944 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3091 ms 38988 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
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 5 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 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 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 384 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 5 ms 384 KB Output is correct
18 Correct 5 ms 384 KB Output is correct
19 Correct 8 ms 768 KB Output is correct
20 Correct 8 ms 768 KB Output is correct
21 Correct 8 ms 768 KB Output is correct
22 Correct 35 ms 1088 KB Output is correct
23 Correct 39 ms 1152 KB Output is correct
24 Correct 34 ms 1132 KB Output is correct
25 Correct 37 ms 1152 KB Output is correct
26 Correct 35 ms 1084 KB Output is correct
27 Correct 12 ms 1208 KB Output is correct
28 Correct 12 ms 1216 KB Output is correct
29 Correct 13 ms 1216 KB Output is correct
30 Correct 70 ms 1908 KB Output is correct
31 Correct 67 ms 1816 KB Output is correct
32 Correct 69 ms 1808 KB Output is correct
33 Correct 74 ms 5688 KB Output is correct
34 Correct 73 ms 5548 KB Output is correct
35 Correct 94 ms 5748 KB Output is correct
36 Correct 846 ms 11996 KB Output is correct
37 Correct 908 ms 11812 KB Output is correct
38 Correct 848 ms 11900 KB Output is correct
39 Incorrect 619 ms 10796 KB Output isn't correct
40 Halted 0 ms 0 KB -

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 5 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 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 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 384 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 5 ms 384 KB Output is correct
18 Correct 5 ms 384 KB Output is correct
19 Correct 8 ms 768 KB Output is correct
20 Correct 8 ms 768 KB Output is correct
21 Correct 8 ms 768 KB Output is correct
22 Correct 35 ms 1088 KB Output is correct
23 Correct 39 ms 1152 KB Output is correct
24 Correct 34 ms 1132 KB Output is correct
25 Correct 37 ms 1152 KB Output is correct
26 Correct 35 ms 1084 KB Output is correct
27 Correct 223 ms 16288 KB Output is correct
28 Correct 249 ms 17172 KB Output is correct
29 Correct 228 ms 18580 KB Output is correct
30 Correct 196 ms 16788 KB Output is correct
31 Incorrect 959 ms 16660 KB Output isn't correct
32 Halted 0 ms 0 KB -