Submission #399820

#	Time	Username	Problem	Language	Result	Execution time	Memory
399820		my99n	Circle selection (APIO18_circle_selection)	C++14	0 / 100	3101 ms	97580 KiB

circle_selection

#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<long long,long long> point;
 
struct A {
  long long x, y, r;
  int i;
  bool operator < (const A & o) const {
    if (r == o.r) return i < o.i;
    return r > o.r;
  }
} ori[300100], cir[300100];
 
struct X {
  long long x;
  int i, t;
  bool operator < (const X & o) const {
    if (x == o.x) return i < o.i;
    return x < o.x;
  }
};

struct Y {
  long long y; 
  int i, t;
  bool operator < (const Y & o) const {
    if (y == o.y) return i < o.i;
    return y < o.y;
  }
};

set<X> sx;
set<Y> sy;
 
int ans[300100];
 
long long dis (point i, point j) {
  long long temp = ((i.x-j.x) * (i.x-j.x)) + ((i.y-j.y) * (i.y-j.y));
  return temp;
}
 
bool intersect (A i, A j) {
  return (dis({i.x, i.y}, {j.x, j.y}) <= (i.r+j.r)*(i.r+j.r));
}

bool cover (A i, long long x, long long y) {
  return intersect(i, {x, y, 0, -1});
}
 
int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int n; cin >> n;
  for (int i = 1; i <= n; i++) {
    long long x, y, r; cin >> x >> y >> r;
    ori[i] = cir[i] = {x, y, r, i};
    sx.insert({x+r, i, 1});
    sx.insert({x-r, i, 0});
    sy.insert({y+r, i, 1});
    sy.insert({y-r, i, 0});
  }
  sort(cir+1, cir+1+n);
 
  for (int i = 1; i <= n; i++) {
    int ind = cir[i].i;
    if (ans[ind]) continue;

    // cerr << ind << endl;

    auto a = sx.lower_bound({ori[ind].x, ind, -1});
    if (a != sx.begin()) {
      auto x = prev(a);
      while (x != sx.begin()) {
        if (abs(x->x-ori[ind].x) > ori[ind].r) break;
        if (ans[x->i] != 0) {
          auto temp = x--;
          sx.erase(temp);
          continue;
        }
        if (!intersect(ori[ind], ori[x->i])) {x--; continue;}
        ans[x->i] = ind;
        // cerr << "ans" << ' ' <<  x->i << ' ' << ind << endl;
        auto temp = x--;
        sx.erase(temp);
      }
      if (x == sx.begin() and intersect(ori[ind], ori[x->i])) {
        if (!ans[x->i]) {
          ans[x->i] = ind;
          // cerr << "ans" << ' ' <<  x->i << ' ' << ind << endl;
        }
        auto temp = x;
        sx.erase(temp);
      }
    }
    auto x = a;
    while (x != sx.end()) {
      if (abs(x->x-ori[ind].x) > ori[ind].r) break;
      if (ans[x->i] != 0) {
        auto temp = x++;
        sx.erase(temp);
        continue;
      }
      if (!intersect(ori[ind], ori[x->i])) {x--; continue;}
      ans[x->i] = ind;
      // cerr << "ans" << ' ' <<  x->i << ' ' << ind << endl;
      auto temp = x++;
      sx.erase(temp);
    }


    auto b = sy.lower_bound({ori[ind].y, ind, -1});
    if (b != sy.begin()) {
      auto y = prev(b);
      while (y != sy.begin()) {
        if (abs(y->y-ori[ind].y) > ori[ind].r) break;
        if (ans[y->i] != 0) {
          auto temp = y--;
          sy.erase(temp);
          continue;
        }
        if (!intersect(ori[ind], ori[y->i])) {y--; continue;}
        ans[y->i] = ind;
        // cerr << "ans" << ' ' <<  y->i << ' ' << ind << endl;
        auto temp = y--;
        sy.erase(temp);
      }
      if (y == sy.begin() and intersect(ori[ind], ori[y->i])) {
        if (!ans[y->i]) {
          ans[y->i] = ind;
          // cerr << "ans" << ' ' <<  y->i << ' ' << ind << endl;
        }
        auto temp = y;
        sy.erase(temp);
      }
    }
    auto y = b;
    while (y != sy.end()) {
      if (abs(y->y-ori[ind].y) > ori[ind].r) break;
      if (ans[y->i] != 0) {
        auto temp = y++;
        sy.erase(temp);
        continue;
      }
      if (!intersect(ori[ind], ori[y->i])) {y--; continue;}
      ans[y->i] = ind;
      // cerr << "ans" << ' ' <<  y->i << ' ' << ind << endl;
      auto temp = y++;
      sy.erase(temp);
    }

    ans[ind] = ind;
    // cerr << "ans " << ind << ' ' << ind << endl;

  }
 
  for (int i = 1; i <= n; i++) {
    cout << ans[i] << ' ';
  } cout << endl;
  return 0;
}
/*
11 
9 9 2
13 2 1
11 8 2
3 3 2
3 12 1
12 14 1
9 8 5
2 8 2
5 2 1
14 4 2
14 14 1
*/

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