Submission #963462

#	Time	Username	Problem	Language	Result	Execution time	Memory
963462		nguyentunglam	Circle selection (APIO18_circle_selection)	C++17	100 / 100	1266 ms	108856 KiB

circle_selection

#include<bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define endl "\n"
#define int long long
using namespace std;

const int N = 3e5 + 10;

int n;

int x[N], y[N], r[N], dd[N];

int ans[N];

int R;

vector<int> arr[N];

vector<pair<int, int> > rrh;

int idx (int x, int y) {
  int ret = upper_bound(all(rrh), make_pair(x, y)) - rrh.begin();
  if (rrh[ret - 1].first == x && rrh[ret - 1].second == y) return ret;
  return 0;
}

void rebuild () {
  rrh.clear();
  for(int i = 1; i <= n; i++) rrh.emplace_back(x[i] / R, y[i] / R);

  sort(all(rrh));
  rrh.resize(unique(all(rrh)) - rrh.begin());

  for(int i = 1; i <= rrh.size(); i++) arr[i].clear(), dd[i] = 0;

  for(int i = 1; i <= n; i++) {
    arr[idx(x[i] / R, y[i] / R)].push_back(i);
  }
}

int32_t main() {
  #define task ""

  cin.tie(0) -> sync_with_stdio(0);

  if (fopen("task.inp", "r")) {
    freopen("task.inp", "r", stdin);
    freopen("task.out", "w", stdout);
  }

  if (fopen(task".inp", "r")) {
    freopen (task".inp", "r", stdin);
    freopen (task".out", "w", stdout);
  }

  cin >> n;

  for(int i = 1; i <= n; i++) cin >> x[i] >> y[i] >> r[i];

  vector<pair<int, int> > order;

  for(int i = 1; i <= n; i++) order.emplace_back(r[i], -i);

  sort(all(order), greater<pair<int, int> > ());

  R = order[0].first;
  rebuild();

  for(auto &[radius, i] : order) {
    i = -i;
//    cout << i << " " << ans[i] << endl;
    if (ans[i]) continue;
    int cur = idx(x[i] / R, y[i] / R);
    if (dd[cur]) {
      R = radius;
      rebuild();
    }
    else dd[cur] = 1;

    for(int deltax = -2; deltax <= 2; deltax++) for(int deltay = -2; deltay <= 2; deltay++) {
      int pos = idx(x[i] / R + deltax, y[i] / R + deltay);
      for(auto &j : arr[pos]) if (!ans[j]) {
        if (1LL * (x[i] - x[j]) * (x[i] - x[j]) + 1LL * (y[i] - y[j]) * (y[i] - y[j]) <= 1LL * (r[i] + r[j]) * (r[i] + r[j])) {
          ans[j] = i;
        }
      }
    }
  }

  for(int i = 1; i <= n; i++) cout << ans[i] << " ";
}

Compilation message (stderr)

circle_selection.cpp: In function 'void rebuild()':
circle_selection.cpp:34:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |   for(int i = 1; i <= rrh.size(); i++) arr[i].clear(), dd[i] = 0;
      |                  ~~^~~~~~~~~~~~~
circle_selection.cpp: In function 'int32_t main()':
circle_selection.cpp:47:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |     freopen("task.inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
circle_selection.cpp:48:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |     freopen("task.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
circle_selection.cpp:52:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |     freopen (task".inp", "r", stdin);
      |     ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
circle_selection.cpp:53:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |     freopen (task".out", "w", stdout);
      |     ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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