oj.uz

Submission #253658

# Submission time Handle Problem Language Result Execution time Memory
253658 2020-07-28T13:47:07 Z EntityIT Circle selection (APIO18_circle_selection) C++14
15 / 100
 1747 ms 58812 KB 
#include <bits/stdc++.h>
using namespace std;

#define ALL(x) (x).begin(), (x).end()
#define SZ(x) static_cast<int>((x).size())

template<class T, size_t D>
struct vec : vector<vec<T, D - 1>> {
  template<class... Args>
  vec(size_t n = 0, Args... args)
      : vector<vec<T, D - 1>>(n, vec<T, D - 1>(args...)) {}
};
template<class T>
struct vec<T, 1> : vector<T> {
  template<class... Args>
  vec(Args... args)
      : vector<T>(args...) {}
};

template<class T>
inline bool Minimize(T& a, const T& b) { return a > b ? a = b, true : false; }
template<class T>
inline bool Maximize(T& a, const T& b) { return a < b ? a = b, true : false; }
inline int Next(int i, int n) { return i == n - 1 ? 0 : i + 1; }
inline int Prev(int i, int n) { return !i ? n - 1 : i - 1; }

mt19937 rng(static_cast<uint32_t>(chrono::steady_clock::now().time_since_epoch().count()));

struct Circle {
  int x, y, r;
  Circle(int t_x = 0, int t_y = 0, int t_r = 0)
      : x(t_x),
        y(t_y),
        r(t_r) {}

  bool CheckIntersection(const Circle& o) const {
    return static_cast<int64_t>(x - o.x) * (x - o.x) + static_cast<int64_t>(y - o.y) * (y - o.y) <= static_cast<int64_t>(r + o.r) * (r + o.r);
  }
};

int main() {
  ios_base::sync_with_stdio(0); cin.tie(0);

  int n_circles; cin >> n_circles;
  vec<Circle, 1> circles(n_circles);
  int min_x, min_y;
  min_x = min_y = numeric_limits<int>::max();
  for (auto& circle : circles) {
    cin >> circle.x >> circle.y >> circle.r;
    Minimize(min_x, circle.x);
    Minimize(min_y, circle.y);
  }
  for (auto& circle : circles) {
    circle.x -= min_x;
    circle.y -= min_y;
  }

  vec<int, 1> ord_circles(n_circles); iota(ALL(ord_circles), 0);
  sort(ALL(ord_circles), [&](int i, int j) {
    return circles[i].r != circles[j].r ? circles[i].r > circles[j].r : i < j;
  });

  int scaler = 31;
  vec<pair<int, int>, 2> members_groups(1);
  for (int i = 0; i < n_circles; ++i) {
    members_groups[0].emplace_back(circles[i].y, i);
  }
  sort(ALL(members_groups[0]));

  vec<bool, 1> deleted(n_circles);
  vec<int, 1> answers(n_circles);
  for (auto& idx_circle : ord_circles) {
    if (!deleted[idx_circle]) {
      deleted[idx_circle] = true;
      answers[idx_circle] = idx_circle;

      while (scaler && circles[idx_circle].r <= (1 << (scaler - 1))) {
        --scaler;

        vec<pair<int, int>, 2> next_members_groups;
        for (auto& members : members_groups) {
          array<vec<pair<int, int>, 1>, 2> tmp_members;
          for (auto& member : members) {
            if (deleted[member.second]) {
              continue;
            }
            tmp_members[(circles[member.second].x >> scaler) & 1].emplace_back(member);
          }
          if (SZ(tmp_members[0])) {
            next_members_groups.emplace_back(tmp_members[0]);
          }
          if (SZ(tmp_members[1])) {
            next_members_groups.emplace_back(tmp_members[1]);
          }
        }

        members_groups.swap(next_members_groups);
      }

      for (auto it_members_groups = lower_bound(ALL(members_groups), (circles[idx_circle].x >> scaler) - 2, [&](vec<pair<int, int>, 1> i, int j) { return (circles[i[0].second].x >> scaler) < j; }); it_members_groups != members_groups.end() && (circles[(*it_members_groups)[0].second].x >> scaler) <= (circles[idx_circle].x >> scaler) + 2; ++it_members_groups) {
        for (auto it_members = lower_bound(ALL(*it_members_groups), (circles[idx_circle].y >> scaler) - 2, [&](pair<int, int> i, int j) { return (i.first >> scaler) < j; });
        it_members != it_members_groups->end() && (it_members->first >> scaler) <= (circles[idx_circle].y >> scaler) + 2; ++it_members) {
          if (circles[idx_circle].CheckIntersection(circles[it_members->second])) {
            deleted[it_members->second] = true;
            answers[it_members->second] = idx_circle;
          }
        }
      }
    }
  }

  for (auto& answer : answers) {
    cout << answer + 1 << ' ';
  }
  cout << '\n';

  return 0;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Incorrect 0 ms 384 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 204 ms 16744 KB Output is correct
2 Incorrect 203 ms 16924 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 233 ms 8796 KB Output is correct
3 Correct 977 ms 24752 KB Output is correct
4 Correct 1018 ms 26564 KB Output is correct
5 Correct 976 ms 23148 KB Output is correct
6 Correct 317 ms 12444 KB Output is correct
7 Correct 151 ms 6968 KB Output is correct
8 Correct 29 ms 2164 KB Output is correct
9 Correct 943 ms 25904 KB Output is correct
10 Correct 836 ms 23216 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1025 ms 19152 KB Output is correct
2 Correct 1747 ms 58812 KB Output is correct
3 Incorrect 484 ms 17960 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Incorrect 0 ms 384 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Incorrect 0 ms 384 KB Output isn't correct
11 Halted 0 ms 0 KB -