제출 #959523

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
959523		rxlfd314	원 고르기 (APIO18_circle_selection)	C++17	15 / 100	1441 ms	26196 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;
      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;
          if (good(i, ij))
            ans[ij] = i;
        }
    }
  }
  FOR(i, 0, N-1)
    cout << (ans[i]<0 ? i : ans[i]) + 1 << "\n "[i+1<N], assert(ans[i] >= 0);
}

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