Submission #968554

#	Time	Username	Problem	Language	Result	Execution time	Memory
968554		kilkuwu	Circle selection (APIO18_circle_selection)	C++17	100 / 100	1018 ms	36736 KiB

circle_selection

#include <bits/stdc++.h>

#define nl '\n'

const int inf = 1e9;

signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  
  int n;
  std::cin >> n;
  std::vector<int> ans(n, -1);

  std::vector<std::array<int, 3>> c(n);
  for (int i = 0; i < n; i++) {
    std::cin >> c[i][1] >> c[i][2] >> c[i][0];
    c[i][1] += inf;
    c[i][2] += inf;
  }

  std::vector<int> ord(n);
  std::iota(ord.begin(), ord.end(), 0);
  std::sort(ord.begin(), ord.end(), [&](int i, int j) {
    if (c[i][0] == c[j][0]) return i < j;
    return c[i][0] > c[j][0];
  });

  int block = c[ord[0]][0];
  
  std::vector<std::pair<int, int>> xy;
  std::vector<std::vector<int>> at(n);

  auto get_id = [&](std::pair<int, int> p) {
    int i = std::lower_bound(xy.begin(), xy.end(), p) - xy.begin();
    if (i == (int) xy.size() || xy[i] != p) return -1;
    return i;
  };

  auto sqr = [&](int x) -> int64_t {
    return (int64_t) x * x;
  };

  auto intersect = [&](int i, int j) {
    auto dist = sqr(c[i][1] - c[j][1]) + sqr(c[i][2] - c[j][2]);
    auto srad = sqr(c[i][0] + c[j][0]);
    return dist <= srad;
  };

  auto rescale = [&]() {
    xy.clear();
    for (int i = 0; i < n; i++) {
      at[i].clear();
    }
    for (int i = 0; i < n; i++) {
      if (ans[i] != -1) continue;
      xy.emplace_back(c[i][1] / block, c[i][2] / block);
    }
    std::sort(xy.begin(), xy.end());
    xy.erase(std::unique(xy.begin(), xy.end()), xy.end());

    for (int i = 0; i < n; i++) {
      if (ans[i] != -1) continue;
      at[get_id({c[i][1] / block, c[i][2] / block})].push_back(i);
    }
  };

  rescale();

  for (int id : ord) {
    if (ans[id] != -1) continue;
    if (c[id][0] * 2 < block) {
      block = c[id][0];
      rescale();
    }
    ans[id] = id;

    int x = c[id][1] / block;
    int y = c[id][2] / block;

    for (int i = x - 2; i <= x + 2; i++) {
      for (int j = y - 2; j <= y + 2; j++) {
        int idx = get_id({i, j});
        if (idx == -1) continue;
        std::vector<int> new_at;
        for (int ii : at[idx]) {
          if (intersect(id, ii)) {
            ans[ii] = id;
          } else {
            new_at.push_back(ii);
          }
        }
        std::swap(at[idx], new_at);
      }
    }
  }

  for (int i = 0; i < n; i++) {
    std::cout << ++ans[i] << " ";
  }
  std::cout << nl;
}

• Subtask 1: 7 / 7
• Subtask 2: 12 / 12
• Subtask 3: 15 / 15
• Subtask 4: 23 / 23
• Subtask 5: 30 / 30
• Subtask 6: 13 / 13