Submission #265063

#	Time	Username	Problem	Language	Result	Execution time	Memory
265063		extraterrestrial	Circle selection (APIO18_circle_selection)	C++14	19 / 100	3053 ms	74928 KiB

circle_selection

#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
using namespace std;
#define F first
#define S second
#define pb push_back  
#define all(x) (x).begin(), (x).end()
#define SZ(x) (int)(x).size()
#define int ll    

const int N = 3e5 + 10;
int x[N], y[N], r[N], ans[N];

bool inter(int id1, int id2) {
  return (x[id1] - x[id2]) * (x[id1] - x[id2]) + (y[id1] - y[id2]) * (y[id1] - y[id2]) <= (r[id1] + r[id2]) * (r[id1] + r[id2]); 
}

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0); 
  cout.tie(0);
  int n;
  cin >> n;
  bool group2 = true;
  for (int i = 0; i < n; i++) {
    cin >> x[i] >> y[i] >> r[i];
    if (y[i] != 0) {
      group2 = false;
    }
  }
  if (!group2) {
    vector<bool> used(n);
    int cnt = 0;
    while (cnt < n) {
      pair<int, int> best = {1e9, 1e9};
      for (int i = 0; i < n; i++) {
        if (!used[i]) {
          best = min(best, make_pair(-r[i], i));
        }
      }
      //cout << best.S + 1 << '\n';
      cnt++;
      used[best.S] = true;
      ans[best.S + 1] = best.S + 1;
      for (int i = 0; i < n; i++) {
        if (!used[i] && inter(i, best.S)) {
          used[i] = true;
          ans[i + 1] = best.S + 1;
          cnt++;
        }
      }
    }
  }
  else {
    set<pair<int, int>> unused, lef, rig;
    for (int i = 0; i < n; i++) {
      unused.insert({-r[i], i});
      lef.insert({x[i] - r[i], i});
      rig.insert({x[i] + r[i], i});
    }
    while (!unused.empty()) {
      int id = unused.begin()->S;
      ans[id + 1] = id + 1;
      unused.erase(unused.begin());
      lef.erase({x[id] - r[id], id});
      rig.erase({x[id] + r[id], id});
      for (;;) {
        auto it = lef.upper_bound(make_pair(x[id] + r[id], 1e9));
        if (it == lef.begin()) {
          break;
        }
        it--;
        if (it->F < x[id] - r[id]) {
          break;
        }
        ans[it->S + 1] = id + 1;
        unused.erase({-r[it->S], it->S});
        lef.erase({x[it->S] - r[it->S], it->S});
        rig.erase({x[it->S] + r[it->S], it->S});
      }

      for (;;) {
        auto it = rig.lower_bound(make_pair(x[id] - r[id], 0));
        if (it == rig.end()) {
          break;
        }
        if (it->F > x[id] + r[id]) {
          break;
        }
        ans[it->S + 1] = id + 1;
        unused.erase({-r[it->S], it->S});
        lef.erase({x[it->S] - r[it->S], it->S});
        rig.erase({x[it->S] + r[it->S], it->S}); 
      } 
    }
  }
  for (int i = 1; i <= n; i++) {
    cout << ans[i] << ' ';
  }
  cout << '\n';
}

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