Submission #235106

#	Time	Username	Problem	Language	Result	Execution time	Memory
235106		rama_pang	Circle selection (APIO18_circle_selection)	C++14	7 / 100	2809 ms	46712 KiB

circle_selection

#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 = -2; dx <= 2; dx++) {
      for (int dy = -2; dy <= 2; 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 / 7
• Subtask 2: 0 / 12
• Subtask 3: 0 / 15
• Subtask 4: 0 / 23
• Subtask 5: 0 / 30
• Subtask 6: 0 / 13