Submission #959534

#	Time	Username	Problem	Language	Result	Execution time	Memory
959534		rxlfd314	Circle selection (APIO18_circle_selection)	C++17	100 / 100	1747 ms	25240 KiB

circle_selection

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using ari2=array<int,2>;
using ari3=array<int,3>;

#define vt vector
#define size(x) (int((x).size()))
#define all(x) begin(x), end(x)

#define REP(a,b,c,d) for (int a=(b);(d)>0?a<=(c):a>=(c);a+=(d))
#define FOR(a,b,c) REP(a,b,c,1)
#define ROF(a,b,c) REP(a,b,c,-1)

signed main() {
#ifndef DEBUG
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
#endif
  int N;
  cin >> N;
  vt<int> X(N), Y(N), R(N);
  FOR(i, 0, N-1)
    cin >> X[i] >> Y[i] >> R[i];
  vt<int> ord(N);
  iota(all(ord), 0);
  sort(all(ord), [&](const int &a, const int &b) {
    return ari2{R[a], b} > ari2{R[b], a};   
  });
  auto good = [&](int i, int j) {
    auto sq = [&](int x) {
      return 1ll * x * x;
    };  
    return sq(X[i]-X[j]) + sq(Y[i]-Y[j]) <= sq(R[i]+R[j]);
  };
  vt<int> ans(N, -1);
  for (int r=1<<30; r>0; r>>=1) {
    vt<ari3> points;
    FOR(i, 0, N-1)
      if (ans[i] < 0)
        points.push_back({X[i]/r, Y[i]/r, i});
    sort(all(points));
    for (int i : ord) {
      if (ans[i] >= 0 || R[i] < r/2 || R[i] > r)
        continue;
      #ifdef DEBUG
      cout << "trying circle " << i+1 << " with r = " << r << '\n';
      #endif
      ans[i] = i;
      int x = X[i] / r;
      int y = Y[i] / r;
      FOR(d, -2, 2)
        FOR(j, lower_bound(all(points), ari3{x+d, y-2, 0}) - begin(points), size(points)-1) {
          auto [xj, yj, ij] = points[j];
          if (xj != x+d || abs(yj-y) > 2)
            break;
          #ifdef DEBUG
          cout << "does circle " << ij+1 << " work\n";
          #endif
          if (good(i, ij) && ans[ij] < 0)
            ans[ij] = i;
        }
    }
  }
  for (int &i : ans)
    cout << i+1 << ' ';
  cout << '\n';
}

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