Submission #316906

#	Time	Username	Problem	Language	Result	Execution time	Memory
316906		casperwang	Circle selection (APIO18_circle_selection)	C++14	100 / 100	2044 ms	25540 KiB

circle_selection

#include <bits/stdc++.h>
#define pb push_back
#define ll long long
#define pii pair<int,int>
#define ppi pair<pii,int>
#define ff first
#define ss second
using namespace std;

const int MAXN = 300000;

struct Cir{
  int x, y, r, id;
  Cir() {}
  Cir(int _x, int _y, int _r, int _id) {
    x = _x, y = _y, r = _r, id = _id;
  }
};

bool intersect(const Cir &a, const Cir &b) {
  return (ll)(a.x-b.x)*(a.x-b.x)+(ll)(a.y-b.y)*(a.y-b.y) <= (ll)(a.r+b.r)*(a.r+b.r);
}

signed main() {
  ios_base::sync_with_stdio(0), cin.tie(0);
  int n;
  cin >> n;
  vector <Cir> cir, tmp;
  for (int i = 0; i < n; i++) {
    int x, y, r;
    cin >> x >> y >> r;
    cir.pb(Cir(x, y, r, i+1));
  }
  sort(cir.begin(), cir.end(), [](const Cir a, const Cir b){
      return a.r != b.r ? a.r > b.r : a.id < b.id;
      });
  int now_r = cir[0].r+1;
  vector <int> ans(n+1);
  while (cir.size()) {
    vector <ppi> arr;
    for (int i = 0; i < cir.size(); i++)
      arr.pb(ppi(pii(cir[i].x / now_r, cir[i].y / now_r), i));
    sort(arr.begin(), arr.end());
    for (Cir C : cir) {
      if (ans[C.id]) continue;
      if (C.r < now_r/2) break;
      int X = C.x / now_r, Y = C.y / now_r;
      ppi grid;
      grid.ss = 0;
      grid.ff.ss = Y-2;
      for (int i = X-2; i <= X+2; i++) {
        grid.ff.ff = i;
        int p = lower_bound(arr.begin(), arr.end(), grid) - arr.begin();
        if (p == arr.size() || arr[p].ff.ff != i) continue;
        while (p < arr.size() && arr[p].ff.ff == i && arr[p].ff.ss <= Y+2) {
          if (!ans[cir[arr[p].ss].id] && intersect(C, cir[arr[p].ss]))
            ans[cir[arr[p].ss].id] = C.id;
          p++;
        }
      }
    }
    arr.clear();
    for (Cir C : cir)
      if (!ans[C.id]) tmp.pb(C);
    cir = tmp;
    tmp.clear();
    now_r /= 2;
  }
  for (int i = 1; i <= n; i++)
    cout << ans[i] << " \n"[i==n];
  return 0;
}

Compilation message (stderr)

circle_selection.cpp: In function 'int main()':
circle_selection.cpp:41:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Cir>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     for (int i = 0; i < cir.size(); i++)
      |                     ~~^~~~~~~~~~~~
circle_selection.cpp:54:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |         if (p == arr.size() || arr[p].ff.ff != i) continue;
      |             ~~^~~~~~~~~~~~~
circle_selection.cpp:55:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |         while (p < arr.size() && arr[p].ff.ff == i && arr[p].ff.ss <= Y+2) {
      |                ~~^~~~~~~~~~~~

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